Collaborative Research: Distributed Collaborative Computing and Adversity

该项目推进了在逆境中分布式协作计算能力的最新进展。这是通过为基本的分布式计算原语建立复杂性界限来实现的。需要分布式协作的关键问题包括：在分布式环境中执行一组共同的任务，在并行环境中修改共享内存，分布式协作调度，集体掷硬币和领导人选举，以及消息传递环境中的八卦和共识算法。这项研究沿着两个互补的方向进行：(1)抽象信息模型中的分布式可计算性，(2)特定计算模型中的分布式算法。信息模型是对分布式系统中的信息建模的工具。信息模型捕捉了大类低级计算模型的本质特征：通过证明选定的信息模型的强界，本研究在现有的低级模型中提取了关于分布式计算的新事实，并扩展了对分布式计算的基本成分的理解。信息模型以与特定低级模型的特性隔离的方式促进关于分布式算法的推理，例如，在关于同步的各种假设下的共享存储器或消息传递模型。第二个研究方向通过从算法角度探讨分布式计算环境的基本特性和内在局限性来支持信息模型的研究。本研究考虑计算模型，明确关注多个协作处理器使用的通信手段。在研究故障或异步性时，每个模型都会增加一个干扰通信的对手。目标是开发相对于同时反映几个标准复杂性度量(例如，时间、轮次、通信)的复合复杂性度量有效的算法。总而言之，这些方法通过将高层信息流与底层算法构建块分开处理来解决分布式算法设计和分析的问题。广泛的影响：作为一个整体，这个项目展示了一种新的方法来建模分布式计算问题的可行性。在这种“信息模型”方法中，人们用问题的共性来换取模型独立性；也就是说，通过关注关于信息流的高度具体的假设(它限制了模型捕获的一系列计算问题)，人们获得了与广泛类别的低级计算模型相关的结果。这样的框架对分布式计算的研究非常有吸引力。与单处理器计算不同，分布式计算的研究一直存在着对现有低级模型有效性的坚定分歧。该项目解决了整个分布式计算社区感兴趣的问题，为这些学生提供了一个机会，让他们将应用数学的工具应用于计算机科学中的问题，成为现有低级计算模型的专家，并从事分布式计算基础的原创性研究。

This project advances the state-of-the-art in distributed collaborative computability in the presence of adversity. This is accomplished by establishing complexity bounds for fundamental distributed computing primitives. The key problems requiring distributed collaboration include: performing a common set of tasks in a distributed setting, modifying shared memory in a parallel setting, distributed collaborative scheduling, collective coin-flipping and leader election, and algorithms for gossip and consensus in message-passing settings. This research is pursued along two complementary directions:(1) distributed computability in abstract information models, and(2) distributed algorithmics in specific models of computation.Information models are tools that model information in distributed systems. Information models capture essential features of wide classes of low-level computing models: by proving strong bounds in select information models, this research extracts new facts about distributed computation in extant low-level models and expands the understanding of the essential ingredients of distributed computation. Information models facilitate reasoning about distributed algorithms in a fashion insulated from the idiosyncrasies of particular low-level models, e.g., shared-memory or message-passing models under various assumptions about synchrony. The second research direction supports the information model research by exploring fundamental properties and intrinsic limitations of distributed computing environments from an algorithmic point of view.This research considers models of computation focusing explicitly onthe means of communication used by multiple collaborating processors. When studying failures or asynchrony, each of the models is augmented with an adversary that interferes with the communication. The goal is to develop algorithms that are efficient with respect to a composite complexity measure simultaneously reflecting several standard complexity measures (e.g., time, rounds, communication). Together, these approaches address the problem of distributed algorithm design and analysis by treating high-level information flow separately from the underlying algorithmic building blocks.Broad impact:This project, as a whole, demonstrates the feasibility of a new approach to the problem of modeling distributed computation. In this "information model" approach, one trades problem generality for model independence; that is, by focusing on highly specific assumptions about information flow (which restrict the family of computational problems captured by the model) one obtains results relevant to a wide class of low-level computing models. Such a framework is quite appealing for the study ofdistributed computing which, unlike uniprocessor computing, hassuffered from steadfast disagreement about the validity of extantlow-level models.The proposed research involves several well-prepared graduatestudents. The project, while addressing issues of interest tothe entire distributed computing community, is an opportunity forthese students to apply tools from applied mathematics to problems incomputer science, become expert with extant low-level computingmodels, and engage in original research in the foundations ofdistributed computation.