Theory of Distributed Systems
Broadly speaking, distributed computing concerns systems that consist of multiple agents that act based on local information. The main challenge is typically how agents gain access to sufficient information to collaboratively solve a task quickly, despite limits on communication, faults, or inaccurate data.
People
Coordinator
Researchers
Research Area
We are interested in all aspects of distributed computing, but the following are the topics we currently focus on.
- Graph Algorithms:
Naturally, well-known graph structures like dominating sets, colorings, minimum spanning trees, matchings, etc. are of great utility in distributed systems, too. We tackle these problems with all available means: randomization, approximation, decomposition, and so on. The key differences to centralized algorithms are that each node can perform its own computations, initially is aware of its neighborhood in the graph only, and needs to learn its local share of the output only (e.g., whether it is in the dominating set or not). To this end, nodes communicate over the edges of the graph; this communication is the main cost factor.
- Fault-Tolerance:
The nodes of a distributed system can be used to solve tasks redundantly, permitting to limit the effets of faults on the system as a whole. A second aspect is that faults are not necessarily permanent, implying that individual nodes or an entire system can recover from corrupted memory states that result from transient faults. We study fault-tolerance in distributed systems, examining to what extent it can be prevented that faulty nodes corrupt the state of other nodes, under what circumstances it is possible to recover from transients and how fast, and how costly respective algorithms are with respect to communication and time complexity.
- Design of Reliable Hardware:
Today's Very Large Scale Integrated (VLSI) circuits operate on such small length and time scales that they become distributed systems in their own right. Small subcircuits take the role of nodes that communicate via wires - the "edges" of the communication graph - and billions of individual components render fault-tolerance mission-critical. Hence, insights from both of the above domains are useful for designing reliable hardware. However, VLSI circuits add unique challenges. In low-level hardware, even simple computations like an addition require substantial effort, and violation of timing constraints may induce so-called metastability, states of the logic that lie outside the abstraction of binary logic. We seek to adapt the algorithmic ideas from above areas to this environment, with the goal of devising hardware with strong, provable fault-tolerance properties.
Sample Publications
- Near-Optimal Distributed Maximum Flow
Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, and Boaz Patt-Shamir.
34th Symposium on Principles of Distributed Computing (PODC), July 2015.
preprint
- Algebraic Methods in the Congested Clique
Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela.
34th Symposium on Principles of Distributed Computing (PODC), July 2015.
preprint
- Fast Partial Distance Estimation and Applications
Christoph Lenzen and Boaz Patt-Shamir.
34th Symposium on Principles of Distributed Computing (PODC), July 2015.
preprint
- Towards Optimal Synchronous Counting
Christoph Lenzen, Joel Rybicki, and Jukka Suomela.
34th Symposium on Principles of Distributed Computing (PODC), July 2015.
preprint
- The 1-2-3 Toolkit for Building your own Balls-into-Bins Algorithm
Pierre Bertrand and Christoph Lenzen.
Meeting on Algorithm Engineering and Experiments (ALENEX), January 2015.
preprint | sources - Tight Bounds for Parallel Randomized Load Balancing
Christoph Lenzen and Roger Wattenhofer.
Distributed Computing, to appear.
preprint - Fault-tolerant Algorithms for Tick-generation in Asynchronous Logic: Robust Pulse Generation
Danny Dolev, Matthias Fuegger, Christoph Lenzen, and Ulrich Schmid.
Journal of the ACM, 61(5):860-900, August 2014.
preprint - Improved Distributed Steiner Forest Construction
Christoph Lenzen and Boaz Patt-Shamir.
33rd Symposium on Principles of Distributed Computing (PODC), July 2014.
arxiv - PulseSync: An Efficient and Scalable Clock Synchronization Protocol
Christoph Lenzen, Philipp Sommer, and Roger Wattenhofer.
Transactions on Networking, to appear.
preprint - Rigorously Modeling Self-Stabilizing Fault-Tolerant Circuits: An Ultra-Robust Clocking Scheme for Systems-on-Chip
Danny Dolev, Matthias Fuegger, Christoph Lenzen, Markus Posch, Ulrich Schmid, and Andreas Steininger.
Journal of Computer and System Sciences, 80(4):30, January 2014.
- HEX: Scaling Honeycombs is Easier than Scaling Clock Trees
Danny Dolev, Matthias Fuegger, Christoph Lenzen, Martin Perner, and Ulrich Schmid.
25th Symposium on Parallelism in Algorithms and Architectures (SPAA), July 2013. - Fast Routing Table Construction Using Small Messages
Christoph Lenzen and Boaz Patt-Shamir.
45th Symposium on the Theory of Computing (STOC), June 2013.
arxiv
- Distributed Minimum Dominating Set Approximations in Restricted Families of Graphs
Christoph Lenzen, Yvonne-Anne Pignolet, and Roger Wattenhofer.
Distributed Computing, 26(2):119-137, April 2013.
preprint - Tight Bounds for Clock Synchronization
Christoph Lenzen, Thomas Locher, and Roger Wattenhofer.
Journal of the ACM, Volume 57, Number 2, January 2010.