Collaborative Research: Distributed Collaborative Computing and Adversity

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.