ADGA 2016

5th Workshop on Advances in Distributed Graph Algorithms · Paris · 26 September 2016

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 2016 will be held on Monday, 26 September 2016 in Paris, France, and will be co-located with DISC 2016. The workshop will be chaired by Danupon Nanongkai.

For information on past and future ADGA workshops, see the web site of the ADGA workshop series. For information about the registration, please go to the DISC 2016 website.

Venue: The workshops will be held in room 25-26/105 at Université Pierre & Marie Curie at 1st floor of Tower 26, Campus de Jussieu, 4 place Jussieu, 75005 Paris (that is, first floor from Tower 26, corridor 26-25, room 105). For more information about venue please go to the DISC 2016 local arrangement website.


ADGA programme
9:30 am talk 1 Stephan Holzer: Recent Algorithms and Lower Bounds for Global Distributed Graph Problems
10:30 am coffee break
11:00 am talk 2 Richard Peng: Parallel Graph Algorithms
12:00 pm lunch break (lunches are provided)
1:30 pm talk 3 Qin Zhang: Communication Complexity for Distributed Graphs
2:30 pm talk 4 Ittai Abraham: A journey through compact routing
3:30 pm coffee break
4:00 pm talk 5 John Augustine: Robust and Efficient Computation in Dynamic Networks with Heavy Churn
5:00 pm talk 6 Leonid Barenboim: Distributed Symmetry-Breaking in Static and Dynamic Networks
6:00 pm Workshop ends
DISC programme
6:30 pm DISC Welcome Reception at the Zamanski Tour (on the UPMC campus).

Invited Speakers

[Stephan Holzer]
9:30 am

Stephan Holzer


Stephan Holzer is a postdoctoral associate at MIT’s Computer Science and Artificial Intelligence Laboratory. Before joining MIT he received his Ph.D. at ETH Zurich’s Electrical Engineering Department. He spent a year as a visiting fellow in Harvard’s Computer Science Department as a Hamburg Scholar and obtained his M.S. and B.S. in Mathematics in Germany’s first excellence program in Mathematics (TopMath) at TU Munich, where he received the student award and was a fellow of the Studienstiftung des deutschen Volkes. In 2016 he was selected to be one of the 36 members of the Young Academy of the Academy of Sciences and Literature | Mainz, Germany. His research focuses on distributed graph algorithms, on broadcast in wireless networks and on lower bounds for these scenarios.

Recent Algorithms and Lower Bounds for Global Distributed Graph Problems

The talk discusses several classical graph-problems such as computing all pairs shortest paths, and the related problem of computing the diameter in a distributed setting (CONGEST model). For the above mentioned problems, the talk will cover algorithms running in time O(n) in the unweighted case, as well as lower bounds derived from lower bounds on two-party communication complexity of set disjointness showing that this is essentially optimal. After extending these results to approximation algorithms and corresponding lower bounds, the talk will provide insights into lower bounds for distributed verification problems. That is, we study problems such as verifying that a subgraph H of a graph G is a minimum spanning tree. In the talk we will see that verifying a spanning tree can take much more time than actually computing a spanning tree of G. As an application of these results we derive strong unconditional time lower bounds on the hardness of distributed approximation for many classical optimization problems including minimum spanning tree, shortest paths, and minimum cut. Many of these results are the first non-trivial lower bounds for both exact and approximate distributed computation and they resolve previous open questions. Our result implies that there can be no distributed approximation algorithm for minimum spanning tree that is significantly faster than the current exact algorithm, for any approximation factor.

[Richard Peng]
11:00 am

Richard Peng

Georgia Tech

Richard Peng is an assistant professor in the school of computer science at the Georgia Institute of Technology. His main research interests are in the design, analysis, and implementation of efficient algorithms. Richard received his Ph.D. from Carnegie Mellon University in 2013 and was an instructor in applied math at the Massachusetts Institute of Technology until 2015. He was a Microsoft Research PhD Fellow and his thesis won the CMU SCS Distinguished Dissertation Award.

Parallel Graph Algorithms

Parallel algorithms study ways of speeding up sequential algorithms through concurrently computing on multiple processors. Theoretical parallel algorithms often focus on performing a small number of operations, but assume more generous models of communication.

Recent progresses led to parallel algorithms for many graph optimization problems that have proven to be difficult to parallelize. In this talk I will survey these new algorithmic frameworks and discuss some of their core routines: low diameter decompositions, random sampling, and iterative methods.

[Qin Zhang]
1:30 pm

Qin Zhang

Indiana University Bloomington

Qin Zhang is an assistant professor at the Indiana University Bloomington. He received a B.S. degree from Funda University and a Ph.D. from Hong Kong University of Science and Technology. He also spent a couple of years as a post-doc at the Theory Group of IBM Almaden Research Center, and the Center for Massive Data Algorithmics at Aarhus University. He is interested in algorithms for big data, in particular, data stream algorithms, sublinear algorithms, algorithms on distributed data; I/O-efficient algorithms, data structures, database algorithms and communication complexity.

Communication Complexity for Distributed Graphs

In this talk we will discuss the communication complexity of problems in distributed graphs, where we have k machines, each holding a subgraph and they want to jointly compute some function defined on the union of the k subgraphs. The communication is point-to-point, and the goal is to minimize the total communication between the k machines. This model captures all point-to-point distributed computational models with the clique topology in terms of communication complexity, including BSP and MapReduce.

In this talk I will introduce a few techniques developed in the last few years for proving multiparty point-to-point communication lower bounds, and then discuss how to use them for proving lower bounds for graph problems such as connectivity and maximum matching.

[Ittai Abraham]
2:30 pm

Ittai Abraham

VMware Research

Ittai is a Senior Researcher and founding member of the VMware Research Group. Prior to joining VMware, Ittai was a Researcher in Microsoft Research Silicon Valley (2008-2014). He holds a Phd in Computer Science from the Hebrew University.

A journey through compact routing

I will give an overview of a part of my research journey centered around compact routing. Progress in compact routing had a significant impact on several other research areas. In particular, compact routing has influenced problems in metric embeddings, real world route planning systems, dynamic graph algorithms, distributed systems and more! I will highlight how many of these problems are interrelated and how progress in one field sometime leads to improvements in others.

[John Augustine]
4:00 pm

John Augustine

IIT Madras

John Augustine is an Associate Professor in the Department of Computer Science and Engineering at IIT Madras. He received his Ph.D. in Computer Science from the University of California at Irvine in 2006. Prior to IIT Madras, he worked as a scientist at Tata Research Development and Design Centre and also as a Research Fellow at Nanyang Technological University. He has a wide array of research interests ranging from distributed network algorithms (esp., dynamic network algorithms), online algorithms, computational geometry, combinatorial optimization, and also applied algorithms, esp., in the context of inexact computing.

Robust and Efficient Computation in Dynamic Networks with Heavy Churn

Peer-to-Peer (P2P) networks — typically overlays on top of the Internet — pose some unique challenges to algorithm designers. The difficulty comes primarily from constant churn owing to the short life span of most nodes in the network. In order to maintain a well-connected overlay network despite churn at this level, the overlay must be dynamically maintained. This makes the overlay network graph an evolving graph that exhibits both edge dynamism and node churn. In this talk, we will discuss the somewhat surprising line of work in which we show how to design fast algorithms that are robust against heavy churn.

We will begin with a discussion on how to create an overlay network that has good expansion despite adversarial churn. Subsequently, assuming such an overlay network with good expansion, we will present a few basic techniques like fast information dissemination, random walks, and support estimation. Finally, we show how to use these techniques to design algorithms to solve fundamental problems like agreement, leader election, storing and retrieving data items.

[Leonid Barenboim]
5:00 pm

Leonid Barenboim

Open University of Israel

Leonid Barenboim is a Senior Lecturer at the Open University of Israel. He obtained his Ph.D. in Computer Science from Ben-Gurion University of the Negev. He was a post-doctoral fellow in the joint program of the Simons Institute at UC Berkeley and I-CORE center at the Weizmann Institute of Science. His research interests include computer networks, distributed algorithms, dynamic algorithms, sublinear algorithms and big data. Papers he (co-)authored won best paper awards in PODC 2010 and 2015, and best student paper awards in PODC 2011 and ICALP 2012. His dissertation won the Principles of Distributed Computing Dissertation Award in 2015. He also coauthored (together with his Ph.D. adviser Prof. Michael Elkin) a monograph on Distributed Graph Coloring.

Distributed Symmetry-Breaking in Static and Dynamic Networks

In the distributed message passing model a communication network is represented by a graph whose vertices host processors that communicate over the edges. Computation proceeds in rounds of local computations and message exchange between neighbors. Our goal is solving graph-theoretic tasks (vertex-coloring, maximal matching, maximal independent set, etc.), where the network graph is the input. The input is provided in a distributed manner, i.e., initially each vertex knows only its neighbors. Eventually, the vertices output their parts in the solution, and the union of these answers constitutes a proper solution for the entire graph. The running time is the number of rounds required for all vertices to output their answers.

Although some networks remain the same throughout the entire execution, other networks are very dynamic and may change significantly. This is the case in wireless ad-hoc networks, social networks, mobile networks and many other networks. In these networks new vertices may join and connect to existing ones, old vertices may crash, and connections between vertices may appear and disappear as a result of movement of vertices, channel failures, etc. Consequently, distributed algorithms must handle not only static networks, but also the ones that change rapidly. In the latter scenario, even when a correct solution has been computed, the network may change, and a correction to the solution may be required. In this case, the number of rounds required for correcting the solution after a topology change is the dynamic running time.

While distributed symmetry breaking has been studied for decades, researchers were able to overcome some complexity barriers only recently. This progress has been achieved thanks to the discovery of novel directions for coloring, maximal independent set, and related symmetry breaking problems. I will survey some classical results in this area and proceed with recent advances that allow for significant improvements in both the static and dynamic settings. I will illustrate how the dynamic setting borrows ideas from the static one, and how it pays back.