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

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

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.