Search Results

Documents authored by Lenzen, Christoph

Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2024.51
Brief Announcement: Clock Distribution with Gradient TRIX

Authors: Christoph Lenzen and Shreyas Srinivas

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
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.
Cite as

Christoph Lenzen and Shreyas Srinivas. Brief Announcement: Clock Distribution with Gradient TRIX. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 51:1-51:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lenzen_et_al:LIPIcs.DISC.2024.51,
  author =	{Lenzen, Christoph and Srinivas, Shreyas},
  title =	{{Brief Announcement: Clock Distribution with Gradient TRIX}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{51:1--51:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.51},
  URN =		{urn:nbn:de:0030-drops-212791},
  doi =		{10.4230/LIPIcs.DISC.2024.51},
  annote =	{Keywords: local skew, gradient clock synchronisation, average-case fault-tolerance, self-stabilisation, Systems-on-Chip}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.6
Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts

Authors: Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic, and Themis Gouleakis

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
In this paper, we refine the (almost) existentially optimal distributed Laplacian solver recently developed by 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 SQ(G) can be solved after n^{o(1)} SQ(G) log(1/ε) rounds, where ε is the required accuracy. This almost matches our lower bound that guarantees that any correct algorithm on G requires Ω̃(SQ(G)) rounds, even for a crude solution with ε ≤ 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 ⋅ n^{o(1)} log(1/ε) rounds, where D is the hop-diameter of the network; as well as n^{o(1)} log (1/ε)-round algorithms for the case of SQ(G) ≤ n^{o(1)}, which holds for most networks of interest. Conditioned on improvements in state-of-the-art constructions of low-congestion shortcuts, the CONGEST results will match the Supported-CONGEST ones. 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 clique (NCC) model. In this model, we show the existence of a Laplacian solver with round complexity n^{o(1)} log(1/ε). The unifying thread of these results, and our main technical contribution, is the study of a novel ρ-congested generalization of the standard part-wise aggregation problem. We develop near-optimal algorithms for this primitive in the Supported-CONGEST model, almost-optimal algorithms in (standard) CONGEST (with the additional overhead due to standard barriers), as well as a simple algorithm for bounded-treewidth graphs with a quadratic dependence on the congestion ρ. This primitive can be readily used to accelerate the Laplacian solver of Forster, Goranci, Liu, Peng, Sun, and Ye, and we believe it will find further independent applications in the future.
Cite as

Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic, and Themis Gouleakis. Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{anagnostides_et_al:LIPIcs.DISC.2022.6,
  author =	{Anagnostides, Ioannis and Lenzen, Christoph and Haeupler, Bernhard and Zuzic, Goran and Gouleakis, Themis},
  title =	{{Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{6:1--6:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.6},
  URN =		{urn:nbn:de:0030-drops-171978},
  doi =		{10.4230/LIPIcs.DISC.2022.6},
  annote =	{Keywords: Distributed algorithms, Laplacian solvers, low-congestion shortcuts}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.32
Small Hazard-Free Transducers

Authors: Johannes Bund, Christoph Lenzen, and Moti Medina

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
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.
Cite as

Johannes Bund, Christoph Lenzen, and Moti Medina. Small Hazard-Free Transducers. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 32:1-32:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bund_et_al:LIPIcs.ITCS.2022.32,
  author =	{Bund, Johannes and Lenzen, Christoph and Medina, Moti},
  title =	{{Small Hazard-Free Transducers}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{32:1--32:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.32},
  URN =		{urn:nbn:de:0030-drops-156281},
  doi =		{10.4230/LIPIcs.ITCS.2022.32},
  annote =	{Keywords: Hazard-Freeness, Parallel Prefix Computation, Finite State Transducers}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.50
Low Diameter Graph Decompositions by Approximate Distance Computation

Authors: Ruben Becker, Yuval Emek, and Christoph Lenzen

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
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.
Cite as

Ruben Becker, Yuval Emek, and Christoph Lenzen. Low Diameter Graph Decompositions by Approximate Distance Computation. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 50:1-50:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.ITCS.2020.50,
  author =	{Becker, Ruben and Emek, Yuval and Lenzen, Christoph},
  title =	{{Low Diameter Graph Decompositions by Approximate Distance Computation}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{50:1--50:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.50},
  URN =		{urn:nbn:de:0030-drops-117355},
  doi =		{10.4230/LIPIcs.ITCS.2020.50},
  annote =	{Keywords: graph decompositions, metric tree embeddings, distributed graph algorithms, parallel graph algorithms, (semi-)streaming graph algorithms}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.4
Distributed Algorithms for Low Stretch Spanning Trees

Authors: Ruben Becker, Yuval Emek, Mohsen Ghaffari, and Christoph Lenzen

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
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.
Cite as

Ruben Becker, Yuval Emek, Mohsen Ghaffari, and Christoph Lenzen. Distributed Algorithms for Low Stretch Spanning Trees. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.DISC.2019.4,
  author =	{Becker, Ruben and Emek, Yuval and Ghaffari, Mohsen and Lenzen, Christoph},
  title =	{{Distributed Algorithms for Low Stretch Spanning Trees}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.4},
  URN =		{urn:nbn:de:0030-drops-113116},
  doi =		{10.4230/LIPIcs.DISC.2019.4},
  annote =	{Keywords: distributed graph algorithms, low-stretch spanning trees, CONGEST model, ball decomposition, star decomposition}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.87
A Centralized Local Algorithm for the Sparse Spanning Graph Problem

Authors: Christoph Lenzen and Reut Levi

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
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.
Cite as

Christoph Lenzen and Reut Levi. A Centralized Local Algorithm for the Sparse Spanning Graph Problem. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 87:1-87:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{lenzen_et_al:LIPIcs.ICALP.2018.87,
  author =	{Lenzen, Christoph and Levi, Reut},
  title =	{{A Centralized Local Algorithm for the Sparse Spanning Graph Problem}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{87:1--87:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.87},
  URN =		{urn:nbn:de:0030-drops-90919},
  doi =		{10.4230/LIPIcs.ICALP.2018.87},
  annote =	{Keywords: local, spanning graph, sparse}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.7
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models

Authors: Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
We present a method for solving the shortest transshipment problem - also known as uncapacitated minimum cost flow - up to a multiplicative error of (1 + epsilon) in undirected graphs with non-negative integer edge weights using a tailored gradient descent algorithm. Our gradient descent algorithm takes epsilon^(-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 + epsilon)-approximate SSSP using ~O((sqrt(n) + D) epsilon^(-O(1))) rounds, where D is the (hop) diameter of the network. (2) Broadcast congested clique model: (1 + epsilon)-approximate shortest transshipment and SSSP using ~O(epsilon^(-O(1))) rounds. (3) Multipass streaming model: (1 + epsilon)-approximate shortest transshipment and SSSP using ~O(n) space and ~O(epsilon^(-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 non-negative 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.
Cite as

Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.DISC.2017.7,
  author =	{Becker, Ruben and Karrenbauer, Andreas and Krinninger, Sebastian and Lenzen, Christoph},
  title =	{{Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.7},
  URN =		{urn:nbn:de:0030-drops-80031},
  doi =		{10.4230/LIPIcs.DISC.2017.7},
  annote =	{Keywords: Shortest Paths, Shortest Transshipment, Undirected Min-cost Flow, Gradient Descent, Spanner}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.32
Self-Stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus

Authors: Christoph Lenzen and Joel Rybicki

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
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 Theta(f) and have each node broadcast Theta(f log f) bits per time unit. We exponentially reduce the number of bits broadcasted per time unit to Theta(log f) while retaining the same stabilisation time. - In the randomised setting, the state-of-the-art solutions stabilise in time Theta(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.
Cite as

Christoph Lenzen and Joel Rybicki. Self-Stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{lenzen_et_al:LIPIcs.DISC.2017.32,
  author =	{Lenzen, Christoph and Rybicki, Joel},
  title =	{{Self-Stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{32:1--32:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.32},
  URN =		{urn:nbn:de:0030-drops-79914},
  doi =		{10.4230/LIPIcs.DISC.2017.32},
  annote =	{Keywords: Byzantine faults, self-stabilisation, clock synchronisation, consensus}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2017.57
Brief Announcement: A Centralized Local Algorithm for the Sparse Spanning Graph Problem

Authors: Christoph Lenzen and Reut Levi

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
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)) (up to polylogarithmic factors in n) 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 spanner, 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.
Cite as

Christoph Lenzen and Reut Levi. Brief Announcement: A Centralized Local Algorithm for the Sparse Spanning Graph Problem. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 57:1-57:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{lenzen_et_al:LIPIcs.DISC.2017.57,
  author =	{Lenzen, Christoph and Levi, Reut},
  title =	{{Brief Announcement: A Centralized Local Algorithm for the Sparse Spanning Graph Problem}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{57:1--57:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.57},
  URN =		{urn:nbn:de:0030-drops-80064},
  doi =		{10.4230/LIPIcs.DISC.2017.57},
  annote =	{Keywords: local, spanning graph, sparse}
}
Document
DOI: 10.4230/DagSemProc.09371.3
Local Algorithms: Self-Stabilization on Speed

Authors: Christoph Lenzen, Jukka Suomela, and Roger Wattenhofer

Published in: Dagstuhl Seminar Proceedings, Volume 9371, Algorithmic Methods for Distributed Cooperative Systems (2010)

Abstract
An introduction to distributed algorithms, in particular local algorithms. Essentially a practice talk of my SSS 2009 invited talk.
Cite as

Christoph Lenzen, Jukka Suomela, and Roger Wattenhofer. Local Algorithms: Self-Stabilization on Speed. In Algorithmic Methods for Distributed Cooperative Systems. Dagstuhl Seminar Proceedings, Volume 9371, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{lenzen_et_al:DagSemProc.09371.3,
  author =	{Lenzen, Christoph and Suomela, Jukka and Wattenhofer, Roger},
  title =	{{Local Algorithms: Self-Stabilization on Speed}},
  booktitle =	{Algorithmic Methods for Distributed Cooperative Systems},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9371},
  editor =	{S\'{a}ndor Fekete and Stefan Fischer and Martin Riedmiller and Suri Subhash},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09371.3},
  URN =		{urn:nbn:de:0030-drops-24257},
  doi =		{10.4230/DagSemProc.09371.3},
  annote =	{Keywords: Local Algorithms, Self-Stabilization, Lower Bounds, Upper Bounds, MIS}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact