92 citations · 220 across the 35 of their papers we have counts for
36 papers · 1 filter
Robust Routing Made Easy: Reinforcing Networks Against Non-Benign Faults
Christoph Lenzen, Moti Medina, Mehrdad Saberi +1
With the increasing scale of communication networks, the likelihood of failures grows as well. Since these networks form a critical backbone of our digital society, it is important…
On Specifications and Proofs of Timed Circuits
Matthias Fuegger, Christoph Lenzen, Ulrich Schmid
Given a discrete-state continuous-time reactive system, like a digital circuit, the classical approach is to first model it as a state transition system and then prove its properti…
Optimal Clock Synchronization with Signatures
Christoph Lenzen, Julian Loss
Cryptographic signatures can be used to increase the resilience of distributed systems against adversarial attacks, by increasing the number of faulty parties that can be tolerated…
Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts
Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler +2
In this paper, we refine the (almost) \emph{existentially optimal} distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS `21) into an (a…
TRIX: Low-Skew Pulse Propagation for Fault-Tolerant Hardware
Christoph Lenzen, Ben Wiederhake
The vast majority of hardware architectures use a carefully timed reference signal to clock their computational logic. However, standard distribution solutions are not fault-tolera…
PALS: Plesiochronous and Locally Synchronous Systems
Johannes Bund, Matthias Függer, Christoph Lenzen +2
Consider an arbitrary network of communicating modules on a chip, each requiring a local signal telling it when to execute a computational step. There are three common solutions to…
A Breezing Proof of the KMW Bound
Corinna Coupette, Christoph Lenzen
In their seminal paper from 2004, Kuhn, Moscibroda, and Wattenhofer (KMW) proved a hardness result for several fundamental graph problems in the LOCAL model: For any (randomized) a…
Optimal Metastability-Containing Sorting via Parallel Prefix Computation
Johannes Bund, Christoph Lenzen, Moti Medina
Friedrichs et al. (TC 2018) showed that metastability can be contained when sorting inputs arising from time-to-digital converters, i.e., measurement values can be correctly sorted…
Low Diameter Graph Decompositions by Approximate Distance Computation
Ruben Becker, Yuval Emek, Christoph Lenzen
In many models for large-scale computation, decomposition of the problem is key to efficient algorithms. For distance-related graph problems, it is often crucial that such a decomp…
Parallel Balanced Allocations: The Heavily Loaded Case
Christoph Lenzen, Merav Parter, Eylon Yogev
We study parallel algorithms for the classical balls-into-bins problem, in which balls acting in parallel as separate agents are placed into bins. Algorithms operate in syn…
Locality of not-so-weak coloring
Alkida Balliu, Juho Hirvonen, Christoph Lenzen +2
Many graph problems are locally checkable: a solution is globally feasible if it looks valid in all constant-radius neighborhoods. This idea is formalized in the concept of locally…
Fault Tolerant Gradient Clock Synchronization
Johannes Bund, Christoph Lenzen, Will Rosenbaum
Synchronizing clocks in distributed systems is well-understood, both in terms of fault-tolerance in fully connected systems and the dependence of local and global worst-case skews…
Optimal Metastability-Containing Sorting Networks
Johannes Bund, Christoph Lenzen, Moti Medina
When setup/hold times of bistable elements are violated, they may become metastable, i.e., enter a transient state that is neither digital 0 nor 1. In general, metastability cannot…
Self-stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus
Christoph Lenzen, Joel Rybicki
We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of the nodes has its own clock. Our algorithms operate in a very strong fault…
Robust Routing Made Easy
Christoph Lenzen, Moti Medina, Mehrdad Saberi +1
With the increasing scale of communication networks, the likelihood of failures grows as well. Since these networks form a critical backbone of our digital society, it is important…
Self-stabilizing Byzantine Clock Synchronization with Optimal Precision
Pankaj Khanchandani, Christoph Lenzen
We revisit the approach to Byzantine fault-tolerant clock synchronization based on approximate agreement introduced by Lynch and Welch. Our contribution is threefold: (1) We provid…
Near-Optimal Self-Stabilising Counting and Firing Squads
Christoph Lenzen, Joel Rybicki
Consider a fully-connected synchronous distributed system consisting of nodes, where up to nodes may be faulty and every node starts in an arbitrary initial state. In the s…
CLEX: Yet Another Supercomputer Architecture?
Christoph Lenzen, Roger Wattenhofer
We propose the CLEX supercomputer topology and routing scheme. We prove that CLEX can utilize a constant fraction of the total bandwidth for point-to-point communication, at delays…
Metastability-Containing Circuits
Stephan Friedrichs, Matthias Függer, Christoph Lenzen
In digital circuits, metastability can cause deteriorated signals that neither are logical 0 or logical 1, breaking the abstraction of Boolean logic. Unfortunately, any way of read…
Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford
Stephan Friedrichs, Christoph Lenzen
A \emph{metric tree embedding} of expected \emph{stretch~} maps a weighted -node graph to a weighted tree with s…
Efficient counting with optimal resilience
Christoph Lenzen, Joel Rybicki, Jukka Suomela
Consider a complete communication network of nodes, where the nodes receive a common clock pulse. We study the synchronous -counting problem: given any starting state and up…
Towards Optimal Synchronous Counting
Christoph Lenzen, Joel Rybicki, Jukka Suomela
Consider a complete communication network of nodes, where the nodes receive a common clock pulse. We study the synchronous -counting problem: given any starting state and up…
Algebraic Methods in the Congested Clique
Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen +3
In this work, we use algebraic methods for studying distance computation and subgraph detection tasks in the congested clique model. Specifically, we adapt parallel matrix multipli…
Fast Partial Distance Estimation and Applications
Christoph Lenzen, Boaz Patt-Shamir
We study approximate distributed solutions to the weighted {\it all-pairs-shortest-paths} (APSP) problem in the CONGEST model. We obtain the following results. A deterministic…