Research Initiation Award: Algorithms for On-Line and Distributed Systems

研究启动奖：在线和分布式系统算法

• 批准号: 9309456
• 负责人: Sandra Irani
• 金额: $ 5.26万
• 依托单位: University of California-Irvine
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1993
• 资助国家: 美国
• 起止时间: 1993-06-15 至 1997-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9309456&HistoricalAwards=false
• 关键词: Research; Initiation; Award; Algorithms; Line

This project focuses on algorithms that work on-line or with limited information. The project addresses three topics, each motivated by an application in on-line, distributed or parallel computation: (1) metrical task systems where the set of tasks (inputs to the system) are restricted. The restriction on the input is part of the description of the system. A general, simple algorithm is developed which uses the system specification to approximate the best on-line algorithm for each particular system; (2) distributed computation where a group of agents must collectively solve a problem. Each agent receives part of the input, and a graph is used to represent knowledge that is shared between the agents. How to use shared information between the agents to solve a distributed job scheduling problem and to determine the value of sharing information are determined; (3) the problem of partitioning elements of a partial order into disjoint chains on-line, and its applications to parallel computation are discussed.

这个项目的重点是在线工作或有限的信息的算法。 该项目涉及三个主题，每个主题 由在线、分布式或并行计算中的应用所激发：（1）其中任务集（系统的输入）受限的度量任务系统。 对输入的限制是系统描述的一部分。 开发了一种通用、简单的算法，它使用系统规范来逼近每个特定系统的最佳在线算法;（2）分布式计算，其中一组代理必须集体解决问题。 每个代理接收部分输入，并使用图来表示代理之间共享的知识。 讨论了如何利用Agent之间的共享信息来解决分布式作业调度问题以及共享信息的取值问题;（3）讨论了偏序元素的在线分割问题及其在并行计算中的应用。