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.