Collaborative Research: Distributed Collaborative Computing and Adversity

该项目推进了在逆境中分布式协作可计算性的最新发展。 这是通过为基本的分布式计算原语建立复杂性界限来实现的。需要分布式协作的关键问题包括：在分布式环境中执行一组公共任务，在并行环境中修改共享内存，分布式协作调度，集体抛硬币和领导者选举，以及消息传递环境中的八卦和共识算法。该研究沿着两个互补的方向进行：（1）抽象信息模型中的分布式可计算性，以及（2）特定计算模型中的分布式算法。信息模型捕捉广泛的低级别计算模型的基本特征：通过证明强界选择信息模型，本研究提取新的事实，分布式计算在现有的低级别模型和扩展的理解的基本成分的分布式计算。信息模型以与特定低级模型的特性绝缘的方式促进关于分布式算法的推理，例如，共享内存或消息传递模型在各种假设下的同步。第二个研究方向支持信息模型研究，从算法的角度探索分布式计算环境的基本属性和内在局限性，该研究考虑明确关注多个协作处理器使用的通信手段的计算模型。在研究故障或故障时，每个模型都增加了一个干扰通信的对手。目标是开发相对于同时反映若干标准复杂性度量的复合复杂性度量有效的算法（例如，时间、回合、通信）。总之，这些方法解决了分布式算法设计和分析的问题，分别从底层算法building blocks.Broad的影响：这个项目，作为一个整体，演示了一个新的方法来建模分布式计算的问题的可行性。在这种“信息模型”的方法，一个贸易问题的一般性模型的独立性，也就是说，通过专注于高度具体的假设信息流（这限制了家庭的计算模型捕获的问题），一个获得的结果相关的一个广泛的低级别计算模型。这样一个框架是非常有吸引力的分布式计算的研究，不像单处理器计算，遭受了坚定的分歧的有效性experimental低级别models.The拟议的研究涉及几个准备充分的研究生。该项目在解决整个分布式计算社区感兴趣的问题的同时，也为这些学生提供了一个机会，将应用数学工具应用于计算机科学问题，成为现有低级计算模型的专家，并从事分布式计算基础的原创研究。

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.