A fundamental problem in distributed algorithm theory is reducing contention among an unknown set of processes attempting to communicate on a shared channel. In the 1980s, Bar-Yehuda, Goldreich and Itai (BGI) introduced a surprisingly simple randomized distributed algorithm for broadcasting a single message to all processes on a multihop shared channel. Their solution solved the problem faster (with high probability) than the best known centralized scheduling algorithm at the time. It was later proved to be optimal among all possible distributed algorithms.

In this talk, I will discuss the backstory and impact of the BGI broadcast algorithm. I will then detail our recent efforts to explore the behavior of this basic strategy in more realistic (i.e., less well-behaved) variations of the radio network model — efforts that culminated in establishing that the BGI algorithm retains strong guarantees even in very noisy and unpredictable radio networks.

My goal is to underscore the surprising and elegant effectiveness of this seemingly simple strategy.

In this talk, we will survey recent work on designing algorithms for analyzing massive graphs via data streams and linear sketches. We will consider a range of problems including connectivity and sparsification; matchings and vertex cover; and correlation clustering and clustering coefficients.

This talk is about the amount of communication needed to construct a spanning tree (and minimum spanning tree) of a distributed network where each node has only local information about the network and communication is by message-passing. While this problem has been studied for thirty years or more, it is still not fully understood. I’ll survey the known techniques for upper and lower bounds and the open problems in this area.

One strange aspect of the LOCAL model is that there are many “unnatural” ranges of computational complexities for locally checkable graph labeling problems. These complexity gaps are proved via automatic-speedup theorems. In this talk I will survey how 5 of the automatic speedup theorems work. In particular, on constant-degree graphs:

• Any o(log(log* n))-time algorithm can be mechanically converted to an O(1)-time algorithm. The argument makes use of hypergraph Ramsey numbers.
• Any o(log n)-time deterministic algorithm and any o(log log n)-time randomized algorithm can be converted to an O(log* n) deterministic algorithm. The proof uses a derandomization technique reminiscent of the classic proof that BPP ⊆ P/poly.
• Any o(log n)-time randomized algorithm can be sped up to run in the complexity of the distributed Lovasz Local Lemma (LLL) problem.
• Any algorithm that runs in n^o(1)-time on trees can be sped up to run in O(log n) time on trees. The proof is based on the pumping lemma for regular languages.

Automatic-speedup is one of the principle techniques used to develop fast, sublogarithmic Distributed LLL algorithms.

This talk is based on work by Naor and Stockmeyer (SICOMP 1995), Chang, Kopelowitz, and Pettie (FOCS 2016), Chang and Pettie (FOCS 2017).

Despite being one of the major classic graph problems, there is no truly satisfying algorithm for computing single-source shortest paths in distributed and parallel models of computation. In the CONGEST model, this problem has received considerable attention in recent years leading to nearly optimal approximation algorithms. As a consequence, researchers have now started to tackle the exact version of the problem. In this talk, I will review my recent contributions to this line of research.

Population protocols are a popular model of distributed computing, in which agents with limited local state interact randomly in pairs, according to an underlying communication graph, and cooperate to collectively compute global predicates. Introduced to model animal populations equipped with sensors, they have proved a useful abstraction for settings from wireless sensor networks, to gene regulatory networks, and chemical reaction networks. From theoretical prospective, population protocols, with the restricted communication and computational power, are probably the simplest distributed model. Yet, perhaps surprisingly, solutions to classical distributed tasks are still possible. Moreover, these solutions often rely on neat algorithmic ideas for design and interesting combinatorial techniques for analysis.

Inspired by recent developments in DNA programming, an extensive series of papers, across different communities, has examined the computability and complexity characteristics of this model. I will review some of these recent developments, as well as open problems and directions.