AF: Small: Collaborative Research: Principles of Robust Cooperative Computing in Dynamic Distributed Systems

AF：小型：协作研究：动态分布式系统中鲁棒协作计算的原理

• 批准号: 1017232
• 负责人: Alexander Schwarzmann
• 金额: $ 30万
• 依托单位: University of Connecticut
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1017232&HistoricalAwards=false
• 关键词: AF; Small; Collaborative; Research; Principles

This project investigates computability, algorithmics, and complexity in distributed settings with large numbers of machines cooperating on solving computation problems in the presence of dynamic changes in the computing medium. The computation problems are modeled as collections of tasks, such as the problems frequently occurring in the Internet supercomputing. This research has the potential to impact massive cooperative computing in dynamic settings through the use of rigorously developed algorithms with formally proved efficiency and fault-tolerance guarantees. In the longer term this research will also have impact on the development of broader classes of adaptive distributed systems.This research develops advanced algorithms enabling efficient and fault-tolerant cooperative computing in dynamic distributed settings. The basic problem is formulated in terms of a collection of processors that need to perform a set of tasks, where the tasks must be executed using either at-least-once or at-most-once semantics. The research considers dynamic settings that are representative of situations in Internet supercomputing. The models of cooperation include: (a) oracle model, where a central authority provides information to the participants. (b) master-worker model, where a single master coordinates the workers in performing the tasks, a typical setting in Internet supercomputing. (c) peer-to-peer mode, where fully-distributed solutions will be investigated, enabling much more dynamic and fault-tolerant solutions. The investigation includes the associated resource discovery problem of identifying the nodes in the distributed system that are willing and able to cooperate; here the investigation focuses on more realistic settings than previously considered. This research also studies supporting services that can provide effective implementations of communication and shared-memory primitives in target dynamic platforms. The quality of algorithms is evaluated using corresponding lower bounds and impossibility results.

该项目研究分布式环境中的可计算性、算法和复杂性，其中大量机器在计算介质存在动态变化的情况下合作解决计算问题。计算问题被建模为任务的集合，例如互联网超级计算中经常出现的问题。这项研究有可能通过使用经过正式证明的效率和容错保证的严格开发的算法来影响动态设置中的大规模协作计算。从长远来看，这项研究还将对更广泛的自适应分布式系统的开发产生影响。这项研究开发了先进的算法，可在动态分布式设置中实现高效且容错的协作计算。基本问题是根据需要执行一组任务的处理器集合来表述的，其中必须使用至少一次或最多一次语义来执行任务。该研究考虑了代表互联网超级计算情况的动态设置。合作模式包括： (a) 预言机模式，由中央机构向参与者提供信息。 (b) 主从模型，其中单个主节点协调工作节点执行任务，这是互联网超级计算中的典型设置。 (c) 对等模式，将研究完全分布式的解决方案，从而实现更加动态和容错的解决方案。调查包括相关的资源发现问题，即识别分布式系统中愿意并且能够合作的节点；这里的调查重点是比之前考虑的更现实的环境。这项研究还研究了支持服务，这些服务可以在目标动态平台中提供通信和共享内存原语的有效实现。使用相应的下限和不可能性结果来评估算法的质量。