# Christoph Lenzen

## Contact Details

NameChristoph Lenzen |
||

Affiliation |
||

Location |
||

## Pubs By Year |
||

## Pub CategoriesComputer Science - Distributed; Parallel; and Cluster Computing (24) Computer Science - Data Structures and Algorithms (9) Computer Science - Computational Complexity (2) Computer Science - Architecture (2) Computer Science - Networking and Internet Architecture (1) |

## Publications Authored By Christoph Lenzen

Constructing a sparse \emph{spanning subgraph} is a fundamental primitive in graph theory. In this paper, we study this problem in the Centralized Local model, where the goal is to decide whether an edge is part of the spanning subgraph by examining only a small part of the input; yet, answers must be globally consistent and independent of prior queries. Unfortunately, maximally sparse spanning subgraphs, i. Read More

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 provide a slightly refined variant of the algorithm yielding improved bounds on the skew that can be achieved and the sustainable frequency offsets. (2) We show how to extend the technique to also synchronize clock rates. Read More

Consider a fully-connected synchronous distributed system consisting of $n$ nodes, where up to $f$ nodes may be faulty and every node starts in an arbitrary initial state. In the synchronous $C$-counting problem, all nodes need to eventually agree on a counter that is increased by one modulo $C$ in each round for given $C>1$. In the self-stabilising firing squad problem, the task is to eventually guarantee that all non-faulty nodes have simultaneous responses to external inputs: if a subset of the correct nodes receive an external "go" signal as input, then all correct nodes should agree on a round (in the not-too-distant future) in which to jointly output a "fire" signal. Read More

We present a method for solving the shortest transshipmen} problem - also known as uncapacitated minimum cost flow - up to a multiplicative error of $ 1 + \epsilon $ in undirected graphs with polynomially bounded integer edge weights using a tailored gradient descent algorithm. An important special case of the transshipment problem is the single-source shortest paths (SSSP) problem. Our gradient descent algorithm takes $ \epsilon^{-3} polylog{n} $ iterations, and in each iteration it needs to solve the transshipment problem up to a multiplicative error of $ polylog n $, where $ n $ is the number of nodes. Read More

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 proportional to the sum of the number of intermediate hops and the maximum physical distance between any two nodes. Moreover, % applying an asymmetric bandwidth assignment to the links, all-to-all communication can be realized $(1+o(1))$-optimally both with regard to bandwidth and delays. Read More

In digital circuits, \emph{metastable} signals have voltages strictly between logical 0 and logical~1, breaking the abstraction of Boolean logic. Unfortunately, any way of reading a signal from an unsynchronized clock domain or performing an analog-to-digital conversion incurs the risk of a metastable result; no physical implementation of a digital circuit can deterministically avoid, resolve, or detect metastability (Marino,~1981). Traditionally, the only countermeasure is to write a potentially metastable signal into a synchronizer---a bistable storage element like a flip-flop---and wait. Read More

A \emph{metric tree embedding} of expected \emph{stretch~$\alpha \geq 1$} maps a weighted $n$-node graph $G = (V, E, \omega)$ to a weighted tree $T = (V_T, E_T, \omega_T)$ with $V \subseteq V_T$ such that, for all $v,w \in V$, $\operatorname{dist}(v, w, G) \leq \operatorname{dist}(v, w, T)$ and $operatorname{E}[\operatorname{dist}(v, w, T)] \leq \alpha \operatorname{dist}(v, w, G)$. Such embeddings are highly useful for designing fast approximation algorithms, as many hard problems are easy to solve on tree instances. However, to date the best parallel $(\operatorname{polylog} n)$-depth algorithm that achieves an asymptotically optimal expected stretch of $\alpha \in \operatorname{O}(\log n)$ requires $\operatorname{\Omega}(n^2)$ work and a metric as input. Read More

We present a near-optimal distributed algorithm for $(1+o(1))$-approximation of single-commodity maximum flow in undirected weighted networks that runs in $(D+ \sqrt{n})\cdot n^{o(1)}$ communication rounds in the \Congest model. Here, $n$ and $D$ denote the number of nodes and the network diameter, respectively. This is the first improvement over the trivial bound of $O(n^2)$, and it nearly matches the $\tilde{\Omega}(D+ \sqrt{n})$ round complexity lower bound. Read More

Consider a complete communication network of $n$ nodes, where the nodes receive a common clock pulse. We study the synchronous $c$-counting problem: given any starting state and up to $f$ faulty nodes with arbitrary behaviour, the task is to eventually have all correct nodes labeling the pulses with increasing values modulo $c$ in agreement. Thus, we are considering algorithms that are self-stabilising despite Byzantine failures. Read More

Consider a complete communication network of $n$ nodes, where the nodes receive a common clock pulse. We study the synchronous $c$-counting problem: given any starting state and up to $f$ faulty nodes with arbitrary behaviour, the task is to eventually have all correct nodes counting modulo $c$ in agreement. Thus, we are considering algorithms that are self-stabilizing despite Byzantine failures. Read More

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 multiplication implementations to the congested clique, obtaining an $O(n^{1-2/\omega})$ round matrix multiplication algorithm, where $\omega < 2.3728639$ is the exponent of matrix multiplication. Read More

We study approximate distributed solutions to the weighted {\it all-pairs-shortest-paths} (APSP) problem in the CONGEST model. We obtain the following results. $1. Read More

While algebrisation constitutes a powerful technique in the design and analysis of centralised algorithms, to date there have been hardly any applications of algebraic techniques in the context of distributed graph algorithms. This work is a case study that demonstrates the potential of algebrisation in the distributed context. We will focus on distributed graph algorithms in the congested clique model; the graph problems that we will consider include, e. Read More

In this work, we examine a generic class of simple distributed balls-into-bins algorithms. Exploiting the strong concentration bounds that apply to balls-into-bins games, we provide an iterative method to compute accurate estimates of the remaining balls and the load distribution after each round. Each algorithm is classified by (i) the load that bins accept in a given round, (ii) the number of messages each ball sends in a given round, and (iii) whether each such message is given a rank expressing the sender's inclination to commit to the receiving bin (if feasible). Read More

We present new distributed algorithms for constructing a Steiner Forest in the CONGEST model. Our deterministic algorithm finds, for any given constant $\epsilon>0$, a $(2+\epsilon)$-approximation in $\tilde{O}(sk+\sqrt{\min(st,n)})$ rounds, where $s$ is the shortest path diameter, $t$ is the number of terminals, $k$ is the number of terminal components in the input, and $n$ is the number of nodes. Our randomized algorithm finds, with high probability, an $O(\log n)$- approximation in time $\tilde{O}(k+\min(s,\sqrt n)+D)$, where $D$ is the unweighted diameter of the network. Read More

We consider the ANTS problem [Feinerman et al.] in which a group of agents collaboratively search for a target in a two-dimensional plane. Because this problem is inspired by the behavior of biological species, we argue that in addition to studying the {\em time complexity} of solutions it is also important to study the {\em selection complexity}, a measure of how likely a given algorithmic strategy is to arise in nature due to selective pressures. Read More

We show that there is no deterministic local algorithm (constant-time distributed graph algorithm) that finds a $(7-\epsilon)$-approximation of a minimum dominating set on planar graphs, for any positive constant $\epsilon$. In prior work, the best lower bound on the approximation ratio has been $5-\epsilon$; there is also an upper bound of $52$. Read More

The majority of the literature on consensus assumes that protocols are jointly started at all nodes of the distributed system. We show how to remove this problematic assumption in semi-synchronous systems, where messages delays and relative drifts of local clocks may vary arbitrarily within known bounds. Our framework is self-stabilizing and efficient both in terms of communication and time; more concretely, compared to a synchronous start in a synchronous model of a non-self-stabilizing protocol, we achieve a constant-factor increase in the time and communicated bits to complete an instance, plus an additive communication overhead of O(n log n) broadcasted bits per time unit and node. Read More

Consider a complete communication network on $n$ nodes, each of which is a state machine. In synchronous 2-counting, the nodes receive a common clock pulse and they have to agree on which pulses are "odd" and which are "even". We require that the solution is self-stabilising (reaching the correct operation from any initial state) and it tolerates $f$ Byzantine failures (nodes that send arbitrary misinformation). Read More

We describe a distributed randomized algorithm computing approximate distances and routes that approximate shortest paths. Let n denote the number of nodes in the graph, and let HD denote the hop diameter of the graph, i.e. Read More

Consider a clique of n nodes, where in each synchronous round each pair of nodes can exchange O(log n) bits. We provide deterministic constant-time solutions for two problems in this model. The first is a routing problem where each node is source and destination of n messages of size O(log n). Read More

We present concept and implementation of a self-stabilizing Byzantine fault-tolerant distributed clock generation scheme for multi-synchronous GALS architectures in critical applications. It combines a variant of a recently introduced self-stabilizing algorithm for generating low-frequency, low-accuracy synchronized pulses with a simple non-stabilizing high-frequency, high-accuracy clock synchronization algorithm. We provide thorough correctness proofs and a performance analysis, which use methods from fault-tolerant distributed computing research but also addresses hardware-related issues like metastability. Read More

Let G = (V,E) be an n-vertex graph and M_d a d-vertex graph, for some constant d. Is M_d a subgraph of G? We consider this problem in a model where all n processes are connected to all other processes, and each message contains up to O(log n) bits. A simple deterministic algorithm that requires O(n^((d-2)/d) / log n) communication rounds is presented. Read More

Today's hardware technology presents a new challenge in designing robust systems. Deep submicron VLSI technology introduced transient and permanent faults that were never considered in low-level system designs in the past. Still, robustness of that part of the system is crucial and needs to be guaranteed for any successful product. Read More

We explore the fundamental limits of distributed balls-into-bins algorithms. We present an adaptive symmetric algorithm that achieves a bin load of two in log* n+O(1) communication rounds using O(n) messages in total. Larger bin loads can be traded in for smaller time complexities. Read More

We study the problem of clock synchronization in highly dynamic networks, where communication links can appear or disappear at any time. The nodes in the network are equipped with hardware clocks, but the rate of the hardware clocks can vary arbitrarily within specific bounds, and the estimates that nodes can obtain about the clock values of other nodes are inherently inaccurate. Our goal in this setting is to output a logical clock at each node, such that the logical clocks of any two nodes are not too far apart, and nodes that remain close to each other in the network for a long time are better synchronized than distant nodes. Read More