Collaborative Research: Distributed Collaborative Computing and Adversity

University Of Colorado At Denver-Downtown Campus, Denver CO

Investigators

Abstract

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 on the 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 of distributed computing which, unlike uniprocessor computing, has suffered from steadfast disagreement about the validity of extant low-level models. The proposed research involves several well-prepared graduate students. The project, while addressing issues of interest to the entire distributed computing community, is an opportunity for these students to apply tools from applied mathematics to problems in computer science, become expert with extant low-level computing models, and engage in original research in the foundations of distributed computation.