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

这个项目研究分布式环境中的可计算性、算法和复杂性，在计算介质存在动态变化的情况下，大量机器协作解决计算问题。计算问题被建模为任务的集合，例如互联网超级计算中频繁出现的问题。这项研究有可能通过使用经过严格开发的算法来影响动态环境下的大规模协作计算，这些算法具有正式证明的效率和容错保证。从长远来看，这项研究还将对更广泛类别的自适应分布式系统的发展产生影响。本研究开发了能够在动态分布式环境下实现高效和容错的协作计算的高级算法。基本问题是根据需要执行一组任务的处理器集合来制定的，其中任务必须使用至少一次或至多一次的语义来执行。这项研究考虑了代表互联网超级计算情况的动态设置。合作模式包括：(A)先知模式，即中央当局向参与者提供信息。(B)主机-工人模式，即一个主机协调工人执行任务，这是互联网超级计算中的一个典型设置。(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.