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.

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