ADGA is a one-day workshop that focuses on the theoretical foundations of distributed graph algorithms. The programme consists of several invited talks, which are aimed at the general DISC audience.

ADGA 2014 was held on **Sunday, 12 October 2014** in **Austin, Texas**, and it was co-located with **DISC 2014**. The workshop was chaired by Christoph Lenzen.

For information on past and future ADGA workshops, see the web site of the ADGA workshop series.

# Schedule

ADGA programme | ||
---|---|---|

8:30 am | talk 1 | Keren Censor-Hillel: Distributed Algorithms as Combinatorial Structures |

9:30 am | coffee break | |

9:45 am | talk 2 | Seth Pettie: Randomized Symmetry Breaking and the Constructive Lovász Local Lemma |

10:45 am | coffee break | |

11:00 am | talk 3 | Amos Korman: Efficient Information Dissemination despite Noisy Communication |

12:00 pm | lunch break | |

1:30 pm | talk 4 | Bernhard Haeupler: Distributed Graph Algorithms for Planar Networks |

2:30 pm | coffee break | |

2:45 pm | talk 5 | Danupon Nanongkai: Distributed Shortest Paths and Related Problems |

3:45 pm | coffee break | |

4:00 pm | talk 6 | Jukka Suomela: Lower Bounds for Local Algorithms |

5:00 pm | workshop ends | |

DISC programme | ||

6:00 pm | DISC Welcome Reception (until 8:00 pm) |

# Invited Speakers

Technion

Keren Censor-Hillel is an Assistant Professor at the Department of Computer Science at the Technion — Israel Institute of Technology. She received her PhD from the Technion and was afterwards a Simons Postdoctoral Fellow at MIT. Her research interests are in theory of computation and focus on distributed computing. Censor-Hillel is a Shalon Fellow, and also received an Alon Fellowship. Previously she was also a Rothschild Fellow, and received an Adams Fellowship from the Israel Academy of Sciences and Humanities and a Google Anita Borg Memorial Scholarship, as well as additional research and teaching awards.

Distributed Algorithms as Combinatorial Structures

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.

Presentation slides: PDF

University of Michigan

Seth Pettie is an Associate Professor of Computer Science and Engineering at the University of Michigan, Ann Arbor. He received his Ph.D. from the University of Texas at Austin, in 2003. He was a postdoctoral researcher at the Max Planck Institute for Informatics, from 2003–2006, and was supported by an Alexander von Humboldt Fellowship. His research focuses on combinatorics, data structures, and algorithm design for both distributed and centralized models of computation.

Randomized Symmetry Breaking and the Constructive Lovász Local Lemma

*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.

Presentation slides: PPTX

CNRS and University Paris Diderot

Amos Korman is a permanent researcher in CNRS located at LIAFA in the University of Paris Diderot. He received a Ph.D. degree in Computer Science from the Weizmann Institute of Science under the guidance of Prof. David Peleg. His thesis “Static and Dynamic Labeling Schemes” won the Dean’s Prize for Ph.D. Students. Amos’ main research interest includes various fundamental aspects of distributed computing. In particular, he is interested in abstract models that aim to improve our understanding of the notion of locality. Recently, Amos has become particularly intrigued with in applying ideas and techniques from theoretical distributed computing studies to improve our understanding of complex biological systems.

Efficient Information Dissemination despite Noisy Communication

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.

Presentation slides: PDF

Carnegie Mellon University

Bernhard Haeupler is an Assistant Professor at the Computer Science Department of Carnegie Mellon University. He received his PhD and MSc in Computer Science from MIT, and a B.Sc., MSc and Diploma in Mathematics from the Technical University of Munich. He has (co-)authored over 40 publications and won several awards for his dissertation and his research. Bernhard’s research interests lie in the intersection of classical algorithm design, distributed computing, and information theory.

Distributed Graph Algorithms for Planar Networks

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.

Presentation slides: PDF

University of Vienna

Danupon is an assistant professor at the University of Vienna, Austria. He received his PhD from Georgia Tech and was afterwards a postdoctoral fellow at University of Vienna, Nanyang Technological University, and Brown University. His main research interest is on attacking basic graph problems from the communication perspective and spans research areas such as distributed computing, dynamic algorithms, and approximation algorithms.

Distributed Shortest Paths and Related Problems

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

- Surveying the state of the art and standard upper/lower bound techniques, as well as identifying challenging open problems in the area.
- 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.

Presentation slides: PDF

Aalto University

Jukka Suomela is an Assistant Professor in the Department of Information and Computer Science at Aalto University. He received his PhD from the University of Helsinki in 2009, and the title of Docent in Computer Science in 2012. Suomela’s research group conducts basic research related to the theoretical foundations of distributed computing, with particular emphasis on the concept of locality in the context of distributed graph algorithms.

Lower Bounds for Local Algorithms

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.

Presentation slides: PDF

Further information:

- Göös et al. (2014): Linear-in-Δ lower bounds in the LOCAL model