Homepage
Christoph Lenzen
Theory of Distributed and Embedded Systems
Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Campus E1 4, Room 314
66123 Saarbrücken
Germany
Email: clenzen@mpi-inf.mpg.de
Phone: +49 681 9325 1008
Fax: +49 681 9325 199
This page is no longer maintained. My new homepage is here.
In protest to Elsevier's policies, I stepped down from my role as editor of TCS.
I'm a faculty member at CISPA since July 2021.
The new contact person for BHons students from TU Vienna planning to do an internship at MPII is Dr. Andreas Karrenbauer. Further details.
For other internships at D1, please refer to this information.
Theory of Distributed Computing, in particular clock synchronization, randomized load balancing, routing, graph problems (e.g. dominating sets, maximal independent sets, coloring), fault-tolerance, and algorithms in hardware. Here's a poster about a recent result.
July 2021 - present: faculty member at CISPA.
2021: ERC proof-of-concept grant "Fast Response Circuits for Voltage Droop Compensation" aiming at commercialisation of results from the ERC starting grant.
2017 - 2022: ERC starting grant project "A Theory of Reliable Hardware."
July 2014 - June 2021: Group Leader at MPI for Informatics.
2013 - June 2014: Postdoctoral fellow at MIT CSAIL, with Nancy Lynch.
2012: Postdoctoral fellow in the Department of Computer Science and Applied Mathematics,
Weizmann Institute of Science, with David Peleg.
2011: Postdoctoral fellow in the Department of Computer Science and
Engineering, Hebrew University of Jerusalem, with Danny Dolev.
2011: Ph.D. degree from ETH Zurich. Thesis:
Synchronization and Symmetry Breaking in Distributed Systems.
2007 - 2010: Graduate studies, Distributed Computing Group, ETH Zurich.
My advisor was Roger Wattenhofer.
2007: Diploma Degree in Mathematics, University of Bonn.
winter 2022/23: Clock Synchronization and Adversarial Fault Tolerance
summer 2022: How To Clock Your Computer
winter 2021/22: Metastability-containing Synchronization Circuits
summer 2021: Clock Synchronization and Adversarial Fault Tolerance
winter 2020/21: How To Clock Your Computer
winter 2020/21: Theory of Distributed Systems
winter 2019/20: Theory of Distributed Systems
summer 2019: Keeping Time in Distributed Systems
winter 2018/19: Theory of Distributed Systems
summer 2018: Keeping Time in Distributed Systems
winter 2017/18: Theory of Distributed Systems
winter 2016/17: Theory of Distributed Systems
winter 2015/16: Theory of Distributed Systems
winter 2014/15: Theory of Distributed Systems
- Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts
Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic, and Themis Gouleakis.
Symposium on Distributed Computing (DISC), October 2022.
arxiv (full version)
- G-SINC: Global Synchronization Infrastructure for Network Clocks
Marc Frei, Jonghoon Kwon, Seyedali Tabaeiaghdaei, Marc Wyss, Christoph Lenzen, and Adrian Perrig.
Symposium on Reliable Distributed Systems (SRDS), September 2022.
- A Recursive Early-Stopping Phase King Protocol
Christoph Lenzen and Sahar Sheikholeslami.
Symposium on Principles of Distributed Computing (PODC), July 2022.
- Optimal Clock Synchronization with Signatures
Christoph Lenzen and Julian Loss.
Symposium on Principles of Distributed Computing (PODC), July 2022.
- On Specifications and Proofs of Timed Circuits
Matthias Fuegger, Christoph Lenzen, and Ulrich Schmid.
Thomas Henzinger Festschrift - Conference celebrating his 60th birthday, 2022.
- Small Hazard-Free Transducers
Johannes Bund, Christoph Lenzen, and Moti Medina.
Innovations in Theoretical Computer Science (ITCS), January 2022.
arxiv (full version)
- Fast All-Digital Clock Frequency Adaptation Circuit for Voltage Droop Tolerance
Matthias Fuegger, Attila Kinali, Christoph Lenzen, and Ben Wiederhake.
Transactions on Computer-Aided Design of Integrated Circuits and Systems, July 2021.
- Approximate Minimum Directed Spanning Trees under Congestion
Christoph Lenzen and Hossein Vahidi.
28th Colloquium on Structural Information and Communication Complexity (SIROCCO), June 2021.
preprint
- Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
Ruben Becker, Sebastian Forster, Andreas Karrenbauer, and Christoph Lenzen.
SIAM Journal on Computing, May 2021.
arxiv
- A Breezing Proof of the KMW Bound
Corinna Coupette and Christoph Lenzen.
Symposium on Simplicity in Algorithms (SOSA), January 2021.
arxiv (full version)
- Brief Announcement: TRIX: Low-Skew Pulse Propagation for Fault-Tolerant Hardware
Christoph Lenzen and Ben Wiederhake.
Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), November 2020.
arxiv (full version)
- PALS: Plesiochronous and Locally Synchronous Systems
Johannes Bund, Matthias Fuegger, Christoph Lenzen, Moti Medina, and Will Rosenbaum.
26th Symposium on Asynchronous Circuits and Systems (ASYNC), May 2020.
arxiv (full version)
- Synchronizer-free Digital Link Controller
Johannes Bund, Matthias Fuegger, Christoph Lenzen, and Moti Medina.
Transactions on Circuits and Systems I, May 2020.
- Fooling views: a new lower bound technique for distributed computations under congestion
Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Christoph Lenzen.
Distributed Computing, April 2020.
arxiv
- Low Diameter Graph Decompositions by Approximate Distance Computation
Ruben Becker, Yuval Emek, and Christoph Lenzen.
11th Conference on Innovations in Theoretical Computer Science (ITCS), January 2020.
preprint
- Distributed Algorithms for Low Stretch Spanning Trees
Ruben Becker, Yuval Emek, Mohsen Ghaffari, and Christoph Lenzen.
33rd Symposium on Distributed Computing (DISC), October 2019.
preprint
- Optimal Metastability-Containing Sorting via Parallel Prefix Computation
Johannes Bund, Christoph Lenzen, and Moti Medina.
Transactions on Computers, October 2019.
preprint (full version with proofs)
- Self-stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus
Christoph Lenzen and Joel Rybicki.
Journal of the ACM, August 2019.
preprint
- On the complexity of hazard-free circuits
Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, and Karteek Sreenivasaiah.
Journal of the ACM, August 2019.
preprint
- Fault Tolerant Gradient Clock Synchronization
Johannes Bund, Christoph Lenzen, and Will Rosenbaum.
38th Symposium on Principles of Distributed Computing (PODC), July 2019.
arxiv
- Locality of not-so-weak coloring
Alkida Balliu, Juho Hirvonen, Christoph Lenzen, Dennis Olivetti, and Jukka Suomela.
26th Colloquium on Structural Information and Communication Complexity (SIROCCO), July 2019.
arxiv
- Parallel Balanced Allocations: The Heavily Loaded Case
Christoph Lenzen, Merav Parter, and Eylon Yogev.
31st Symposium on Parallelism in Algorithms and Architectures (SPAA), June 2019.
preprint
- Near-Optimal Distributed Maximum Flow
Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, and Boaz Patt-Shamir.
SIAM Journal on Computing, November 2018.
- Near-Optimal Self-Stabilising Counting and Firing Squads
Christoph Lenzen and Joel Rybicki.
Distributed Computing, September 2018.
- Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford
Stephan Friedrichs and Christoph Lenzen.
Journal of the ACM, August 2018.
- A Local Algorithm for the Sparse Spanning Graph Problem
Christoph Lenzen and Reut Levi.
45th Colloquium on Automata, Languages, and Programming (ICALP), July 2018.
arxiv
- On the complexity of hazard-free circuits
Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, and Karteek Sreenivasaiah.
50th Symposium on the Theory of Computing (STOC), June 2018.
arxiv
- Fast All-Digital Clock Frequency Adaptation Circuit for Voltage Droop Tolerance
Matthias Fuegger, Attila Kinali, Christoph Lenzen, and Ben Wiederhake.
Symposium on Asynchronous Circuits and Systems (ASYNC), May 2018.
preprint
- Optimal Metastability-Containing Sorting Networks
Johannes Bund, Christoph Lenzen, and Moti Medina.
Design, Automation and Test in Europe (DATE), March 2018.
arxiv
- Metastability-Containing Circuits
Stephan Friedrichs, Matthias Fuegger, and Christoph Lenzen.
IEEE Transactions on Computers, March 2018.
- Distributed Distance Computation and Routing with Small Messages
Christoph Lenzen, Boaz Patt-Shamir, and David Peleg.
Distributed Computing, February 2018.
- Self-stabilizing Byzantine Clock Synchronization with Optimal Precision
Pankaj Khanchandani and Christoph Lenzen.
Theory of Computing Systems, January 2018.
preprint
- Robust Routing Made Easy
Christoph Lenzen and Moti Medina.
19th Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), November 2017.
arxiv
- Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen.
31st Symposium on Distributed Computing (DISC), October 2017.
arxiv
- Self-stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus
Christoph Lenzen and Joel Rybicki.
31st Symposium on Distributed Computing (DISC), October 2017.
arxiv
- Efficient Counting with Optimal Resilience
Christoph Lenzen, Joel Rybicki, and Jukka Suomela.
SIAM Journal on Computing, 46(4):1473-1500, August 2017.
preprint
- Searching without Communicating: Tradeoffs Between Performance and Selection Complexity
Christoph Lenzen, Nancy Lynch, Calvin Newport, and Tsvetomira Radeva.
Distributed Computing, 30(3):169-191, June 2017.
preprint
- Metastability-Aware Memory-Efficient Time-to-Digital Converters
Matthias Fuegger, Attila Kinali, Christoph Lenzen, and Thomas Polzer.
Symposium on Asynchronous Circuits and Systems (ASYNC), May 2017.
- Metastability Tolerant Computing
Ghaith Tarawneh, Matthias Fuegger, and Christoph Lenzen.
Symposium on Asynchronous Circuits and Systems (ASYNC), May 2017.
- Near-Optimal Metastability-Containing Sorting Networks
Johannes Bund, Christoph Lenzen, and Moti Medina.
Design, Automation and Test in Europe (DATE), March 2017.
- Self-stabilizing Byzantine Clock Synchronization with Optimal Precision
Pankaj Khanchandani and Christoph Lenzen.
Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), November 2016.
arxiv
- Near-Optimal Self-Stabilising Counting and Firing Squads
Christoph Lenzen and Joel Rybicki.
Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), November 2016.
arxiv
- Algebraic Methods in the Congested Clique
Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela.
Distributed Computing, March 2016.
preprint
- HEX: Scaling Honeycombs is Easier than Scaling Clock Trees
Danny Dolev, Matthias Fuegger, Christoph Lenzen, Martin Perner, and Ulrich Schmid.
Journal of Computer and System Sciences, 82(5):929-956, August 2016.
preprint
- Fault-tolerant Clock Synchronization with High Precision
Attila Kinali, Florian Huemer, and Christoph Lenzen.
Symposium on VLSI (ISVLSI), July 2016.
preprint
- Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford
Stephan Friedrichs and Christoph Lenzen.
25th Symposium on Parallelism in Algorithms and Architectures (SPAA), July 2016.
arxiv
- Efficient Metastability-Containing Gray Code 2-Sort
Christoph Lenzen and Moti Medina.
22nd Symposium on Asynchronous Circuits and Systems (ASYNC), May 2016.
preprint
- Tight Bounds for Parallel Randomized Load Balancing
Christoph Lenzen and Roger Wattenhofer.
Distributed Computing, 29(2):127-142, April 2016.
preprint
- Synchronous Counting and Computational Algorithm Design
Danny Dolev, Keijo Heljanko, Matti Järvisalo, Janne H. Korhonen, Christoph Lenzen, Joel Rybicki, Jukka Suomela, and Siert Wieringa.
Journal of Computer and System Sciences, 82(2):310-332, March 2016.
preprint
- Efficient counting with optimal resilience
Christoph Lenzen and Joel Rybicki.
29th Symposium on Distributed Computing (DISC), October 2015.
arxiv
- 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 | arxiv
- 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 | arxiv
- Fast Partial Distance Estimation and Applications
Christoph Lenzen and Boaz Patt-Shamir.
34th Symposium on Principles of Distributed Computing (PODC), July 2015.
preprint | arxiv
- Towards Optimal Synchronous Counting
Christoph Lenzen, Joel Rybicki, and Jukka Suomela.
34th Symposium on Principles of Distributed Computing (PODC), July 2015.
preprint | arxiv
- Fault-tolerant Distributed Systems in Hardware
Danny Dolev, Matthias Fuegger, Christoph Lenzen, Ulrich Schmid, and Andreas Steininger. (Invited article)
EATCS Bulletin 116, June 2015.
- PulseSync: An Efficient and Scalable Clock Synchronization Protocol
Christoph Lenzen, Philipp Sommer, and Roger Wattenhofer.
Transactions on Networking, 23(3):717-727, June 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
- Near-Optimal Distributed Tree Embedding
Mohsen Ghaffari and Christoph Lenzen.
28th Symposium on Distributed Computing (DISC), October 2014.
preprint
- Brief Announcement: The 1-2-3 Toolkit for Building your own Balls-into-Bins Algorithm
Pierre Bertrand and Christoph Lenzen.
28th Symposium on Distributed Computing (DISC), October 2014.
preprint | sources
- 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
- Trade-offs between Selection Complexity and Performance
when Searching the Plane without Communication
Christoph Lenzen, Nancy Lynch, Calvin Newport, and Tsvetomira Radeva.
33rd Symposium on Principles of Distributed Computing (PODC), July 2014.
arxiv
- Brief Announcement: Local Approximability of Minimum Dominating Set on Planar Graphs
Miikka Hilke, Christoph Lenzen, and Jukka Suomela
33rd Symposium on Principles of Distributed Computing (PODC), July 2014.
- 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.
- Synchronous Counting and Computational Algorithm Design
Danny Dolev, Janne H. Korhonen, Christoph Lenzen, Joel Rybicki, and Jukka Suomela.
15th Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), November 2013.
- The Power of Pheromones in Ant Foraging
Christoph Lenzen and Tsvetomira Radeva.
1st Workshop on Biological Distributed Algorithms (BDA), October 2013.
- Efficient Construction of Global Time in SoCs despite Arbitrary Faults
Matthias Fuegger, Markus Hofstaetter, Christoph Lenzen, and Ulrich Schmid.
16th Conference on Digital System Design (DSD), September 2013.
- Byzantine Self-Stabilizing Clock Distribution with HEX: Implementation, Simulation, Clock Multiplication
Christoph Lenzen, Martin Perner, Martin Sigl, and Ulrich Schmid .
6th Conference on Dependability (DEPEND), August 2013.
- 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.
- Efficient Distributed Source Detection with Limited Bandwidth
Christoph Lenzen and David Peleg.
32nd Symposium on Principles of Distributed Computing (PODC), July 2013.
- Early-Deciding Consensus is Expensive
Danny Dolev and Christoph Lenzen.
32nd Symposium on Principles of Distributed Computing (PODC), July 2013.
- Optimal Deterministic Routing and Sorting on the Congested Clique
Christoph Lenzen.
32nd Symposium on Principles of Distributed Computing (PODC), 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
- "Tri, Tri again": Finding Triangles and Small Subgraphs in a Distributed Setting
Danny Dolev, Christoph Lenzen, and Shir Peled.
26th Symposium on Distributed Computing (DISC), October 2012.
arxiv
- Distributed Algorithms for Sensor Networks
Christoph Lenzen and Roger Wattenhofer. (Invited article)
Philosophical Transactions of the Royal Society A, 370(1958), January 2012.
preprint
- Coupling Molecular Dynamics and Continua with Weak Constraints
Konstantin Fackeldey, Dorian Krause, Rolf Krause, and Christoph Lenzen.
SIAM Journal on Multiscale Modeling and Simulation, 9(4), November 2011.
preprint
- Fault-tolerant Algorithms for
Tick-generation in Asynchronous Logic: Robust Pulse Generation
Danny Dolev, Matthias Fuegger, Christoph Lenzen, and Ulrich Schmid.
13th Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), October 2011.
arxiv
- Tight Bounds for Parallel Randomized Load Balancing
Christoph Lenzen and Roger Wattenhofer.
43rd Symposium on Theory of Computing (STOC), June 2011.
arxiv
- MIS on Trees
Christoph Lenzen and Roger Wattenhofer.
30th Symposium on Principles of Distributed Computing (PODC), June 2011.
- Synchronization and Symmetry Breaking in Distributed Systems
Christoph Lenzen. (ETH medal for outstanding thesis)
Diss. ETH No. 19459, Ph.D. thesis, ETH Zurich, January 2011.
- Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
Christoph Lenzen and Roger Wattenhofer.
24th Symposium on Distributed Computing (DISC), September 2010.
- Optimal Gradient Clock Synchronization in Dynamic Networks
Fabian Kuhn, Christoph Lenzen, Thomas Locher, and Rotem Oshman. (Best Paper Session)
29th Symposium on Principles of Distributed Computing (PODC), July 2010.
technical report
- Brief Announcement: Exponential Speed-Up of Local Algorithms using Non-Local Communication
Christoph Lenzen and Roger Wattenhofer.
29th Symposium on Principles of Distributed Computing (PODC), July 2010.
- Clock Synchronization: Open Problems in Theory and Practice
Christoph Lenzen, Thomas Locher, Philipp Sommer, and Roger Wattenhofer. (Invited paper)
36th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), January 2010.
- Tight Bounds for Clock Synchronization
Christoph Lenzen, Thomas Locher, and Roger Wattenhofer.
Journal of the ACM, Volume 57, Number 2, January 2010.
- Local Algorithms: Self-Stabilization on Speed
Christoph Lenzen, Jukka Suomela, and Roger Wattenhofer. (Invited paper)
11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), November 2009.
- Optimal Clock Synchronization in Networks
Christoph Lenzen, Philipp Sommer, and Roger Wattenhofer.
7th ACM Conference on Embedded Networked Sensor Systems (SenSys), November 2009.
- Tight Bounds for Clock Synchronization
Christoph Lenzen, Thomas Locher, and Roger Wattenhofer. (Best Paper Award)
28th ACM Symposium on Principles of Distributed Computing (PODC), August 2009.
technical report
- Clock Synchronization with Bounded Global and Local Skew
Christoph Lenzen, Thomas Locher, and Roger Wattenhofer.
49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), October 2008.
technical report
- Leveraging Linial's Locality Limit
Christoph Lenzen and Roger Wattenhofer.
22nd International Symposium on Distributed Computing (DISC), September 2008.
- What Can Be Approximated Locally? Case Study: Dominating Sets in Planar Graphs
Christoph Lenzen, Yvonne-Anne Pignolet, and Roger Wattenhofer.
22nd Symposium on Parallelism in Algorithms and Architectures (SPAA), June 2008.
technical report
