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

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