For many distributed computing problems there exists a characterizing combinatorial structure. In other words, the existence of an algorithm for solving the problem on any graph G in time T(G) implies the existence of the structure in G with some parameter related to T(G), and vice versa. Such relations go back to classic examples, such as synchronizers and sparse spanners, and continue to emerge in recent studies of gossip algorithms and multicast algorithms in different communication settings. In this talk I will give an overview of both old and recent results that illustrate these connections. I will show how finding distributed algorithms as well as proving lower bounds can be reduced to studying combinatorial graph structures.

Symmetry breaking problems pervade every area of distributed computing. The devices in a distributed system are often assumed to be initially undifferentiated, except for possibly having distinct IDs. In order to accomplish basic tasks they must break this initial symmetry. In distributed graph algorithms (where the communications network and the input graph are identical) some symmetry breaking tasks include computing maximal matchings, vertex- and edge-colorings, maximal independent sets (MIS), and t-ruling sets. Running time is usually measured in rounds of communication, and expressed as a function of two parameters: n, the number of nodes, and Δ, the maximum node degree.

Randomization is one of the most powerful tools used by efficient distributed symmetry breaking algorithms. With only a few exceptions, the randomized algorithms are always faster than their deterministic competitors, often exponentially faster. However, the power of randomization seems to be greatly diminished when Δ drops below a critical threshold. In a common situation, nodes fail to achieve their goal with probability e^−Δ, which is insufficient to obtain high probability bounds (in n) when Δ is sub-logarithmic.

In the first part of the talk I’ll survey the probabilistic tools used to analyze the state-of-the-art algorithms for MIS, maximal matching, and coloring. In the second part of the talk I’ll introduce distributed algorithms for the constructive Lovász Local Lemma (LLL), and show how they can be applied to solve distributed symmetry breaking problems when Δ is too small for conventional probabilistic analyses. The LLL states that in any set of n “bad” events, each occurring with probability at most p and each being independent of all but d other events, if ep(d + 1) < 1 then with positive (but maybe negligible) probability no bad event occurs.

Distributed computing models typically assume reliable communication between processors. While such assumptions often hold for engineered networks, e.g., due to underlying error correction protocols, their relevance to biological systems, wherein messages are often distorted before reaching their destination, is quite limited. We aim at bridging this gap by considering communication models in large anonymous populations composed of simple agents which interact through short and highly unreliable messages. In such settings, even basic distributed computing tasks become difficult. In this talk, I will discuss some of the difficulties that may arise when messages can be distorted. I will focus on the rumor-spreading problem and the majority-consensus problem, and propose extremely simple algorithms that solve these problems efficiently despite the severely restricted, stochastic and noisy setting assumed. These algorithms suggest balancing between silence and transmission, synchronization, and majority-based decisions as important ingredients towards understanding collective communication schemes in anonymous and noisy populations.

This talk is based on a joint work with Ofer Feinerman and Bernhard Haeupler.

Many real-world networks and optimization problem instances have a planar-like structure that allows for simpler, more efficient, and highly practical algorithms. The study of such network structures and their algorithmic implications has been a very successful endeavor with a rich theory and many versatile tools leading to significant algorithmic advances on problem instances of interest. Unfortunately these powerful tools and algorithms do not carry over to the distributed setting and very little is known about how distributed algorithms for important standard optimization problems such as minimum spanning tree, maximum flow, or shortest path(s) can be improved on planar-like instances.

The goal of this talk is to propose the principled study of distributed algorithms for planar networks and the development of a distributed algorithmic toolbox for this setting. In particular, for networks with diameter D and standard bandwidth-limitations (CONGEST model) it would be great to obtain efficient planar network optimization algorithms running in O(D) synchronous rounds (up to additive/multiplicative polylogarithmic terms). This goal also very timely connects to recent, far-reaching, distributed lower bounds which show that in general (even degree bounded) graphs many optimization problems, such as minimum spanning tree, cannot be computed or even crudely approximated in less than Ω(n^1/2) rounds.

The talk will report on the initial progress and first insights obtained towards this goal and point at many more interesting challenges and open questions.

This talk will be centered around the problem of computing shortest paths on distributed networks. The purpose is twofold:

1. Surveying the state of the art and standard upper/lower bound techniques, as well as identifying challenging open problems in the area.
2. Showing some connections to other areas such as communication complexity, centralized dynamic algorithms, and streaming algorithms, to which perspectives from the distributed algorithm community could be helpful.

The talk will cover problems such as computing single-source and all-pair shortest paths on distributed, dynamic, and streaming settings, as well as some routing problems. It will also cover concepts such as backbone, spanner, hopset, and proving lower bounds from communication complexity.

In the field of distributed graph algorithms, the time complexity (i.e., the number of communication rounds) is commonly studied as a function of two parameters: n, the number of nodes in the input graph, and Δ, the maximum degree of the input graph.

For many problems, the landscape of time complexity is still largely unknown. There is, however, one part of the (n,Δ)-plane in which tight bounds appear to be finally within reach: the case of n >> Δ. In this talk I will give an overview of both classical results and recent progress related to this region, as well as highlights of open questions.

I will use distributed algorithms for the maximal matching problem as a running example:

• maximal matchings in general graphs: can be solved in time O(Δ + log* n)
• maximal matchings in bipartite graphs: can be solved in time O(Δ)
• maximal fractional matching in general graphs: can be solved in time O(Δ).

All of these are examples of “coordination problems”, which seem to require linear-in-Δ time (at least for n >> Δ). For maximal fractional matchings we can now prove this: the problem cannot be solved in time o(Δ) independently of n, with any deterministic or randomised distributed algorithm.