ADGA is a one-day workshop that focuses on the theoretical foundations of distributed graph algorithms. The programme consists of five invited talks, which are aimed at the general DISC audience.
ADGA 2013 was held on Monday, 14 October 2013 in Jerusalem, and it was co-located with DISC 2013. The workshop was chaired by Jukka Suomela.
For information on past and future ADGA workshops, see the web site of the ADGA workshop series.
Schedule
ADGA programme | ||
---|---|---|
8:30am | talk 1 | Christoph Lenzen: Distributed Algorithms on a Congested Clique |
9:30am | talk 2 | Rotem Oshman: Communication Complexity and Graph Algorithms |
10:30am | coffee | |
11:00am | talk 3 | Michael Elkin: Distributed Algorithms for Graph Coloring |
12:00pm | talk 4 | Thomas Sauerwald: Distributed Load Balancing on Graphs |
1:00pm | lunch | |
2:30pm | talk 5 | Danny Dolev: Distributed Graph Algorithms and Very Large Scale Integrated Circuits |
3:30pm | workshop ends | |
DISC programme | ||
4:00pm | Teemu Koponen: The Evolution of SDN and How Your Network Is Changing | |
6:00pm | Uri Alon: Love and Fear in the Lab | |
6:30pm | DISC Welcome Reception |
The regular paper presentations of DISC 2013 will be held on 15–17 October, and there will be more workshops on 17–18 October.
Presentation Slides
Christoph Lenzen, Distributed Algorithms on a Congested Clique: PPTX, PPT, PDF
Rotem Oshman, Communication Complexity and Graph Algorithms: PPTX
Michael Elkin, Distributed Algorithms for Graph Coloring: PDF
Thomas Sauerwald, Distributed Load Balancing on Graphs: PDF
Danny Dolev, Distributed Graph Algorithms and Very Large Scale Integrated Circuits: PDF
Invited Speakers
MIT
Christoph Lenzen defended his Ph.D. thesis, which was advised by Roger Wattenhofer, at ETH Zurich in January 2011. In 2011 and 2012 he was a postdoc with Danny Dolev (Hebrew University of Jerusalem) and David Peleg (Weizmann Institute of Science), respectively. Currently he is a postdoctaral fellow at MIT CSAIL, in the group of Nancy Lynch.
Distributed Algorithms on a Congested Clique
Algorithms for distributed systems are frequently devised and analyzed in either the LOCAL or the CONGEST model. In both settings, the distributed system is modelled as a graph, where nodes perform arbitrary computations in synchronous rounds and, in each round, exchange messages along the edges. In the LOCAL model, messages may be of arbitrary size, meaning that an r-round algorithm can be interpreted as a function mapping the topology and inputs of a node’s r-neighborhood to the node’s share of the algorithm’s output. In the CONGEST model, message size is restricted, typically to a polylogarithmic number of bits in terms of the input size, restricting algorithms further. Usually, the problem specification is fused to the topology of the communication graph, e.g., one might want to find a maximal independent set or matching of the graph.
In this talk, I will discuss a different setup: in each round, each node can send a (different) message of logarithmic size to each other node. This enables to obtain information from distant parts of an input graph quickly, and there is no communication “bottleneck” imposing potentially unreasonable restrictions on communication. This removes the main obstacles of the LOCAL and CONGEST model that give rise to lower bounds, yet in many cases it is non-trivial to devise very fast algorithms. I will motivate the study of this model, illustrate it by some examples, summarize the state of the art, and present a number of open problems in the area.
Presentation slides: PPTX, PPT, PDF
Further information:
- Zvi Lotker et al. (2006): Distributed MST for constant diameter graphs (free version)
- Atish Das Sarma et al. (2012): Distributed verification and hardness of approximation (free version, arXiv)
- Christoph Lenzen (2013): Optimal deterministic routing and sorting on the congested clique (free version, arXiv)
Tel Aviv University
Rotem Oshman is currently a post-doc at the Center for Computational Intractability in Princeton University. She completed her PhD at MIT in 2012, under the supervision of Prof. Nancy Lynch, and was a post-doc in the theory group at the University of Toronto. She will be a senior lecturer at Tel Aviv University starting in September 2014.
Communication Complexity and Graph Algorithms
In this talk I will describe recent advances in communication complexity, which have led for the first time to strong lower bounds on multi-party computation with private channels. These new bounds and techniques hold out the hope of proving lower bounds on distributed graph problems that were previously not approachable, as well as analyzing models for which no good lower bounds currently exist, such as the congested clique model.
I will show a recent lower bound on multi-party set disjointness (to appear in FOCS’13), which was proven using information theory. To prove the lower bound, we prove a direct sum theorem, which shows that the cost of the problem is at least the sum of the costs of many sub-problems; namely, we are able to formally prove that if one wants to check if k sets intersect, then one has to essentially go over each coordinate and check whether that coordinate is in the intersection. The same principle seems likely to apply to distributed testing of graph properties. The set disjointness lower bound yields some distributed lower bounds, and I will conclude by discussing open problems and exciting directions to extend these results.
Presentation slides: PPTX
Further information:
- Mark Braverman et al. (2013): Tight bounds for set disjointness in the message passing model
- David P. Woodruff & Qin Zhang (2013): When distributed computation is communication expensive (arXiv)
Ben-Gurion University
Michael Elkin finished his B.Sc. in Computer Science and Mathematics in Hebrew University in 1995. He graduated with Ph.D. in Computer Science from Weizmann Institute in 2002. Then he spent two years of postdoc in the Institute for Advanced Study in Princeton and in Yale. Starting from 2004 he is a faculty member in the Computer Science department in the Ben-Gurion University. Michael Elkin works mainly on distributed algorithms for the message-passing model of computation, and on problems of building spanners and metric spanning trees.
Distributed Algorithms for Graph Coloring
Suppose that every vertex of an n-vertex graph G = (V, E) of maximum degree Δ hosts a processor. These processors wake up simultaneously and communicate in discrete rounds. In each round each vertex is allowed to send an arbitrarily large message to all its neighbors. We are interested in coloring this graph with a relatively few colors within a small number of rounds. At the end of the algorithm each vertex needs to know its own color. This problem is closely related to problems of computing a maximal independent set and a maximal matching in the distributed setting.
In this talk I plan to overview the rich history of the research on these problems, to mention the most important known results, and describe some of the basic techniques which are used to achieve them. Then I will turn to my own recent work on both deterministic (joint with Barenboim, JACM’11) and randomized (joint with Barenboim, Pettie and Schneider, FOCS’12) variants of these problems. Specifically, I will show an outline of the deterministic Δ^{1+ε}-coloring algorithm that requires polylogarithmic in n number of rounds. (Here ε > 0 is an arbitrarily small constant.) This result solves an open problem posed by Linial in 1987. If time permits I will also show an outline of a randomized (Δ + 1)-coloring algorithm that requires O(log Δ) + exp(O((log log n)^{1/2})) number of rounds.
There is a huge number of open problems in this area. During the talk I will present and discuss some of them.
Presentation slides: PDF
Further information:
- Leonid Barenboim & Michael Elkin (2013): Distributed Graph Coloring: Fundamentals and Recent Developments (draft)
- Nathan Linial (1992): Locality in distributed graph algorithms (free version)
- David Peleg (2000): Distributed Computing: A Locality-Sensitive Approach (Google)
- Fabian Kuhn et al. (2004): What cannot be computed locally! (free version)
- Kishore Kothapalli & Sriram Pemmaraju (2011): Distributed graph coloring in a few rounds (free version)
University of Cambridge
Thomas Sauerwald is a lecturer in the Computer Laboratory at the University of Cambridge. He obtained his PhD in computer science from the University of Paderborn in 2008. After that, he has held positions at the International Computer Science Institute, Simon Fraser University and Max Planck Institute for Informatics. His main research area are randomized and distributed algorithms.
Distributed Load Balancing on Graphs
Load Balancing is a crucial ingredient for the efficient utilization of shared resources. As we are at the end of an era of increasing individual processor power, more and more computations are performed on decentralized networks.
In one of the standard models of load balancing, processors are represented by nodes of a graph, while links are represented by edges. The objective is to balance the load by allowing vertices to exchange loads with their direct neighbors. In this talk we are interested in minimizing the discrepancy of the load, that is, the difference between the maximum loaded and minimum loaded processor.
In the first part we discuss several aspects of our model, including the relation between Markov chains and iterative load balancing algorithms under the assumption that load is arbitrarily divisible. The second (and main) part of this talk covers a more realistic setting with unsplittable jobs and analyzes a natural randomized rounding-based strategy. We analyze this strategy for hypercubes first and then turn to the general setting of arbitrary graphs.
Presentation slides: PDF
Further information:
- Thomas Sauerwald & He Sun (2012): Tight bounds for randomized load balancing on arbitrary network topologies (arXiv)
The Hebrew University of Jerusalem
Danny Dolev (SM’89) received his B.Sc. degree in mathematics and physics from the Hebrew University, Jerusalem in 1971; M.Sc. in Applied Mathematics at the Weizmann Institute of Science, Israel, in 1973; and Ph.D. on Synchronization of Parallel Processors in 1979, also at the Weizmann Institute of Science, Israel. He was a Post-Doctoral fellow at Stanford University, 1979–1981, and IBM Research Fellow 1981–1982. He joined the Hebrew University in 1982. From 1987 to 1993 he held a joint appointment as a professor at the Hebrew University and as a research staff member at the IBM Almaden Research Center. He is currently a professor at the Hebrew University of Jerusalem. His research interests cover all aspects of distributed computing, fault tolerance, security and networking — theory and practice.
Distributed Graph Algorithms and Very Large Scale Integrated Circuits
We argue that grid structures are a very promising alternative to the standard approach for distributing a clock signal throughout VLSI circuits and other hardware devices. Traditionally, this is accomplished by a delay-balanced clock tree, which distributes the signal supplied by a single clock source via carefully engineered and buffered signal paths.
Our approach, termed HEX, is based on a hexagonal grid with simple intermediate nodes, which both control the forwarding of clock ticks in the grid and supply them to nearby functional units. HEX is Byzantine fault-tolerant, in a way that scales with the grid size, self-stabilizing, and seamlessly integrates with multiple synchronized clock sources, as used in multi-synchronous Globally Synchronous Locally Asynchronous (GALS) architectures. Moreover, HEX guarantees a small clock skew between neighbors even for wire delays that are only moderately balanced. We provide both a theoretical analysis of the worst-case skew and simulation results that demonstrate very small typical skew in realistic runs.
(Coauthored by Danny Dolev, Matthias Függer, Christoph Lenzen, Martin Perner, and Ulrich Schmid.)
Presentation slides: PDF
Further information:
- Danny Dolev et al. (2013): HEX: scaling honeycombs is easier than scaling clock trees (free version)
Registration
Please follow the instructions in the DISC 2013 registration system. ADGA and other satellite workshops are included in the DISC 2013 registration fee. There is also a workshop-only option in the registration system.
The early registration deadline for DISC is 9 September 2013. You can use the DISC 2013 registration system to book your accommodation. For further information on the conference venue and practicalities, please refer to the DISC 2013 web site.
Past
ADGA 2012 was co-located with DISC 2012 (Salvador, Brazil, October 2012). The workshop was chaired by Amos Korman.