Publisher Copyright: © 2026 Copyright held by the owner/author(s).

Synchronous Counting is the task of reaching agreement on a common round counter in a synchronous system of n nodes with up to t Byzantine faults in a self-stabilizing manner. That is, after transient faults may have arbitrarily corrupted the system state and ceased, the at least n - t non-faulty nodes need to (re-)establish that (i) their local outputs are identical and (ii) increase by 1 modulo C in each round. An overhead-free reduction from consensus shows that all known lower bounds and impossibilities for consensus carry over to the counting problem. In the other direction, prior work has established that a consensus algorithm A can be turned into a counting algorithm at small overhead relative to the running time and bit complexity of A, without losing resilience.

Byzantine Agreement and Broadcast are traditionally studied in one of two extremes: the authenticated setting, where a public key infrastructure (PKI) enables universally verifiable signatures and yields higher fault tolerance, and the unauthenticated setting, where no PKI is available and resilience necessarily drops. Motivated by Proof-of-Stake blockchains, where only a stable subset of participants (e.g., validators) have registered long-term keys while others do not, we initiate a systematic study of consensus in the partially authenticated setting, where a subset of parties are registered in a PKI and the remaining parties are unregistered.

Gradient clock synchronization (GCS) algorithms minimize the worst-case clock offset between the nodes in a distributed network of diameter D and size n. They achieve optimal offsets of Θ(log D) locally, i.e., between adjacent nodes [14] and Θ(D) globally [2]. A key open problem in this area is to achieve fault tolerance at minimal edge replication overhead.

Constrained Forest Problems (CFPs) as introduced by Goemans and Williamson in 1995 capture a wide range of network design problems with edge subsets as solutions, such as Minimum Spanning Tree, Steiner Forest, and Point-to-Point Connection. While individual CFPs have been studied extensively in individual computational models, a unified approach to solving general CFPs in multiple computational models has been lacking. Against this background, we present the shell-decomposition algorithm, a model-agnostic meta-algorithm that efficiently computes a $(2+ε)$-approximation to CFPs for a broad class of forest functions. To demonstrate the power and flexibility of this result, we instantiate our algorithm for 3 fundamental, NP-hard CFPs in 3 different computational models. For example, for constant $ε$, we obtain the following $(2+ε)$-approximations in the Congest model: 1. For Steiner Forest specified via input components, where each node knows the identifier of one of $k$ disjoint subsets of $V$, we achieve a deterministic $(2+ε)$-approximation in $O(\sqrt{n}+D+k)$ rounds, where $D$ is the hop diameter of the graph. 2. For Steiner Forest specified via symmetric connection requests, where connection requests are issued to pairs of nodes, we leverage randomized equality testing to reduce the running time to $O(\sqrt{n}+D)$, succeeding with high probability. 3. For Point-to-Point Connection, we provide a $(2+ε)$-approximation in $O(\sqrt{n}+D)$ rounds. 4. For Facility Placement and Connection, a relative of non-metric Facility Location, we obtain a $(2+ε)$-approximation in $O(\sqrt{n}+D)$ rounds. We further show how to replace the $\sqrt{n}+D$ term by the complexity of solving Partwise Aggregation, achieving (near-)universal optimality in any setting in which a solution to Partwise Aggregation in near-shortcut-quality time is known.

In digital circuits, hazardous input signals are a result of spurious operation of bistable elements. For example, the problem occurs in circuits with asynchronous inputs or clock domain crossings. Marino (TC’81) showed that hazards in bistable elements are inevitable. Hazard-free circuits compute the “most stable” output possible on hazardous inputs, under the constraint that it returns the same output as the circuit on stable inputs. Ikenmeyer et al. (JACM’19) proved an unconditional exponential separation between the hazard-free complexity and (standard) circuit complexity of explicit functions. Despite that, asymptotically optimal hazard-free sorting circuit are possible (Bund et al., TC’19). This raises the question: Which classes of functions permit efficient hazard-free circuits? We prove that circuit implementations of transducers with small state space are such a class. A transducer is a finite state machine that transcribes, symbol by symbol, an input string of length n into an output string of length n. We present a construction that transforms any function arising from a transducer into an efficient circuit that computes the hazard-free extension of the function. For transducers with constant state space, the circuit has asymptotically optimal size, with small constants if the state space is small.

A randomness beacon is a source of continuous and publicly verifiable randomness which is of crucial importance for many applications. Existing works on randomness beacons suffer from at least one of the following drawbacks: (i) security only against static (i.e., non-adaptive) adversaries, (ii) each epoch takes many rounds of communication, or (iii) computationally expensive tools such as proof-of-work (PoW) or verifiable delay functions (VDF). In this work, we introduce GRandLine, the first adaptively secure randomness beacon protocol that overcomes all these limitations while preserving simplicity and optimal resilience in the synchronous network setting. We achieve our result in two steps. First, we design a novel distributed key generation (DKG) protocol GRand that runs in O(λ n2 log n ) bits of communication but, unlike most conventional DKG protocols, outputs both secret and public keys as group elements. Here, λ denotes the security parameter. Second, following termination of GRand, parties can use their keys to derive a sequence of randomness beacon values, where each random value costs only a single asynchronous round and O(λ n2) bits of communication. We implement GRandLine and evaluate it using a network of up to 64 parties running in geographically distributed AWS instances. Our evaluation shows that GRandLine can produce about 2 beacon outputs per second in a network of 64 parties. We compare our protocol to the state-of-the-art randomness beacon protocols OptRand (NDSS '23), BRandPiper (CCS '21), and Drand, in the same setting and observe that it vastly outperforms them.

Gradient clock synchronisation (GCS) algorithms minimise the worst-case clock offset between the nodes in a distributed network of diameter D and size n. They achieve optimal offsets of Θ(log D) locally, i.e. between adjacent nodes [Lenzen et al., 2010], and Θ(D) globally [Biaz and Welch, 2001]. A key open problem in this area is to achieve fault tolerance at minimal overhead in terms of the number of edges. In this work, we achieve this goal under the assumption of an average-case distribution of faults, i.e., nodes fail with independent probability p ∈ o(n^{-1/2}). In more detail, we present a self-stabilising GCS algorithm for a grid-like directed graph with in- and out-degrees of 3. Note that even for tolerating a single fault, this degree is necessary. Moreover, the failure probability p is the largest possible ensuring the necessary condition that for each node at most one in-neighbour fails with probability 1-o(1). Our algorithm achieves asymptotically optimal local skew of Θ(log D) with probability 1-o(1); this holds under general worst-case assumptions on link delay and clock speed variations, provided they change slowly relative to the speed of the system. On the one hand, our results are of practical interest. As we discuss with care, the fault model is suitable for synchronously clocked hardware. Since our algorithm can simultaneously sustain a constant number of arbitrary changes due to faults in each clock cycle, it achieves sufficient robustness to dramatically increase the size of synchronously clocked Systems-on-Chip. On the other hand, our result is of a theoretical and algorithmic nature. We show that for a worst-case distribution of f 1-local faulty nodes within our fault model’s locality constraints, our algorithm achieves a local skew of O(5^flog D), while for our model with probabilistic distribution of faults the algorithm achieves O(log D). Our work raises questions for further theoretical investigation on techniques for fault tolerance and trade-offs between fault distribution and edge density of graphs.

Abstract. We study the problem of approximating the distances in an undirected weighted graph [Formula: see text] by the distances in trees based on the notion of stretch. Focusing on decentralized models of computation such as the [Formula: see text], [Formula: see text], and semi-streaming models, our main results are as follows: (1) We develop a simple randomized algorithm that constructs a spanning tree such that the expected stretch of every edge is [Formula: see text], where [Formula: see text] is the number of nodes in [Formula: see text]. If [Formula: see text] is unweighted, then this algorithm can be implemented to run in [Formula: see text] rounds in the [Formula: see text] model, where [Formula: see text] is the hop-diameter of [Formula: see text]; thus our algorithm is asymptotically optimal in this case. In the weighted case, the run-time of the algorithm matches the currently best known bound for exact single source shortest path (SSSP) computations, which despite recent progress is still separated from the lower bound of [Formula: see text] by polynomial factors. A naive attempt to replace exact SSSP computations with approximate ones in order to improve the complexity in the weighted case encounters a fundamental challenge, as the underlying decomposition technique fails to work under distance approximation. (2) We overcome this obstacle by developing a technique termed blurry ball growing. This technique, in combination with a clever algorithmic idea of Miller, Peng, and Xu (SPAA 2013), allows us to obtain low diameter graph decompositions with small edge cutting probabilities based solely on approximate SSSP computations. (3) Using these decompositions, we in turn obtain metric tree embedding algorithms in the vein of the celebrated work of Bartal (FOCS 1996), whose computational complexity is optimal up to polylogarithmic factors not only in the [Formula: see text] model but also in the [Formula: see text] and semi-streaming models. Our embeddings have the additional useful property that the tree can be mapped back to the original graph such that each edge is “used” only logarithmically many times. This property is of interest for capacitated problems and for simulating [Formula: see text] algorithms on the tree into which the graph is embedded.

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 that they rely on robust routing algorithms which ensure connectivity despite such failures. While most modern communication networks feature robust routing mechanisms, these mechanisms are often fairly complex to design and verify, as they need to account for the effects of failures and rerouting on communication. This paper conceptualizes the design of robust routing mechanisms, with the aim to avoid such complexity. In particular, we showcase simple and generic blackbox transformations that increase resilience of routing against independently distributed failures, which allows to simulate the routing scheme on the original network, even in the presence of non-benign node failures (henceforth called faults). This is attractive as the system specification and routing policy can simply be preserved. We present a scheme for constructing such a reinforced network, given an existing (synchronous) network and a routing scheme. We prove that this algorithm comes with small constant overheads, and only requires a minimal amount of additional node and edge resources; in fact, if the failure probability is smaller than$1/n$, the algorithm can come without any overhead at all. At the same time, it allows to tolerate a large number of independent random (node) faults, asymptotically almost surely. We complement our analytical results with simulations on different real-world topologies.

Abstract In this paper, we refine the (almost) existentially optimal distributed Laplacian solver of Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS ‘21) into an (almost) universally optimal distributed Laplacian solver. Specifically, when the topology is known (i.e., the Supported-CONGEST model), we show that any Laplacian system on an n -node graph with shortcut quality $$\textrm{SQ}(G)$$ SQ ( G ) can be solved after $$n^{o(1)} \text {SQ}(G) \log (1/\epsilon )$$ n o ( 1 ) SQ ( G ) log ( 1 / ϵ ) rounds, where $$\epsilon >0$$ ϵ > 0 is the required accuracy. This almost matches our lower bound that guarantees that any correct algorithm on G requires $$\widetilde{\Omega }(\textrm{SQ}(G))$$ Ω ~ ( SQ ( G ) ) rounds, even for a crude solution with $$\epsilon \le 1/2$$ ϵ ≤ 1 / 2 . Several important implications hold in the unknown-topology (i.e., standard CONGEST) case: for excluded-minor graphs we get an almost universally optimal algorithm that terminates in $$D \cdot n^{o(1)} \log (1/\epsilon )$$ D · n o ( 1 ) log ( 1 / ϵ ) rounds, where D is the hop-diameter of the network; as well as $$n^{o(1)} \log (1/\epsilon )$$ n o ( 1 ) log ( 1 / ϵ ) -round algorithms for the case of $$\textrm{SQ}(G) \le n^{o(1)}$$ SQ ( G ) ≤ n o ( 1 ) , which holds for most networks of interest. Moreover, following a recent line of work in distributed algorithms, we consider a hybrid communication model which enhances CONGEST with limited global power in the form of the node-capacitated cli

Ikenmeyer et al. (JACM'19) proved an unconditional exponential separation between the hazard-free complexity and (standard) circuit complexity of explicit functions. This raises the question: which classes of functions permit efficient hazard-free circuits? In this work, we prove that circuit implementations of transducers with small state space are such a class. A transducer is a finite state machine that transcribes, symbol by symbol, an input string of length n into an output string of length n. We present a construction that transforms any function arising from a transducer into an efficient circuit of size 𝒪(n) computing the hazard-free extension of the function. More precisely, given a transducer with s states, receiving n input symbols encoded by l bits, and computing n output symbols encoded by m bits, the transducer has a hazard-free circuit of size n*m*2^{𝒪(s+𝓁)} and depth 𝒪(s*log(n) + 𝓁); in particular, if s, 𝓁,m ∈ 𝒪(1), size and depth are asymptotically optimal. In light of the strong hardness results by Ikenmeyer et al. (JACM'19), we consider this a surprising result.

Early-stopping consensus protocols guarantee termination within a number of rounds that depends only on the actual number f of faulty nodes in a run, not the maximum number of faults that can be tolerated. We consider early-stopping deterministic synchronous consensus with Byzantine faults in a fully connected message passing system of n nodes. Many such protocols are known, but so far none combine early-stopping in O(f+1) rounds with optimal resilience and a bit complexity of o(n2(f+1)).

This paper refines the distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS '21) via the Ghaffari-Haeupler framework (SODA '16) of low-congestion shortcuts. Specifically, if ε > 0 is the error of the Laplacian solver, we obtain two main results.

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. While this is well-studied for consensus, it has been underexplored in the context of fault-tolerant clock synchronization, even in fully connected systems. Here, the honest parties of an n-node system are required to compute output clocks of small skew (i.e., phase offset) despite local clock rates varying between 1 and ϑ > 1, end-to-end communication delays varying between d - u and d, and the interference from malicious parties. Known algorithms with (trivially optimal) resilience of [n/2] - 1 improve over the tight bound of [n/3] - 1 holding without signatures for any skew bound [6, 18], but incur skew d [1] or Ω(n(u + (ϑ - 1)d)) [14]. Since typically d >> u and ϑ - 1 « 1, this is far from the lower bound of u + (ϑ - 1)d that applies even in the fault-free case [3].

Many critical computing applications rely on secure and dependable time which is reliably synchronized across large distributed systems. Today's time synchronization architectures are commonly based on global navigation satellite systems at the considerable risk of being exposed to outages, malfunction, or attacks against availability and accuracy. This paper describes a practical instantiation of a new global, Byzantine fault-tolerant clock synchronization approach that does not place trust in any single entity and is able to tolerate a fraction of faulty entities while still maintaining synchronization on a global scale among otherwise sovereign network topologies. Leveraging strong resilience and security properties provided by the path-aware SCION networking architecture, the presented design can be implemented as a backward compatible active standby solution for existing time synchronization deployments. Through extensive evaluation, we demonstrate that over 94 % of time servers reliably minimize the offset of their local clocks to real-time in the presence of up to 20 % malicious nodes, and all time servers remain synchronized with a skew of only 2 ms even after one year of reference clock outage.

In classical synchronous designs, supply voltage droops can be handled by accounting for them in clock margins. However, this results in a significant performance hit even if droops are rare. In contrast, adaptive strategies detect such potentially hazardous events and either initiate a rollback to a previous state or proactively reduce clock speed in order to prevent timing violations. The performance of such solutions critically depends on a very fast response to droops. State-of-the-art solutions incur synchronization delays in the order of several clock cycles to avoid, with sufficient probability, that the clock signal is affected by metastability. We present an all-digital circuit that can respond to droops within a fraction of a clock cycle. This is achieved by using potentially metastable measurement values to delay clock signalswhilethey undergo synchronization, instead ofafterthey are synchronized. The challenge is to ensure that this strategy does not lead to harmful glitches or metastable upsets within the circuit. To this end, we verify our solution by formally proving correctness. We complement our findings by simulations of a 65-nm ASIC design confirming the results of our analysis.

We present a method for solving the transshipment problem-also known as uncapacitated minimum cost flow-up to a multiplicative error of 1+ε in undirected graphs with nonnegative edge weights using a tailored gradient descent algorithm. Using O(\cdot ) to hide polylogarithmic factors in n (the number of nodes in the graph), our gradient descent algorithm takes O(ε 2) iterations, and in each iteration it solves an instance of the transshipment problem up to a multiplicative error of polylog n. In particular, this allows us to perform a single iteration by computing a solution on a sparse spanner of logarithmic stretch. Using a randomized rounding scheme, we can further extend the method to finding approximate solutions for the single-source shortest paths (SSSP) problem. As a consequence, we improve upon prior works by obtaining the following results: (1) Broadcast CONGEST model: (1 + ε)-approximate SSSP using O(( n + D)ε 3) rounds, where D is the (hop) diameter of the network. (2) Broadcast Congested Clique model: (1 + ε)-approximate transshipment and SSSP using O (ε 2) rounds. (3) Multipass Streaming model: (1 + ε)-approximate transshipment and SSSP using O(n) space and O(ε 2) passes. The previously fastest SSSP algorithms for these models leverage sparse hop sets. We bypass the hop set construction; computing a spanner is sufficient with our method. The above bounds assume nonnegative edge weights that are polynomially bounded in n; for general nonnegative weights, there is an additional multiplicative overhead equal to the logarithm of the maximum ratio between nonzero weights. Our algorithms can also handle asymmetric costs for traversing edges in opposite directions. In this case, we obtain an additional multiplicative dependence of the maximum ratio between the two costs on some edge.

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 decomposition results in clusters of small diameter, while the probability that an edge is cut by the decomposition scales linearly with the length of the edge. There is a large body of literature on low diameter graph decomposition with small edge cutting probabilities, with all existing techniques heavily building on single source shortest paths (SSSP) computations. Unfortunately, in many theoretical models for large-scale computations, the SSSP task constitutes a complexity bottleneck. Therefore, it is desirable to replace exact SSSP computations with approximate ones. However this imposes a fundamental challenge since the existing constructions of low diameter graph decomposition with small edge cutting probabilities inherently rely on the subtractive form of the triangle inequality, which fails to hold under distance approximation. The current paper overcomes this obstacle by developing a technique termed blurry ball growing. By combining this technique with a clever algorithmic idea of Miller et al. (SPAA 2013), we obtain a construction of low diameter decompositions with small edge cutting probabilities which replaces exact SSSP computations by (a small number of) approximate ones. The utility of our approach is showcased by deriving efficient algorithms that work in the CONGEST, PRAM, and semi-streaming models of computation. As an application, we obtain metric tree embedding algorithms in the vein of Bartal (FOCS 1996) whose computational complexities in these models are optimal up to polylogarithmic factors. Our embeddings have the additional useful property that the tree can be mapped back to the original graph such that each edge is "used" only logaritmically many times, which is of interest for capacitated problems and simulating CONGEST algorithms on the tree into which the graph is embedded.

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 without resolving metastability using synchronizers first. However, this work left open whether this can be done by small circuits. We show that this is indeed possible, by providing a circuit that sorts Gray code inputs (possibly containing a metastable bit) and has asymptotically optimal depth and size. Our solution utilizes the parallel prefix computation (PPC) framework (JACM 1980). We improve this construction by bounding its fan-out by an arbitrary f ≥ 3, without affecting depth and increasing circuit size by a small constant factor only. Thus, we obtain the first PPC circuits with asymptotically optimal size, constant fan-out, and optimal depth. To show that applying the PPC framework to the sorting task is feasible, we prove that the latter can, despite potential metastability, be decomposed such that the core operation is associative. We obtain asymptotically optimal metastability-containing sorting networks. We complement these results with simulations, independently verifying the correctness as well as small size and delay of our circuits. Proofs are omitted in this version; the article with full proofs is provided online at http://arxiv.org/abs/1911.00267.

Synchronizing clocks in distributed systems is well-understood, both in terms of fault-tolerance in fully connected systems, and the optimal achievable local skew in general fault-free networks. However, so far nothing non-trivial is known about the local skew that can be achieved in non-fully-connected topologies even under a single Byzantine fault. In this work, we show that asymptotically optimal local skew can be achieved in the presence of Byzantine faults.

We study parallel algorithms for the classical balls-into-bins problem, in which m balls acting in parallel as separate agents are placed into n bins. Algorithms operate in synchronous rounds, in each of which balls and bins exchange messages once. The goal is to minimize the maximal load over all bins using a small number of rounds and few messages. While the case of $m=n$ balls has been extensively studied, little is known about the heavily loaded case. In this work, we consider parallel algorithms for this somewhat neglected regime of $m\gg n$. The naive solution of allocating each ball to a bin chosen uniformly and independently at random results in maximal load $m/n+Θ(\sqrtm/n\cdot łog n )$ (for $m\geq n łog n$) with high probability (w.h.p.). In contrast, for the sequential setting Berenbrink et al (SIAM J. Comput 2006) showed that letting each ball join the least loaded bin of two randomly selected bins reduces the maximal load to $m/n+O(łogłog m)$ w.h.p. To date, no parallel variant of such a result is known. We present a simple parallel threshold algorithm that obtains a maximal load of $m/n+O(1)$ w.h.p. within $O(łogłog (m/n)+łog^* n)$ rounds. The algorithm is symmetric (balls and bins all "look the same"), and balls send $O(1)$ messages in expectation per round. The additive term of $O(łog^* n)$ in the complexity is known to be tight for such algorithms (Lenzen and Wattenhofer Distributed Computing 2016). We also prove that our analysis is tight, i.e., algorithms of the type we provide must run for $Ømega(\min\łogłog (m/n),n\ )$ rounds w.h.p. Finally, we give a simple asymmetric algorithm (i.e., balls are aware of a common labeling of the bins) that achieves a maximal load of $m/n + O(1)$ in a constant number of rounds w.h.p. Again, balls send only a single message per round, and bins receive $(1+o(1))m/n+O(łog n)$ messages w.h.p. This goes to show that, similar to the case of $m=n$, asymmetry allows for highly efficient solutions.

Given an undirected graph with integer edge lengths, we study the problem of approximating the distances in the graph by a spanning tree based on the notion of stretch. Our main contribution is a distributed algorithm in the CONGEST model of computation that constructs a random spanning tree with the guarantee that the expected stretch of every edge is O(log^{3} n), where n is the number of nodes in the graph. If the graph is unweighted, then this algorithm can be implemented to run in O(D) rounds, where D is the hop-diameter of the graph, thus being asymptotically optimal. In the weighted case, the run-time of our algorithm matches the currently best known bound for exact distance computations, i.e., O~ (min{sqrt{n D}, sqrt{n} D^{1 / 4} + n^{3 / 5} + D}). We stress that this is the first distributed construction of spanning trees leading to poly-logarithmic expected stretch with non-trivial running time.

We consider shortest paths computation and related tasks from the viewpoint of network algorithms, where the n-node input graph is also the computational system: nodes represent processors and edges represent communication links, which can in each time step carry an $$\mathcal {O}(\log n)$$ -bit message. We identify several basic distributed distance computation tasks that are highly useful in the design of more sophisticated algorithms and provide efficient solutions. We showcase the utility of these tools by means of several applications.

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. Moreover, no node should generate a “fire” signal without some correct node having previously received a “go” signal as input. We present a framework reducing both tasks to binary consensus at very small cost. For example, we obtain a deterministic algorithm for self-stabilising Byzantine firing squads with optimal resilience $$f

The problem of constructing hazard-free Boolean circuits dates back to the 1940s and is an important problem in circuit design. Our main lower-bound result unconditionally shows the existence of functions whose circuit complexity is polynomially bounded while every hazard-free implementation is provably of exponential size. Previous lower bounds on the hazard-free complexity were only valid for depth 2 circuits. The same proof method yields that every subcubic implementation of Boolean matrix multiplication must have hazards. These results follow from a crucial structural insight: Hazard-free complexity is a natural generalization of monotone complexity to all (not necessarily monotone) Boolean functions. Thus, we can apply known monotone complexity lower bounds to find lower bounds on the hazard-free complexity. We also lift these methods from the monotone setting to prove exponential hazard-free complexity lower bounds for non-monotone functions. As our main upper-bound result, we show how to efficiently convert a Boolean circuit into a bounded-bit hazard-free circuit with only a polynomially large blow-up in the number of gates. Previously, the best known method yielded exponentially large circuits in the worst case, so our algorithm gives an exponential improvement. As a side result, we establish the NP-completeness of several hazard detection problems.

We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of the n nodes has its own clock. Our algorithms operate in a very strong fault model: we require self-stabilisation, i.e., the initial state of the system may be arbitrary, and there can be up to f < n /3 ongoing Byzantine faults, i.e., nodes that deviate from the protocol in an arbitrary manner. Furthermore, we assume that the local clocks of the nodes may progress at different speeds (clock drift) and communication has bounded delay. In this model, we study the pulse synchronisation problem, where the task is to guarantee that eventually all correct nodes generate well-separated local pulse events (i.e., unlabelled logical clock ticks) in a synchronised manner. Compared to prior work, we achieve exponential improvements in stabilisation time and the number of communicated bits, and give the first sublinear-time algorithm for the problem: • In the deterministic setting, the state-of-the-art solutions stabilise in time Θ ( f ) and have each node broadcast Θ( f log f ) bits per time unit. We exponentially reduce the number of bits broadcasted per time unit to Θ (log f ) while retaining the same stabilisation time. • In the randomised setting, the state-of-the-art solutions stabilise in time Θ( f ) and have each node broadcast O (1) bits per time unit. We exponentially reduce the stabilisation time to polylog f while each node broadcasts polylog f bits per time unit. These results are obtained by means of a recursive approach reducing the above task of self-stabilising pulse synchronisation in the bounded-delay model to non-self-stabilising binary consensus in the synchronous model. In general, our approach introduces at most logarithmic overheads in terms of stabilisation time and broadcasted bits over the underlying consensus routine.

In the Byzantine-tolerant clock synchronization problem, the goal is to synchronize the clocks of n fully connected nodes. The clocks run at rates between 1 and 𝜗 > 1, and messages have a delay (including computation) between d − U and d . Moreover, up to f < n /3 of the nodes can fail by deviating arbitrarily from the protocol, i.e., are Byzantine. Despite this interference, correct nodes need to generate distinguished events (or pulses ) almost simultaneously and periodically. The quality of the solution is measured by the skew , which is the maximum real time difference between corresponding pulses. In the self-stabilizing setting, in addition we allow for transient failures, possibly of all nodes. Once transient faults have ceased and at most f nodes remain faulty, the system should start generating synchronized pulses again. We design a self-stabilizing solution to this problem with asymptotically optimal skew. We achieve our goal by refining and extending the protocol of Lynch and Welch and make the following contributions in the process. We give a simple analysis of the Lynch and Welch protocol with improved bounds on skew and tolerable difference in clock rates by rebuilding upon the main ingredient of their protocol, called approximate agreement . We give a modified version of the protocol so that the frequency and amount of communication between the nodes is reduced. The modification adds a step to adjust the clock rates by another application of approximate agreement. The skew bound achieved is asymptotically optimal for suitable choices of parameters. We present a method to add self-stabilization to the above protocols while preserving their skew bounds. The heart of the method is a coupling scheme that leverages a self-stabilizing protocol with a larger skew.

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 [1]. In general, metastability cannot be avoided, a problem that manifests whenever taking discrete measurements of analog values. Metastability of the output then reflects uncertainty as to whether a measurement should be rounded up or down to the next possible measurement outcome. Surprisingly, Lenzen & Medina (ASYNC 2016) showed that metastability can be contained, i.e., measurement values can be correctly sorted without resolving metastability first. However, both their work and the state of the art by Bund et al. (DATE 2017) leave open whether such a solution can be as small and fast as standard sorting networks. We show that this is indeed possible, by providing a circuit that sorts Gray code inputs (possibly containing a metastable bit) and has asymptotically optimal depth and size. Concretely, for 10-channel sorting networks and 16-bit wide inputs, we improve by 48.46% in delay and by 71.58% in area over Bund et al. Our simulations indicate that straightforward transistor-level optimization is likely to result in performance on par with standard (non-containing) solutions.

Constructing a sparse 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.e., spanning trees, cannot be constructed efficiently in this model. Therefore, we settle for a spanning subgraph containing at most (1+epsilon)n edges (where n is the number of vertices and epsilon is a given approximation/sparsity parameter). We achieve a query complexity of O~(poly(Delta/epsilon)n^{2/3}), where Delta is the maximum degree of the input graph. Our algorithm is the first to do so on arbitrary bounded degree graphs. Moreover, we achieve the additional property that our algorithm outputs a spanning subgraph of bounded stretch i.e., distances are approximately preserved. With high probability, for each deleted edge there is a path of O(log n * (Delta+log n)/epsilon) hops in the output that connects its endpoints.

The problem of constructing hazard-free Boolean circuits dates back to the 1940s and is an important problem in circuit design. Our main lower-bound result unconditionally shows the existence of functions whose circuit complexity is polynomially bounded while every hazard-free implementation is provably of exponential size. Previous lower bounds on the hazard-free complexity were only valid for depth 2 circuits. The same proof method yields that every subcubic implementation of Boolean matrix multiplication must have hazards. These results follow from a crucial structural insight: Hazard-free complexity is a natural generalization of monotone complexity to all (not necessarily monotone) Boolean functions. Thus, we can apply known monotone complexity lower bounds to find lower bounds on the hazard-free complexity. We also lift these methods from the monotone setting to prove exponential hazard-free complexity lower bounds for non-monotone functions.

A metric tree embedding of expected stretch α ≥ 1 maps a weighted n -node graph G = ( V , E , ω) to a weighted tree T = ( V T , E T , ω T ) with V ⊑ V T such that, for all v , w ∈ V , dist( v , w , G ) ≤ dist( v , w , T ), and E[dist( v , w , T )] ≤ α 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 polylog n )-depth algorithm that achieves an asymptotically optimal expected stretch of α ∈ O(log n ) requires Ω ( n 2 ) work and a metric as input. In this article, we show how to achieve the same guarantees using polylog n depth and Õ( m 1+ε ) work, where m = | E | and ε > 0 is an arbitrarily small constant. Moreover, one may further reduce the work to Õ( m + n 1+ε ) at the expense of increasing the expected stretch to O(ε −1 log n ). Our main tool in deriving these parallel algorithms is an algebraic characterization of a generalization of the classic Moore-Bellman-Ford algorithm. We consider this framework, which subsumes a variety of previous “Moore-Bellman-Ford-like” algorithms, to be of independent interest and discuss it in depth. In our tree embedding algorithm, we leverage it to provide efficient query access to an approximate metric that allows sampling the tree using polylog n depth and Õ( m ) work. We illustrate the generality and versatility of our techniques by various examples and a number of additional results. Specifically, we (1) improve the state of the art for determining metric tree embeddings in the Congest model, (2) determine a (1 + εˆ)-approximate metric regarding the distances in a graph G in polylogarithmic depth and Õ( n ( m + n 1 + ε )) work, and (3) improve upon the state of the art regarding the k -median and the buy-at-bulk network design problems.

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. The development of the algorithm entails two subresults of independent interest: (i) A $(D+\sqrt{n})\cdot n^{o(1)}$-round distributed construction of a spanning tree of average stretch $n^{o(1)}$. (ii) A $(D+\sqrt{n})\cdot n^{o(1)}$-round distributed construction of an $n^{o(1)}$-congestion approximator consisting of the cuts induced by $O(\log n)$ virtual trees. The distributed representation of the cut approximator allows for evaluation in $(D+\sqrt{n})\cdot n^{o(1)}$ rounds. All our algorithms make use of randomization and succeed with high probability.

In digital circuits, metastability can cause deteriorated signals that neither are logical 0 nor logical 1, breaking the abstraction of Boolean logic. Synchronizers, the only traditional countermeasure, exponentially decrease the odds of maintained metastability overtime. We propose a fundamentally different approach: It is possible to deterministically contain metastability by fine-grained logical masking so that it cannot infect the entire circuit. At the heart of our approach lies a time- and value-discrete model for metastability in synchronous clocked digital circuits, in which metastability is propagated in a worst-case fashion. The proposed model permits positive results and passes the test of reproducing Marino's impossibility results. We fully classify which functions can be computed by circuits with standard registers. Regarding masking registers, we show that more functions become computable with each clock cycle, and that masking registers permit exponentially smaller circuits for some tasks. Demonstrating the applicability of our approach, we present the first fault-tolerant distributed clock synchronization algorithm that deterministically guarantees correct behavior in the presence of metastability. As a consequence, clock domains can be synchronized without using synchronizers, enabling metastability-free communication between them.

Metastability in digital circuits is a spurious mode of operation induced by violation of setup/hold times of stateful components. It cannot be avoided deterministically when transitioning from continuously-valued to (discrete) binary signals. However, in prior work (Lenzen & Medina ASYNC 2016) it has been shown that it is possible to fully and deterministically contain the effect of metastability in sorting networks. More specifically, the sorting operation incurs no loss of precision, i.e., any inaccuracy of the output originates from mapping the continuous input range to a finite domain. The downside of this prior result is inefficiency: for B-bit inputs, the circuit for a single comparison contains Θ(B2) gates and has depth Θ(B). In this work, we present an improved solution with near-optimal Θ(B log B) gates and asymptotically optimal Θ(log B) depth. On the practical side, our sorting networks improves over prior work for all input lengths B > 2, e.g., for 16-bit inputs we present an improvement of more than 70% in depth of the sorting network and more than 60% in cost of the sorting network.

We present a method for solving the shortest transshipment problem-also known as uncapacitated minimum cost flow-up to a multiplicative error of 1 + ε in undirected graphs with non-negative integer edge weights using a tailored gradient descent algorithm. Our gradient descent algorithm takes ε-3 polylog n iterations, and in each iteration it needs to solve an instance of the transshipment problem up to a multiplicative error of polylog n, where n is the number of nodes. In particular, this allows us to perform a single iteration by computing a solution on a sparse spanner of logarithmic stretch. Using a careful white-box analysis, we can further extend the method to finding approximate solutions for the single-source shortest paths (SSSP) problem. As a consequence, we improve prior work by obtaining the following results: 1. Broadcast CONGEST model: (1+")-approximate SSSP using Õ((√ n+D) · ε-O(1)) rounds, 1 where D is the (hop) diameter of the network. 2. Broadcast congested clique model: (1+ε)-approximate shortest transshipment and SSSP using Õ (ε-O(1)) rounds. 3. Multipass streaming model: (1+ε)-approximate shortest transshipment and SSSP using Õ (n) space and Õ(ε-O(1)) passes. The previously fastest SSSP algorithms for these models leverage sparse hop sets. We bypass the hop set construction; computing a spanner is sufficient with our method. The above bounds assume non-negative integer edge weights that are polynomially bounded in n; for general nonnegative weights, running times scale with the logarithm of the maximum ratio between non-zero weights. In case of asymmetric costs for traversing an edge in opposite directions, running times scale with the maximum ratio between the costs of both directions over all edges.

Constructing a sparse 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.e., spanning trees, cannot be constructed efficiently in this model. Therefore, we settle for a spanning subgraph containing at most (1+epsilon)n edges (where n is the number of vertices and epsilon is a given approximation/sparsity parameter). We achieve a query complexity of O~(poly(Delta/epsilon)n^{2/3}), where Delta is the maximum degree of the input graph. Our algorithm is the first to do so on arbitrary bounded degree graphs. Moreover, we achieve the additional property that our algorithm outputs a spanning subgraph of bounded stretch i.e., distances are approximately preserved. With high probability, for each deleted edge there is a path of O(log n * (Delta+log n)/epsilon) hops in the output that connects its endpoints.

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 behavior, 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-stabilizing despite Byzantine failures. In this work, we give new algorithms for the synchronous counting problem that (1) are deterministic, (2) have optimal resilience, (3) have a linear stabilization time in $f$ (asymptotically optimal), (4) use a small number of states, and, consequently, (5) communicate a small number of bits per round. Prior algorithms either resort to randomization, use a large number of states and need high communication bandwidth, or have suboptimal resilience. In particular, we achieve an exponential improvement in both state complexity and message size for deterministic algorithms. Moreover, we present two complementary approaches for reducing the number of bits communicated during and after stabilization.

A metric tree embedding of expected stretch α maps a weighted n-node graph G = (V, E, w) to a weighted tree T = (VT, ET, wT) with V ⊆ VT, and dist(v, w, G) ≤ dist(v, w, T) and E[dist(v, w, T)] ≤ α dist(v, w, G) for all v, w ∈ V. 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 polylog n depth algorithm that achieves an asymptotically optimal expected stretch of α ∈ Ω(log n) uses Ω(n2) work and requires a metric as input.

We argue that a hexagonal grid with simple intermediate nodes is a robust alternative to buffered clock trees typically used for clock distribution in VLSI circuits, multi-core processors, and other applications that require accurate synchronization: Our HEX grid is Byzantine fault-tolerant, 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 a very small average skew.

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). This novel ranking mechanism results in notable improvements, in particular in the number of balls that may commit to a bin in the first round of the algorithm. Simulations independently verify the correctness of the results and confirm that our approximation is highly accurate even for a moderate number of 106 balls and bins.

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(n1-2/ω) round matrix multiplication algorithm, where ω < 2.3728639 is the exponent of matrix multiplication. In conjunction with known techniques from centralised algorithmics, this gives significant improvements over previous best upper bounds in the congested clique model. The highlight results include: triangle and 4-cycle counting in O(n0.158) rounds, improving upon the O(n1/3) triangle counting algorithm of Dolev et al. [DISC 2012], a (1 + o(1))-approximation of all-pairs shortest paths in O(n0.158) rounds, improving upon the ~O (n1/2)-round (2 + o(1))-approximation algorithm of Nanongkai [STOC 2014], and computing the girth in O(n0.158) rounds, which is the first non-trivial solution in this model. In addition, we present a novel constant-round combinatorial algorithm for detecting 4-cycles.

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+ √n)⋅ no(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 O(m) time bound, and it nearly matches the Ω(D+√n) round complexity lower bound.

We study approximate distributed solutions to the weighted all-pairs shortest-paths (APSP) problem in the CONGEST model. We obtain the following results. A deterministic (1+epsilon)-approximation to APSP with running time O(ε-2n log n) rounds. The best previously known algorithm was randomized and slower by a Theta(log n) factor. In many cases, routing schemes involve relabeling, i.e., assigning new names to nodes and that are used in distance and routing queries. It is known that relabeling is necessary to achieve running times of o(n log n). In the relabeling model, we obtain the following results. A randomized O(k)-approximation to APSP, for any integer k>1, running in ~O(n1/2+1/k+D) rounds, where D is the hop diameter of the network. This algorithm simplifies the best previously known result and reduces its approximation ratio from O(k log k) to O(k). Also, the new algorithm uses O(log n)-bit labels, which is asymptotically optimal. A randomized O(k)-approximation to APSP, for any integer k>1, running in time ~O((nD)1/2 n1/k+D) and producing compact routing tables of size ~O(n1/k). The node labels consist of O(k log n) bits. This improves on the approximation ratio of Theta(k2) for tables of that size achieved by the best previously known algorithm, which terminates faster, in ~O(n1/2+1/k+D) rounds. In addition, we improve on the time complexity of the best known deterministic algorithm for distributed approximate Steiner forest.

Consider a complete communication network of n nodes, in which 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 count modulo c in agreement. Thus, we are considering algorithms that are self-stabilising despite Byzantine failures. In this work, we give new algorithms for the synchronous counting problem that (1) are deterministic, (2) have linear stabilisation time in f, (3) use a small number of states, and (4) achieve almost-optimal resilience. Prior algorithms either resort to randomisation, use a large number of states, or have poor resilience. In particular, we achieve an exponential improvement in the state complexity of deterministic algorithms, while still achieving linear stabilisation time and almost-linear resilience.

Clock synchronization is an enabling service for a wide range of applications and protocols in both wired and wireless networks. We study the implications of clock drift and communication latency on the accuracy of clock synchronization when scaling the network diameter. Starting with a theoretical analysis of synchronization protocols, we prove tight bounds on the synchronization error in a model that assumes independently and randomly distributed communication delays and slowly changing drifts. While this model is more optimistic than traditional worst-case analysis, it much better captures the nature of real-world systems such as wireless networks. The bound on the synchronization accuracy, which is roughly the square root of the network diameter, is achieved by the novel PulseSync protocol. Extensive experiments demonstrate that PulseSync is able to meet the predictions from theory and tightly synchronizes large networks. This contrasts against an exponential growth of the skew incurred by the state-of-the-art protocol for wireless sensor networks. Moreover, PulseSync adapts much faster to network dynamics and changing clock drifts than this protocol.

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

We argue that in the context of biology-inspired problems in computer science, in addition to studying the time complexity of solutions it is also important to study the selection complexity, a measure of how likely a given algorithmic strategy is to arise in nature. In this spirit, we propose a selection complexity metric χ for the ANTS problem [Feinerman et al.]. For algorithm A, we define χ(A) = b + log l, where b is the number of memory bits used by each agent and l bounds the fineness of available probabilities (agents use probabilities of at least 1/2l). We consider n agents searching for a target in the plane, within an (unknown) distance D from the origin. We identify log log D as a crucial threshold for our selection complexity metric. We prove a new upper bound that achieves near-optimal speed-up of (D2/n +D) ⋅ 2O(l) for χ(A) ≤ 3 log log D + O(1), which is asymptotically optimal if l∈ O(1). By comparison, previous algorithms achieving similar speed-up require χ(A) = Ω(log D). We show that this threshold is tight by proving that if χ(A) < log log D - ω(1), then with high probability the target is not found if each agent performs D2-o(1) moves. This constitutes a sizable gap to the straightforward Ω(D2/n + D) lower bound.

We present new distributed algorithms for constructing a Steiner Forest in the CONGEST model. Our deterministic algorithm finds, for any given constant ε>0, a (2+ε)-approximation in ~O(sk+√{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 ~O(k+min(s,√ n)+D), where D is the unweighted diameter of the network. We also prove a matching lower bound of ~Ω(k+min(s,√n)+D) on the running time of any distributed approximation algorithm for the Steiner Forest problem. Previous algorithms were randomized, and obtained either an O(log n)-approximation in ~O(sk) time, or an O(1/ε)-approximation in O((√n+t)1+ε+D) time.

Today’s hardware technology presents a new challenge in designing robust systems. Deep submicron VLSI technology introduces 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. Distributed systems, on the other hand, have been dealing with similar issues for decades. However, neither the basic abstractions nor the complexity of contemporary fault-tolerant distributed algorithms match the peculiarities of hardware implementations. This article is intended to be part of an attempt striving to bridge over this gap between theory and practice for the clock synchronization problem. Solving this task sufficiently well will allow to build an ultra-robust high-precision clocking system for hardware designs like systems-on-chips in critical applications. As our first building block, we describe and prove correct a novel distributed, Byzantine fault-tolerant, probabilistically self-stabilizing pulse synchronization protocol, called FATAL, that can be implemented using standard asynchronous digital logic: Correct FATAL nodes are guaranteed to generate pulses (i.e., unnumbered clock ticks) in a synchronized way, despite a certain fraction of nodes being faulty. FATAL uses randomization only during stabilization and, despite the strict limitations introduced by hardware designs, offers optimal resilience and smaller complexity than all existing protocols. Finally, we show how to leverage FATAL to efficiently generate synchronized, self-stabilizing, high-frequency clocks.

We present the first implementation of a distributed clock generation scheme for Systems-on-Chip that recovers from an unbounded number of arbitrary transient faults despite a large number of arbitrary permanent faults. We devise self-stabilizing hardware building blocks and a hybrid synchronous/asynchronous state machine enabling metastability-free transitions of the algorithm's states. We provide a comprehensive modeling approach that permits to prove, given correctness of the constructed low-level building blocks, the high-level properties of the synchronization algorithm (which have been established in a more abstract model). We believe this approach to be of interest in its own right, since this is the first technique permitting to mathematically verify, at manageable complexity, high-level properties of a fault-prone system in terms of its very basic components. We evaluate a prototype implementation, which has been designed in VHDL, using the Petrify tool in conjunction with some extensions, and synthesized for an Altera Cyclone FPGA.

In this paper, we show how to build synchronized clocks of arbitrary size atop of existing small-sized clocks, despite arbitrary faults. Our solution is both self-stabilizing and Byzantine fault-tolerant, and needs merely single-bit channels. It involves a reduction to Byzantine fault-tolerant consensus, which allows different consensus algorithms to be plugged in for matching the actual clock sizes and resilience requirements best. We demonstrate the practicability of our approach by means of an FPGA implementation and its experimental evaluation. To also address the cases where deterministic algorithms hit fundamental limits, we provide a novel randomized self-stabilizing Byzantine consensus algorithm that works very well also in these settings, along with its correctness proof and stabilization time analysis.

In consensus, the n nodes of a distributed system seek to take a consistent decision on some output, despite up to t of them crashing or even failing maliciously, i.e., behaving "Byzantine''. It is known that it is impossible to guarantee that synchronous, deterministic algorithms consistently decide on an output in fewer than f+1 rounds in executions in which the actual number of faults is f ≤ t. This even holds if faults are crash-only, and in this case the bound can be matched precisely. However, the question of whether this can be done efficiently, i.e., with little communication, so far has not been addressed.

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). The second is a sorting problem where each node i is given n keys of size O(log n) and needs to receive the ith batch of n keys according to the global order of the keys. The latter result also implies deterministic constant-round solutions for related problems such as selection or determining modes.

Given a simple graph G=(V,E) and a set of sources S ⊆ V, denote for each node ν ε V by Lν(∞) the lexicographically ordered list of distance/source pairs (d(s,v),s), where s ∈ S. For integers d,k ∈ N∪{∞}, we consider the source detection, or (S,d,k)-detection task, requiring each node v to learn the first k entries of Lν(∞) (if for all of them d(s,v) ≤ d) or all entries (d(s,v),s) ∈ Lν(∞) satisfying that d(s,v) ≤ d (otherwise). Solutions to this problem provide natural generalizations of concurrent breadth-first search (BFS) tree constructions. For example, the special case of k=∞ requires each source s ∈ S to build a complete BFS tree rooted at s, whereas the special case of d=∞ and S=V requires constructing a partial BFS tree comprising at least k nodes from every node in V.

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.

We describe a distributed randomized algorithm to construct routing tables. Given 0< ε <= 1/2, the algorithm runs in time ~O(n1/2+ε + HD), where n is the number of nodes and HD denotes the diameter of the network in hops (i.e., as if the network is unweighted). The weighted length of the produced routes is at most O(ε-1log ε-1) times the optimal weighted length. This is the first algorithm to break the Omega(n) complexity barrier for computing weighted shortest paths even for a single source. Moreover, the algorithm nearly meets the ~Omega(n1/2 + HD) lower bound for distributed computation of routing tables and approximate distances (with optimality, up to polylog factors, for ε=1/log n). The presented techniques have many applications, including improved distributed approximation algorithms for Generalized Steiner Forest, all-pairs distance estimation, and estimation of the weighted diameter.

A maximal independent set on a graph is an inclusion-maximal set of mutually non-adjacent nodes. This basic symmetry breaking structure is vital for many distributed algorithms, which by now has been fueling the search for fast local algorithms to find such sets over several decades. In this paper, we present a solution with randomized running time O(√log n log log n) on trees, improving roughly quadratically on the state-of-the-art bound. Our algorithm is uniform and nodes need to exchange merely O(log n) many bits with high probability. In contrast to previous techniques achieving sublogarithmic running times, our approach does not rely on any bound on the number of independent neighbors (possibly with regard to an orientation of the edges).

We explore the fundamental limits of distributed balls-into-bins algorithms, i.e., algorithms where balls act in parallel, as separate agents. This problem was introduced by Adler et al., who showed that non-adaptive and symmetric algorithms cannot reliably perform better than a maximum bin load of Theta(log log n / log log log n) within the same number of rounds. 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. Moreover, larger bin loads can be traded in for smaller time complexities. We prove a matching lower bound of (1-o(1))log* n on the time complexity of symmetric algorithms that guarantee small bin loads at an asymptotically optimal message complexity of O(n). The essential preconditions of the proof are (i) a limit of O(n) on the total number of messages sent by the algorithm and (ii) anonymity of bins, i.e., the port numberings of balls are not globally consistent. In order to show that our technique yields indeed tight bounds, we provide for each assumption an algorithm violating it, in turn achieving a constant maximum bin load in constant time.

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. This property is called gradient clock synchronization.

We demonstrate how to leverage a system's capability for all-to-all communication to achieve an exponential speed-up of local algorithms despite bandwidth and memory restrictions. More precisely, if a network comprises n nodes with all-to-all bandwidth nε (ε > 0 constant) and nodes know their input and neighborhood with respect to a graph problem instance of polylogarithmic maximum degree, any local algorithm for this problem with running time r ∈ O(log n) and reasonably small states can be simulated within O(log r) rounds.

We present a novel clock synchronization algorithm and prove tight upper and lower bounds on the worst-case clock skew that may occur between any two participants in any given distributed system. More importantly, the worst-case clock skew between neighboring nodes is (asymptotically) at most a factor of two larger than the best possible bound. While previous results solely focused on the dependency of the skew bounds on the network diameter, we prove that our techniques are optimal also with respect to the maximum clock drift, the uncertainty in message delays, and the imposed bounds on the clock rates. The presented results all hold in a general model where both the clock drifts and the message delays may vary arbitrarily within pre-specified bounds. Furthermore, our algorithm exhibits a number of other highly desirable properties. First, the algorithm ensures that the clock values remain in an affine linear envelope of real time. A better worst-case bound on the accuracy with respect to real time cannot be achieved in the absence of an external timer. Second, the algorithm minimizes the number and size of messages that need to be exchanged in a given time period. Moreover, only a small number of bits must be stored locally for each neighbor. Finally, our algorithm can easily be adapted for a variety of other prominent synchronization models.

We present a novel clock synchronization algorithm and prove tight upper and lower bounds on the worst-case clock skew that may occur between any two participants in any given distributed system. More importantly, the worst-case clock skew between neighboring nodes is (asymptotically) at most a factor of two larger than the best possible bound. While previous results solely focused on the dependency of the skew bounds on the network diameter, we prove that our techniques are optimal also with respect to the maximum clock drift, the uncertainty in message delays, and the imposed bounds on the clock rates. The presented results all hold in a general model where both the clock drifts and the message delays may vary arbitrarily within pre-specified bounds.

Having access to an accurate time is a vital building block in all networks; in wireless sensor networks even more so, because wireless media access or data fusion may depend on it. Starting out with a novel analysis, we show that orthodox clock synchronization algorithms make fundamental mistakes. The state-of-the-art clock synchronization algorithm FTSP exhibits an error that grows exponentially with the size of the network, for instance. Since the involved parameters are small, the error only becomes visible in midsize networks of about 10--20 nodes. In contrast, we present PulseSync, a new clock synchronization algorithm that is asymptotically optimal. We evaluate PulseSync on a Mica2 testbed, and by simulation on larger networks. On a 20 node network, the prototype implementation of PulseSync outperforms FTSP by a factor of 5. Theory and simulation show that for larger networks, PulseSync offers an accuracy which is several orders of magnitude better than FTSP. To round off the presentation, we investigate several optimization issues, e.g. media access and local skew.

We present a distributed clock synchronization algorithm that guarantees an exponentially improved bound of O(log D) on the clock skew between neighboring nodes in any graph G of diameter D. In light of the lower bound of Omega(log D/ log log D), this result is almost tight. Moreover, the global clock skew between any two nodes, particularly nodes that are not directly connected, is bounded by O(D), which is optimal up to a constant factor. Our algorithm further ensures that the clock values are always within a linear envelope of real time. A better bound on the accuracy with respect to real time cannot be achieved in the absence of an external timer. These results all hold in a general model where both the clock drifts and the message delays may vary arbitrarily within pre-specified bounds.

Whether local algorithms can compute constant approximations of NP-hard problems is of both practical and theoretical interest. So far, no algorithms achieving this goal are known, as either the approximation ratio or the running time exceed O(1), or the nodes are provided with non-trivial additional information. In this paper, we present the first distributed algorithm approximating a minimum dominating set on a planar graph within a constant factor in constant time. Moreover, the nodes do not need any additional information.