Volume
LIPIcs, Volume 246
36th International Symposium on Distributed Computing (DISC 2022)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC)
Publication Details
- published at: 2022-10-17
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-255-6
- DBLP: db/conf/wdag/disc2022
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
LIPIcs, Volume 246, DISC 2022, Complete Volume
Abstract
LIPIcs, Volume 246, DISC 2022, Complete Volume
Cite as
36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 1-790, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@Proceedings{scheideler:LIPIcs.DISC.2022,
title = {{LIPIcs, Volume 246, DISC 2022, Complete Volume}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {1--790},
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},
URN = {urn:nbn:de:0030-drops-171908},
doi = {10.4230/LIPIcs.DISC.2022},
annote = {Keywords: LIPIcs, Volume 246, DISC 2022, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{scheideler:LIPIcs.DISC.2022.0,
author = {Scheideler, Christian},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {0:i--0:xx},
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.0},
URN = {urn:nbn:de:0030-drops-171917},
doi = {10.4230/LIPIcs.DISC.2022.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
Graph Coloring, Palette Sparsification, and Beyond (Invited Talk)
Abstract
Graph coloring is a central problem in graph theory and has numerous applications in diverse areas of computer science. An important and well-studied case of graph coloring problems is the (Δ+1) (vertex) coloring problem where Δ is the maximum degree of the graph. Not only does every graph admit a (Δ + 1) coloring, but in fact we can find one quite easily in linear time and space via a greedy algorithm. But are there more efficient algorithms for (Δ+1) coloring that can process massive graphs that even this algorithm cannot handle?
This talk overviews recent results that answer this question in affirmative across a variety of models dedicated to processing massive graphs - streaming, sublinear-time, massively parallel computation, distributed communication, etc. - via a single unified approach: Palette Sparsification. We survey the ideas behind these results and techniques, their generalizations to various other coloring problems and even beyond (e.g., to clustering problems), as well as their natural limitations.
The talk is based on a series of joint works with Noga Alon, Andrew Chen, Yu Chen, Sanjeev Khanna, Pankaj Kumar, Parth Mittal, Glenn Sun, and Chen Wang.
Cite as
Sepehr Assadi. Graph Coloring, Palette Sparsification, and Beyond (Invited Talk). In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{assadi:LIPIcs.DISC.2022.1,
author = {Assadi, Sepehr},
title = {{Graph Coloring, Palette Sparsification, and Beyond}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {1:1--1:1},
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.1},
URN = {urn:nbn:de:0030-drops-171920},
doi = {10.4230/LIPIcs.DISC.2022.1},
annote = {Keywords: Graph coloring, Palette Sparsification, Sublinear Algorithms}
}
Document
Invited Talk
Managing the Cyber Risk in a Decoupled World: Does This Bring Potential Opportunities in Computer Science? (Invited Talk)
Abstract
The last thirty years witnessed the growth of both globalization and digital transformation, characterized by information systems becoming interconnected and distributed on a worldwide scale with IT aimed to become a commodity. Cloud computing and blockchain being examples of such robust and distributed technologies which have been the main driver of this globalization process. Global technologies and infrastructures paved the way to organic and highly frequent interactions between millions of companies and organizations in multiple countries almost irrespective of geopolitical implications establishing global and complex interconnected supply chains whose aim was mainly keeping software/devices costs low. This created a virtuous loop that generated an exponential increase of countries' digitalization process and globalized industries.
Like energy, IT progressively became a strategic geopolitical factor as the nation’s vital services implementation went digital. As a consequence, governments realized IT cannot be a simple commodity and that they have to manage the cyber risk associated with procured IT in strategic sectors like, for instance, telecommunication, finance and transportation. Governments have to understand and mitigate IT risks coming from these globalized supply chains against operations of potential powerful adversaries. Even a single supply chain dependency can be a risk, also from a national security perspective, when such dependency is established by a provider/vendor under the direct political influence of an untrusted nation or a trusted provider/vendor victim of a state-backed cyber attack. The recent Ukrainian crisis and the large degree of tension between US and China are amplifying risks coming from globalized supply chains in a world that is politically liquid polarizing in at least two blocks.
In addition, the globalization process has shown its natural limits and frailty culminating with the global supply chain crisis created by the effect of the covid-19 pandemic and extreme events due to climate change. Paradoxically, experience shows the main drawback of globalized supply chains is the centralization of certain key manufacturing in restricted geographical areas, this is the case for the infamous chip shortage. This centralization poses risks if a critical portion of these key manufacturing are owned by untrusted actors. A parallel can be seen in the permissionless blockchain technologies based on Proof-of-Work, where the decentralized worldwide spirit has mercilessly converged to a more convenient but weaker almost centralized system which makes it easier for a powerful adversary to take control of the whole blockchain.
The likely trends of the next few years will be a progressive decoupling of supply chains particularly for all software/hardware manufacturing employed into vital services of a nation. This will be a long and non-economically neutral process that will bring in a medium term towards the composition of “friendshoring” or “almost domestic” supply chains where developing robust technologies and algorithms compliant to society values. This is expected to increase the number, the magnitude and complexity of cyber attacks coming from other geopolitical blocks for espionage or terroristic reasons in a continuous hybrid warfare scenario. Computer scientists and engineers will have to cope with the new challenges within this decoupled world. The keynote will be an attempt to shed some light on what this could imply in terms of technology, computing paradigms and nation IT capability.
Cite as
Roberto Baldoni. Managing the Cyber Risk in a Decoupled World: Does This Bring Potential Opportunities in Computer Science? (Invited Talk). In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{baldoni:LIPIcs.DISC.2022.2,
author = {Baldoni, Roberto},
title = {{Managing the Cyber Risk in a Decoupled World: Does This Bring Potential Opportunities in Computer Science?}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {2:1--2:1},
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.2},
URN = {urn:nbn:de:0030-drops-171931},
doi = {10.4230/LIPIcs.DISC.2022.2},
annote = {Keywords: Supply chain decoupling, technology risk, cyber attacks, computing paradigms and methodologies}
}
Document
Invited Talk
Using Linearizable Objects in Randomized Concurrent Programs (Invited Talk)
Abstract
Atomic shared objects, whose operations take place instantaneously, are a powerful technique for designing complex concurrent programs. Since they are not always available, they are typically substituted with software implementations. A prominent condition relating these implementations to their atomic specifications is linearizability, which preserves safety properties of programs using them. However linearizability does not preserve hyper-properties, which include probabilistic guarantees about randomized programs. A more restrictive property, strong linearizability, does preserve hyper-properties but it is impossible to achieve in many situations. In particular, we show that there are no strongly linearizable implementations of multi-writer registers or snapshot objects in message-passing systems. On the other hand, we show that a wide class of linearizable implementations, including well-known ones for registers and snapshots, can be modified to approximate the probabilistic guarantees of randomized programs when using atomic objects. This is joint work with Hagit Attiya and Constantin Enea.
Cite as
Jennifer L. Welch. Using Linearizable Objects in Randomized Concurrent Programs (Invited Talk). In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{welch:LIPIcs.DISC.2022.3,
author = {Welch, Jennifer L.},
title = {{Using Linearizable Objects in Randomized Concurrent Programs}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {3:1--3:1},
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.3},
URN = {urn:nbn:de:0030-drops-171946},
doi = {10.4230/LIPIcs.DISC.2022.3},
annote = {Keywords: Concurrent objects, strong linearizability, impossibility proofs, message-passing systems, randomized algorithms}
}
Document
Good-Case Early-Stopping Latency of Synchronous Byzantine Reliable Broadcast: The Deterministic Case
Abstract
This paper considers the good-case latency of Byzantine Reliable Broadcast (BRB), i.e., the time taken by correct processes to deliver a message when the initial sender is correct, and an essential property for practical distributed systems. Although significant strides have been made in recent years on this question, progress has mainly focused on either asynchronous or randomized algorithms. By contrast, the good-case latency of deterministic synchronous BRB under a majority of Byzantine faults has been little studied. In particular, it was not known whether a good-case latency below the worst-case bound of t+1 rounds could be obtained under a Byzantine majority. In this work, we answer this open question positively and propose a deterministic synchronous Byzantine reliable broadcast that achieves a good-case latency of max(2,t+3-c) rounds, where t is the upper bound on the number of Byzantine processes, and c the number of effectively correct processes.
Cite as
Timothé Albouy, Davide Frey, Michel Raynal, and François Taïani. Good-Case Early-Stopping Latency of Synchronous Byzantine Reliable Broadcast: The Deterministic Case. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{albouy_et_al:LIPIcs.DISC.2022.4,
author = {Albouy, Timoth\'{e} and Frey, Davide and Raynal, Michel and Ta\"{i}ani, Fran\c{c}ois},
title = {{Good-Case Early-Stopping Latency of Synchronous Byzantine Reliable Broadcast: The Deterministic Case}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {4:1--4:22},
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.4},
URN = {urn:nbn:de:0030-drops-171953},
doi = {10.4230/LIPIcs.DISC.2022.4},
annote = {Keywords: Reliable Broadcast, Byzantine Faults, Synchronous Systems, Good-case latency, Deterministic Algorithms}
}
Document
Polynomial-Time Verification and Testing of Implementations of the Snapshot Data Structure
Abstract
We analyze correctness of implementations of the snapshot data structure in terms of linearizability. We show that such implementations can be verified in polynomial time. Additionally, we identify a set of representative executions for testing and show that the correctness of each of these executions can be validated in linear time. These results present a significant speedup considering that verifying linearizability of implementations of concurrent data structures, in general, is EXPSPACE-complete in the number of program-states, and testing linearizability is NP-complete in the length of the tested execution. The crux of our approach is identifying a class of executions, which we call simple, such that a snapshot implementation is linearizable if and only if all of its simple executions are linearizable. We then divide all possible non-linearizable simple executions into three categories and construct a small automaton that recognizes each category. We describe two implementations (one for verification and one for testing) of an automata-based approach that we develop based on this result and an evaluation that demonstrates significant improvements over existing tools. For verification, we show that restricting a state-of-the-art tool to analyzing only simple executions saves resources and allows the analysis of more complex cases. Specifically, restricting attention to simple executions finds bugs in 27 instances, whereas, without this restriction, we were only able to find 14 of the 30 bugs in the instances we examined. We also show that our technique accelerates testing performance significantly. Specifically, our implementation solves the complete set of 900 problems we generated, whereas the state-of-the-art linearizability testing tool solves only 554 problems.
Cite as
Gal Amram, Avi Hayoun, Lior Mizrahi, and Gera Weiss. Polynomial-Time Verification and Testing of Implementations of the Snapshot Data Structure. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{amram_et_al:LIPIcs.DISC.2022.5,
author = {Amram, Gal and Hayoun, Avi and Mizrahi, Lior and Weiss, Gera},
title = {{Polynomial-Time Verification and Testing of Implementations of the Snapshot Data Structure}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {5:1--5: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.5},
URN = {urn:nbn:de:0030-drops-171964},
doi = {10.4230/LIPIcs.DISC.2022.5},
annote = {Keywords: Snapshot, Linearizability, Verification, Formal Methods}
}
Document
Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts
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
Byzantine Connectivity Testing in the Congested Clique
Abstract
We initiate the study of distributed graph algorithms under the presence of Byzantine nodes. We consider the fundamental problem of testing the connectivity of a graph in the congested clique model in a Byzantine setting. We are given a n-vertex (arbitrary) graph G embedded in a n-node congested clique where an arbitrary subset of B nodes of the clique of size up to (1/3-ε)n (for any arbitrary small constant ε > 0) can be Byzantine. We consider the full information model where Byzantine nodes can behave arbitrarily, collude with each other, and have unlimited computational power and full knowledge of the states and actions of the honest nodes, including random choices made up to the current round.
Our main result is an efficient randomized distributed algorithm that is able to correctly distinguish between two contrasting cases: (1) the graph G⧵ B (i.e., the graph induced by the removal of the vertices assigned to the Byzantine nodes in the clique) is connected or (2) the graph G is far from connected, i.e., it has at least 2|B|+1 connected components. Our algorithm runs in O(polylog n) rounds in the congested clique model and guarantees that all honest nodes will decide on the correct case with high probability. Since Byzantine nodes can lie about the vertices assigned to them, we show that this is essentially the best possible that can be done by any algorithm. Our result can be viewed also in the spirit of property testing, where our algorithm is able to distinguish between two contrasting cases while giving no guarantees if the graph falls in the grey area (i.e., neither of the cases occur).
Our work is a step towards robust and secure distributed graph computation that can output meaningful results even in the presence of a large number of faulty or malicious nodes.
Cite as
John Augustine, Anisur Rahaman Molla, Gopal Pandurangan, and Yadu Vasudev. Byzantine Connectivity Testing in the Congested Clique. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{augustine_et_al:LIPIcs.DISC.2022.7,
author = {Augustine, John and Molla, Anisur Rahaman and Pandurangan, Gopal and Vasudev, Yadu},
title = {{Byzantine Connectivity Testing in the Congested Clique}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {7:1--7:21},
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.7},
URN = {urn:nbn:de:0030-drops-171987},
doi = {10.4230/LIPIcs.DISC.2022.7},
annote = {Keywords: Byzantine protocols, distributed graph algorithms, congested clique, graph connectivity, fault-tolerant computation, randomized algorithms}
}
Document
Efficient Classification of Locally Checkable Problems in Regular Trees
Abstract
We give practical, efficient algorithms that automatically determine the asymptotic distributed round complexity of a given locally checkable graph problem in the [Θ(log n), Θ(n)] region, in two settings. We present one algorithm for unrooted regular trees and another algorithm for rooted regular trees. The algorithms take the description of a locally checkable labeling problem as input, and the running time is polynomial in the size of the problem description. The algorithms decide if the problem is solvable in O(log n) rounds. If not, it is known that the complexity has to be Θ(n^{1/k}) for some k = 1, 2, ..., and in this case the algorithms also output the right value of the exponent k.
In rooted trees in the O(log n) case we can then further determine the exact complexity class by using algorithms from prior work; for unrooted trees the more fine-grained classification in the O(log n) region remains an open question.
Cite as
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, and Jukka Suomela. Efficient Classification of Locally Checkable Problems in Regular Trees. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{balliu_et_al:LIPIcs.DISC.2022.8,
author = {Balliu, Alkida and Brandt, Sebastian and Chang, Yi-Jun and Olivetti, Dennis and Studen\'{y}, Jan and Suomela, Jukka},
title = {{Efficient Classification of Locally Checkable Problems in Regular Trees}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {8:1--8:19},
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.8},
URN = {urn:nbn:de:0030-drops-171993},
doi = {10.4230/LIPIcs.DISC.2022.8},
annote = {Keywords: locally checkable labeling, locality, distributed computational complexity}
}
Document
Exponential Speedup over Locality in MPC with Optimal Memory
Abstract
Locally Checkable Labeling (LCL) problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example problems in this class include maximal matching, maximal independent set, and coloring problems. A successful line of research has been studying the complexities of LCL problems on paths/cycles, trees, and general graphs, providing many interesting results for the LOCAL model of distributed computing. In this work, we initiate the study of LCL problems in the low-space Massively Parallel Computation (MPC) model. In particular, on forests, we provide a method that, given the complexity of an LCL problem in the LOCAL model, automatically provides an exponentially faster algorithm for the low-space MPC setting that uses optimal global memory, that is, truly linear.
While restricting to forests may seem to weaken the result, we emphasize that all known (conditional) lower bounds for the MPC setting are obtained by lifting lower bounds obtained in the distributed setting in tree-like networks (either forests or high girth graphs), and hence the problems that we study are challenging already on forests. Moreover, the most important technical feature of our algorithms is that they use optimal global memory, that is, memory linear in the number of edges of the graph. In contrast, most of the state-of-the-art algorithms use more than linear global memory. Further, they typically start with a dense graph, sparsify it, and then solve the problem on the residual graph, exploiting the relative increase in global memory. On forests, this is not possible, because the given graph is already as sparse as it can be, and using optimal memory requires new solutions.
Cite as
Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, and Jara Uitto. Exponential Speedup over Locality in MPC with Optimal Memory. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{balliu_et_al:LIPIcs.DISC.2022.9,
author = {Balliu, Alkida and Brandt, Sebastian and Fischer, Manuela and Latypov, Rustam and Maus, Yannic and Olivetti, Dennis and Uitto, Jara},
title = {{Exponential Speedup over Locality in MPC with Optimal Memory}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {9:1--9:21},
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.9},
URN = {urn:nbn:de:0030-drops-172003},
doi = {10.4230/LIPIcs.DISC.2022.9},
annote = {Keywords: Distributed computing, Locally checkable labeling problems, Trees, Massively Parallel Computation, Sublinear memory}
}
Document
Holistic Verification of Blockchain Consensus
Abstract
Blockchain has recently attracted the attention of the industry due, in part, to its ability to automate asset transfers. It requires distributed participants to reach a consensus on a block despite the presence of malicious (a.k.a. Byzantine) participants. Malicious participants exploit regularly weaknesses of these blockchain consensus algorithms, with sometimes devastating consequences. In fact, these weaknesses are quite common and are well illustrated by the flaws in various blockchain consensus algorithms [Pierre Tholoniat and Vincent Gramoli, 2019]. Paradoxically, until now, no blockchain consensus has been holistically verified.
In this paper, we remedy this paradox by model checking for the first time a blockchain consensus used in industry. We propose a holistic approach to verify the consensus algorithm of the Red Belly Blockchain [Tyler Crain et al., 2021], for any number n of processes and any number f < n/3 of Byzantine processes. We decompose directly the algorithm pseudocode in two parts - an inner broadcast algorithm and an outer decision algorithm - each modelled as a threshold automaton [Igor Konnov et al., 2017], and we formalize their expected properties in linear-time temporal logic. We then automatically check the inner broadcasting algorithm, under a carefully identified fairness assumption. For the verification of the outer algorithm, we simplify the model of the inner algorithm by relying on its proven properties. Doing so, we formally verify, for any parameter, not only the safety properties of the Red Belly Blockchain consensus but also its liveness in less than 70 seconds.
Cite as
Nathalie Bertrand, Vincent Gramoli, Igor Konnov, Marijana Lazić, Pierre Tholoniat, and Josef Widder. Holistic Verification of Blockchain Consensus. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 10:1-10:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{bertrand_et_al:LIPIcs.DISC.2022.10,
author = {Bertrand, Nathalie and Gramoli, Vincent and Konnov, Igor and Lazi\'{c}, Marijana and Tholoniat, Pierre and Widder, Josef},
title = {{Holistic Verification of Blockchain Consensus}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {10:1--10:24},
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.10},
URN = {urn:nbn:de:0030-drops-172019},
doi = {10.4230/LIPIcs.DISC.2022.10},
annote = {Keywords: Model checking, automata, logic, byzantine failure}
}
Document
How to Meet at a Node of Any Connected Graph
Abstract
Two mobile agents have to meet at the same node of a connected graph with unlabeled nodes. This intensely researched task is known as rendezvous. The adversary assigns the agents different starting nodes in the graph and different integer labels from a set {1,… ,L}. Time is slotted in synchronous rounds. The adversary wakes up the agents in possibly different rounds. After wakeup, the agents move as follows. In each round, an agent can either stay idle or move to an adjacent node. Each agent knows its label but not the label of the other agent, and agents have no a priori information about the graph. They do not know L. They execute the same deterministic algorithm whose parameter is the agent’s label. The time of a rendezvous algorithm is the worst-case number of rounds since the wakeup of the earlier agent till the meeting.
In most of the results concerning rendezvous in graphs, the graph is finite and rendezvous relies on the exploration of the entire graph. Thus the time of rendezvous depends on the size of the graph. This approach is inefficient for very large graphs, and cannot be used for infinite graphs. For such graphs it is natural to seek rendezvous algorithms whose time depends on the initial distance D between the agents. In this paper we adopt this approach and consider rendezvous in arbitrary connected graphs with nodes of finite degrees, and whose set of nodes is finite or countably infinite. Our main result is the first deterministic rendezvous algorithm working under this general scenario.
For any node v and any positive integer r, let P(v,r) be the number of paths of length r in the graph, starting at node v. For any instance of the rendezvous problem where agents start at nodes v₁ and v₂ at distance D, let P(v₁,v₂,D) = max(P(v₁,D),P(v₂,D)). It is well known that, for example in trees, Ω(D+P(v₁,v₂,D) +log L) is a lower bound on rendezvous time for such an instance. The time of our algorithm, working for arbitrary connected graphs of finite degrees, is polynomial in this lower bound.
As an application we solve the problem of approach for synchronous agents in terrains in the plane, in time polynomial in log L and in the initial distance between the agents in the terrain.
Cite as
Subhash Bhagat and Andrzej Pelc. How to Meet at a Node of Any Connected Graph. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{bhagat_et_al:LIPIcs.DISC.2022.11,
author = {Bhagat, Subhash and Pelc, Andrzej},
title = {{How to Meet at a Node of Any Connected Graph}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {11:1--11:16},
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.11},
URN = {urn:nbn:de:0030-drops-172024},
doi = {10.4230/LIPIcs.DISC.2022.11},
annote = {Keywords: Algorithm, graph, rendezvous, mobile agent, terrain}
}
Document
Liveness and Latency of Byzantine State-Machine Replication
Abstract
Byzantine state-machine replication (SMR) ensures the consistency of replicated state in the presence of malicious replicas and lies at the heart of the modern blockchain technology. Byzantine SMR protocols often guarantee safety under all circumstances and liveness only under synchrony. However, guaranteeing liveness even under this assumption is nontrivial. So far we have lacked systematic ways of incorporating liveness mechanisms into Byzantine SMR protocols, which often led to subtle bugs. To close this gap, we introduce a modular framework to facilitate the design of provably live and efficient Byzantine SMR protocols. Our framework relies on a view abstraction generated by a special SMR synchronizer primitive to drive the agreement on command ordering. We present a simple formal specification of an SMR synchronizer and its bounded-space implementation under partial synchrony. We also apply our specification to prove liveness and analyze the latency of three Byzantine SMR protocols via a uniform methodology. In particular, one of these results yields what we believe is the first rigorous liveness proof for the algorithmic core of the seminal PBFT protocol.
Cite as
Manuel Bravo, Gregory Chockler, and Alexey Gotsman. Liveness and Latency of Byzantine State-Machine Replication. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{bravo_et_al:LIPIcs.DISC.2022.12,
author = {Bravo, Manuel and Chockler, Gregory and Gotsman, Alexey},
title = {{Liveness and Latency of Byzantine State-Machine Replication}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {12:1--12:19},
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.12},
URN = {urn:nbn:de:0030-drops-172037},
doi = {10.4230/LIPIcs.DISC.2022.12},
annote = {Keywords: Replication, blockchain, partial synchrony, liveness}
}
Document
Oracular Byzantine Reliable Broadcast
Abstract
Byzantine Reliable Broadcast (BRB) is a fundamental distributed computing primitive, with applications ranging from notifications to asynchronous payment systems. Motivated by practical consideration, we study Client-Server Byzantine Reliable Broadcast (CSB), a multi-shot variant of BRB whose interface is split between broadcasting clients and delivering servers. We present Draft, an optimally resilient implementation of CSB. Like most implementations of BRB, Draft guarantees both liveness and safety in an asynchronous environment. Under good conditions, however, Draft achieves unparalleled efficiency. In a moment of synchrony, free from Byzantine misbehaviour, and at the limit of infinitely many broadcasting clients, a Draft server delivers a b-bits payload at an asymptotic amortized cost of 0 signature verifications, and (log₂(c) + b) bits exchanged, where c is the number of clients in the system. This is the information-theoretical minimum number of bits required to convey the payload (b bits, assuming it is compressed), along with an identifier for its sender (log₂(c) bits, necessary to enumerate any set of c elements, and optimal if broadcasting frequencies are uniform or unknown). These two achievements have profound practical implications. Real-world BRB implementations are often bottlenecked either by expensive signature verifications, or by communication overhead. For Draft, instead, the network is the limit: a server can deliver payloads as quickly as it would receive them from an infallible oracle.
Cite as
Martina Camaioni, Rachid Guerraoui, Matteo Monti, and Manuel Vidigueira. Oracular Byzantine Reliable Broadcast. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{camaioni_et_al:LIPIcs.DISC.2022.13,
author = {Camaioni, Martina and Guerraoui, Rachid and Monti, Matteo and Vidigueira, Manuel},
title = {{Oracular Byzantine Reliable Broadcast}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {13:1--13:19},
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.13},
URN = {urn:nbn:de:0030-drops-172048},
doi = {10.4230/LIPIcs.DISC.2022.13},
annote = {Keywords: Byzantine reliable broadcast, Good-case complexity, Amortized complexity, Batching}
}
Document
Byzantine Consensus Is Θ(n²): The Dolev-Reischuk Bound Is Tight Even in Partial Synchrony!
Abstract
The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic communication complexity in the worst case. While it has been shown that the bound is tight in synchronous environments, it is still unknown whether a consensus protocol with quadratic communication complexity can be obtained in partial synchrony. Until now, the most efficient known solutions for Byzantine consensus in partially synchronous settings had cubic communication complexity (e.g., HotStuff, binary DBFT).
This paper closes the existing gap by introducing SQuad, a partially synchronous Byzantine consensus protocol with quadratic worst-case communication complexity. In addition, SQuad is optimally-resilient and achieves linear worst-case latency complexity. The key technical contribution underlying SQuad lies in the way we solve view synchronization, the problem of bringing all correct processes to the same view with a correct leader for sufficiently long. Concretely, we present RareSync, a view synchronization protocol with quadratic communication complexity and linear latency complexity, which we utilize in order to obtain SQuad.
Cite as
Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira. Byzantine Consensus Is Θ(n²): The Dolev-Reischuk Bound Is Tight Even in Partial Synchrony!. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{civit_et_al:LIPIcs.DISC.2022.14,
author = {Civit, Pierre and Dzulfikar, Muhammad Ayaz and Gilbert, Seth and Gramoli, Vincent and Guerraoui, Rachid and Komatovic, Jovan and Vidigueira, Manuel},
title = {{Byzantine Consensus Is \Theta(n²): The Dolev-Reischuk Bound Is Tight Even in Partial Synchrony!}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {14:1--14:21},
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.14},
URN = {urn:nbn:de:0030-drops-172059},
doi = {10.4230/LIPIcs.DISC.2022.14},
annote = {Keywords: Optimal Byzantine consensus, Communication complexity, Latency complexity}
}
Document
Dynamic Probabilistic Input Output Automata
Abstract
We present probabilistic dynamic I/O automata, a framework to model dynamic probabilistic systems. Our work extends dynamic I/O Automata formalism of Attie & Lynch [Paul C. Attie and Nancy A. Lynch, 2016] to the probabilistic setting. The original dynamic I/O Automata formalism included operators for parallel composition, action hiding, action renaming, automaton creation, and behavioral sub-typing by means of trace inclusion. They can model mobility by using signature modification. They are also hierarchical: a dynamically changing system of interacting automata is itself modeled as a single automaton. Our work extends all these features to the probabilistic setting. Furthermore, we prove necessary and sufficient conditions to obtain the monotonicity of automata creation/destruction with implementation preorder. Our construction uses a novel proof technique based on homomorphism that can be of independent interest. Our work lays down the foundations for extending composable secure-emulation of Canetti et al. [Ran Canetti et al., 2007] to dynamic settings, an important tool towards the formal verification of protocols combining probabilistic distributed systems and cryptography in dynamic settings (e.g. blockchains, secure distributed computation, cybersecure distributed protocols, etc).
Cite as
Pierre Civit and Maria Potop-Butucaru. Dynamic Probabilistic Input Output Automata. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{civit_et_al:LIPIcs.DISC.2022.15,
author = {Civit, Pierre and Potop-Butucaru, Maria},
title = {{Dynamic Probabilistic Input Output Automata}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {15:1--15:18},
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.15},
URN = {urn:nbn:de:0030-drops-172064},
doi = {10.4230/LIPIcs.DISC.2022.15},
annote = {Keywords: Automata, Distributed Computing, Formal Verification, Dynamic systems}
}
Document
How to Wake up Your Neighbors: Safe and Nearly Optimal Generic Energy Conservation in Radio Networks
Abstract
Recent work [Chang et al., 2018; Chang et al., 2020; Varsha Dani et al., 2021] has shown that it is sometimes feasible to significantly reduce the energy usage of some radio-network algorithms by adaptively powering down the radio receiver when it is not needed. Although past work has focused on modifying specific network algorithms in this way, we now ask the question of whether this problem can be solved in a generic way, treating the algorithm as a kind of black box.
We are able to answer this question in the affirmative, presenting a new general way to modify arbitrary radio-network algorithms in an attempt to save energy. At the expense of a small increase in the time complexity, we can provably reduce the energy usage to an extent that is provably nearly optimal within a certain class of general-purpose algorithms.
As an application, we show that our algorithm reduces the energy cost of breadth-first search in radio networks from the previous best bound of 2^O(√{log n}) to polylog(n), where n is the number of nodes in the network
A key ingredient in our algorithm is hierarchical clustering based on additive Voronoi decomposition done at multiple scales. Similar clustering algorithms have been used in other recent work on energy-aware computation in radio networks, but we believe the specific approach presented here may be of independent interest.
Cite as
Varsha Dani and Thomas P. Hayes. How to Wake up Your Neighbors: Safe and Nearly Optimal Generic Energy Conservation in Radio Networks. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 16:1-16:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{dani_et_al:LIPIcs.DISC.2022.16,
author = {Dani, Varsha and Hayes, Thomas P.},
title = {{How to Wake up Your Neighbors: Safe and Nearly Optimal Generic Energy Conservation in Radio Networks}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {16:1--16:22},
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.16},
URN = {urn:nbn:de:0030-drops-172071},
doi = {10.4230/LIPIcs.DISC.2022.16},
annote = {Keywords: Radio Networks, Low Energy Computation, Clustering}
}
Document
Contention Resolution Without Collision Detection: Constant Throughput And Logarithmic Energy
Abstract
A shared channel, also called a multiple access channel, is among the most popular and widely studied models of communication in distributed computing. An unknown number of stations (potentially unbounded) is connected to the channel and can communicate by transmitting and listening. A message is successfully transmitted on the channel if and only if there is a unique transmitter at that time; otherwise the message collides with some other transmission and nothing is sensed by the participating stations. We consider the general framework without collision detection and in which any participating station can join the channel at any moment. The contention resolution task is to let each of the contending stations to broadcast successfully its message on the channel.
In this setting we present the first algorithm which exhibits asymptotically optimal Θ(1) throughput and only an O(log k) energy cost, understood as the maximum number of transmissions performed by a single station (where k is the number of participating stations, initially unknown). We also show that such efficiency cannot be reproduced by non-adaptive algorithms, i.e., whose behavior does not depend on the channel history (for example, classic backoff protocols). Namely, we show that non-adaptive algorithms cannot simultaneously achieve throughput Ω(1/polylog(k)) and energy O((log² k)/(log log k)²).
Cite as
Gianluca De Marco, Dariusz R. Kowalski, and Grzegorz Stachowiak. Contention Resolution Without Collision Detection: Constant Throughput And Logarithmic Energy. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 17:1-17:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{demarco_et_al:LIPIcs.DISC.2022.17,
author = {De Marco, Gianluca and Kowalski, Dariusz R. and Stachowiak, Grzegorz},
title = {{Contention Resolution Without Collision Detection: Constant Throughput And Logarithmic Energy}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {17:1--17:21},
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.17},
URN = {urn:nbn:de:0030-drops-172081},
doi = {10.4230/LIPIcs.DISC.2022.17},
annote = {Keywords: Shared channel, Contention resolution, Throughput, Energy consumption, Randomized algorithms, Lower bound}
}
Document
Smoothed Analysis of Information Spreading in Dynamic Networks
Abstract
The best known solutions for k-message broadcast in dynamic networks of size n require Ω(nk) rounds. In this paper, we see if these bounds can be improved by smoothed analysis. To do so, we study perhaps the most natural randomized algorithm for disseminating tokens in this setting: at every time step, choose a token to broadcast randomly from the set of tokens you know. We show that with even a small amount of smoothing (i.e., one random edge added per round), this natural strategy solves k-message broadcast in Õ(n+k³) rounds, with high probability, beating the best known bounds for k = o(√n) and matching the Ω(n+k) lower bound for static networks for k = O(n^{1/3}) (ignoring logarithmic factors). In fact, the main result we show is even stronger and more general: given 𝓁-smoothing (i.e., 𝓁 random edges added per round), this simple strategy terminates in O(kn^{2/3}log^{1/3}(n)𝓁^{-1/3}) rounds. We then prove this analysis close to tight with an almost-matching lower bound. To better understand the impact of smoothing on information spreading, we next turn our attention to static networks, proving a tight bound of Õ(k√n) rounds to solve k-message broadcast, which is better than what our strategy can achieve in the dynamic setting. This confirms the intuition that although smoothed analysis reduces the difficulties induced by changing graph structures, it does not eliminate them altogether. Finally, we apply tools developed to support our smoothed analysis to prove an optimal result for k-message broadcast in so-called well-mixed networks in the absence of smoothing. By comparing this result to an existing lower bound for well-mixed networks, we establish a formal separation between oblivious and strongly adaptive adversaries with respect to well-mixed token spreading, partially resolving an open question on the impact of adversary strength on the k-message broadcast problem.
Cite as
Michael Dinitz, Jeremy Fineman, Seth Gilbert, and Calvin Newport. Smoothed Analysis of Information Spreading in Dynamic Networks. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 18:1-18:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{dinitz_et_al:LIPIcs.DISC.2022.18,
author = {Dinitz, Michael and Fineman, Jeremy and Gilbert, Seth and Newport, Calvin},
title = {{Smoothed Analysis of Information Spreading in Dynamic Networks}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {18:1--18:22},
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.18},
URN = {urn:nbn:de:0030-drops-172094},
doi = {10.4230/LIPIcs.DISC.2022.18},
annote = {Keywords: Smoothed Analysis, Dynamic networks, Gossip}
}
Document
An Almost Singularly Optimal Asynchronous Distributed MST Algorithm
Abstract
A singularly (near) optimal distributed algorithm is one that is (near) optimal in two criteria, namely, its time and message complexities. For synchronous CONGEST networks, such algorithms are known for fundamental distributed computing problems such as leader election [Kutten et al., JACM 2015] and Minimum Spanning Tree (MST) construction [Pandurangan et al., STOC 2017, Elkin, PODC 2017]. However, it is open whether a singularly (near) optimal bound can be obtained for the MST construction problem in general asynchronous CONGEST networks.
In this paper, we present a randomized distributed MST algorithm that, with high probability, computes an MST in asynchronous CONGEST networks and takes Õ(D^{1+ε} + √n) time and Õ(m) messages, where n is the number of nodes, m the number of edges, D is the diameter of the network, and ε > 0 is an arbitrarily small constant (both time and message bounds hold with high probability). Since Ω̃(D+√n) and Ω(m) are respective time and message lower bounds for distributed MST construction in the standard KT₀ model, our algorithm is message optimal (up to a polylog(n) factor) and almost time optimal (except for a D^ε factor). Our result answers an open question raised in Mashregi and King [DISC 2019] by giving the first known asynchronous MST algorithm that has sublinear time (for all D = O(n^{1-ε})) and uses Õ(m) messages. Using a result of Mashregi and King [DISC 2019], this also yields the first asynchronous MST algorithm that is sublinear in both time and messages in the KT₁ CONGEST model.
A key tool in our algorithm is the construction of a low diameter rooted spanning tree in asynchronous CONGEST that has depth Õ(D^{1+ε}) (for an arbitrarily small constant ε > 0) in Õ(D^{1+ε}) time and Õ(m) messages. To the best of our knowledge, this is the first such construction that is almost singularly optimal in the asynchronous setting. This tree construction may be of independent interest as it can also be used for efficiently performing basic tasks such as verified broadcast and convergecast in asynchronous networks.
Cite as
Fabien Dufoulon, Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg. An Almost Singularly Optimal Asynchronous Distributed MST Algorithm. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{dufoulon_et_al:LIPIcs.DISC.2022.19,
author = {Dufoulon, Fabien and Kutten, Shay and Moses Jr., William K. and Pandurangan, Gopal and Peleg, David},
title = {{An Almost Singularly Optimal Asynchronous Distributed MST Algorithm}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {19:1--19:24},
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.19},
URN = {urn:nbn:de:0030-drops-172107},
doi = {10.4230/LIPIcs.DISC.2022.19},
annote = {Keywords: Asynchronous networks, Minimum Spanning Tree, Distributed Algorithm, Singularly Optimal}
}
Document
Locally Restricted Proof Labeling Schemes
Abstract
Introduced by Korman, Kutten, and Peleg (PODC 2005), a proof labeling scheme (PLS) is a distributed verification system dedicated to evaluating if a given configured graph satisfies a certain property. It involves a centralized prover, whose role is to provide proof that a given configured graph is a yes-instance by means of assigning labels to the nodes, and a distributed verifier, whose role is to verify the validity of the given proof via local access to the assigned labels. In this paper, we introduce the notion of a locally restricted PLS in which the prover’s power is restricted to that of a LOCAL algorithm with a polylogarithmic number of rounds. To circumvent inherent impossibilities of PLSs in the locally restricted setting, we turn to models that relax the correctness requirements by allowing the verifier to accept some no-instances as long as they are not "too far" from satisfying the property in question. To this end, we evaluate (1) distributed graph optimization problems (OptDGPs) based on the notion of an approximate proof labeling scheme (APLS) (analogous to the type of relaxation used in sequential approximation algorithms); and (2) configured graph families (CGFs) based on the notion of a testing proof labeling schemes (TPLS) (analogous to the type of relaxation used in property testing algorithms). The main contribution of the paper comes in the form of two generic compilers, one for OptDGPs and one for CGFs: given a black-box access to an APLS (resp., PLS) for a large class of OptDGPs (resp., CGFs), the compiler produces a locally restricted APLS (resp., TPLS) for the same problem, while losing at most a (1 + ε) factor in the scheme’s relaxation guarantee. An appealing feature of the two compilers is that they only require a logarithmic additive label size overhead.
Cite as
Yuval Emek, Yuval Gil, and Shay Kutten. Locally Restricted Proof Labeling Schemes. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 20:1-20:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{emek_et_al:LIPIcs.DISC.2022.20,
author = {Emek, Yuval and Gil, Yuval and Kutten, Shay},
title = {{Locally Restricted Proof Labeling Schemes}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {20:1--20:22},
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.20},
URN = {urn:nbn:de:0030-drops-172111},
doi = {10.4230/LIPIcs.DISC.2022.20},
annote = {Keywords: proof labeling schemes, generic compilers, SLOCAL algorithms}
}
Document
Distributed Construction of Lightweight Spanners for Unit Ball Graphs
Abstract
Resolving an open question from 2006 [Damian et al., 2006], we prove the existence of light-weight bounded-degree spanners for unit ball graphs in the metrics of bounded doubling dimension, and we design a simple 𝒪(log^*n)-round distributed algorithm in the LOCAL model of computation, that given a unit ball graph G with n vertices and a positive constant ε < 1 finds a (1+ε)-spanner with constant bounds on its maximum degree and its lightness using only 2-hop neighborhood information. This immediately improves the best prior lightness bound, the algorithm of Damian, Pandit, and Pemmaraju [Damian et al., 2006], which runs in 𝒪(log^*n) rounds in the LOCAL model, but has a 𝒪(log Δ) bound on its lightness, where Δ is the ratio of the length of the longest edge to the length of the shortest edge in the unit ball graph. Next, we adjust our algorithm to work in the CONGEST model, without changing its round complexity, hence proposing the first spanner construction for unit ball graphs in the CONGEST model of computation. We further study the problem in the two dimensional Euclidean plane and we provide a construction with similar properties that has a constant average number of edge intersections per node. Lastly, we provide experimental results that confirm our theoretical bounds, and show an efficient performance from our distributed algorithm compared to the best known centralized construction.
Cite as
David Eppstein and Hadi Khodabandeh. Distributed Construction of Lightweight Spanners for Unit Ball Graphs. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 21:1-21:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{eppstein_et_al:LIPIcs.DISC.2022.21,
author = {Eppstein, David and Khodabandeh, Hadi},
title = {{Distributed Construction of Lightweight Spanners for Unit Ball Graphs}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {21:1--21:23},
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.21},
URN = {urn:nbn:de:0030-drops-172129},
doi = {10.4230/LIPIcs.DISC.2022.21},
annote = {Keywords: spanners, doubling metrics, distributed, topology control}
}
Document
Improved Deterministic Connectivity in Massively Parallel Computation
Abstract
A long line of research about connectivity in the Massively Parallel Computation model has culminated in the seminal works of Andoni et al. [FOCS'18] and Behnezhad et al. [FOCS'19]. They provide a randomized algorithm for low-space MPC with conjectured to be optimal round complexity O(log D + log log_{m/n} n) and O(m) space, for graphs on n vertices with m edges and diameter D. Surprisingly, a recent result of Coy and Czumaj [STOC'22] shows how to achieve the same deterministically. Unfortunately, however, their algorithm suffers from large local computation time.
We present a deterministic connectivity algorithm that matches all the parameters of the randomized algorithm and, in addition, significantly reduces the local computation time to nearly linear.
Our derandomization method is based on reducing the amount of randomness needed to allow for a simpler efficient search. While similar randomness reduction approaches have been used before, our result is not only strikingly simpler, but it is the first to have efficient local computation. This is why we believe it to serve as a starting point for the systematic development of computation-efficient derandomization approaches in low-memory MPC.
Cite as
Manuela Fischer, Jeff Giliberti, and Christoph Grunau. Improved Deterministic Connectivity in Massively Parallel Computation. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{fischer_et_al:LIPIcs.DISC.2022.22,
author = {Fischer, Manuela and Giliberti, Jeff and Grunau, Christoph},
title = {{Improved Deterministic Connectivity in Massively Parallel Computation}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {22:1--22:17},
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.22},
URN = {urn:nbn:de:0030-drops-172138},
doi = {10.4230/LIPIcs.DISC.2022.22},
annote = {Keywords: Massively Parallel Computation, MPC, MapReduce, Deterministic Algorithms, Connectivity, Hitting Set, Maximum Matching, Derandomization}
}
Document
Fault Tolerant Coloring of the Asynchronous Cycle
Abstract
We present a wait-free algorithm for proper coloring the n nodes of the asynchronous cycle C_n, where each crash-prone node starts with its (unique) identifier as input. The algorithm is independent of n ≥ 3, and runs in O(log^*n) rounds in C_n. This round-complexity is optimal thanks to a known matching lower bound, which applies even to synchronous (failure-free) executions. The range of colors used by our algorithm, namely {0,…,4}, is optimal too, thanks to a known lower bound on the minimum number of names for which renaming is solvable wait-free in shared-memory systems, whenever n is a power of a prime. Indeed, our model coincides with the shared-memory model whenever n = 3, and the minimum number of names for which renaming is possible in 3-process shared-memory systems is 5.
Cite as
Pierre Fraigniaud, Patrick Lambein-Monette, and Mikaël Rabie. Fault Tolerant Coloring of the Asynchronous Cycle. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{fraigniaud_et_al:LIPIcs.DISC.2022.23,
author = {Fraigniaud, Pierre and Lambein-Monette, Patrick and Rabie, Mika\"{e}l},
title = {{Fault Tolerant Coloring of the Asynchronous Cycle}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {23:1--23:22},
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.23},
URN = {urn:nbn:de:0030-drops-172147},
doi = {10.4230/LIPIcs.DISC.2022.23},
annote = {Keywords: graph coloring, LOCAL model, shared-memory model, immediate snapshot, renaming, wait-free algorithms}
}
Document
Distributed Randomness from Approximate Agreement
Abstract
Randomisation is a critical tool in designing distributed systems. The common coin primitive, enabling the system members to agree on an unpredictable random number, has proven to be particularly useful. We observe, however, that it is impossible to implement a truly random common coin protocol in a fault-prone asynchronous system.
To circumvent this impossibility, we introduce two relaxations of the perfect common coin: (1) approximate common coin generating random numbers that are close to each other; and (2) Monte Carlo common coin generating a common random number with an arbitrarily small, but non-zero, probability of failure. Building atop the approximate agreement primitive, we obtain efficient asynchronous implementations of the two abstractions, tolerating up to one third of Byzantine processes. Our protocols do not assume trusted setup or public key infrastructure and converge to the perfect coin exponentially fast in the protocol running time.
By plugging one of our protocols for Monte Carlo common coin in a well-known consensus algorithm, we manage to get a binary Byzantine agreement protocol with O(n³ log n) communication complexity, resilient against an adaptive adversary, and tolerating the optimal number f < n/3 of failures without trusted setup or PKI. To the best of our knowledge, the best communication complexity for binary Byzantine agreement achieved so far in this setting is O(n⁴). We also show how the approximate common coin, combined with a variant of Gray code, can be used to solve an interesting problem of Intersecting Random Subsets, which we introduce in this paper.
Cite as
Luciano Freitas, Petr Kuznetsov, and Andrei Tonkikh. Distributed Randomness from Approximate Agreement. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 24:1-24:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{freitas_et_al:LIPIcs.DISC.2022.24,
author = {Freitas, Luciano and Kuznetsov, Petr and Tonkikh, Andrei},
title = {{Distributed Randomness from Approximate Agreement}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {24:1--24:21},
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.24},
URN = {urn:nbn:de:0030-drops-172157},
doi = {10.4230/LIPIcs.DISC.2022.24},
annote = {Keywords: Asynchronous, approximate agreement, weak common coin, consensus, Byzantine agreement}
}
Document
Fragmented ARES: Dynamic Storage for Large Objects
Abstract
Data availability is one of the most important features in distributed storage systems, made possible by data replication. Nowadays data are generated rapidly and developing efficient, scalable and reliable storage systems has become one of the major challenges for high performance computing. In this work, we develop and prove correct a dynamic, robust and strongly consistent distributed shared memory suitable for handling large objects (such as files) and utilizing erasure coding. We do so by integrating an Adaptive, Reconfigurable, Atomic memory framework, called Ares, with the CoBFS framework, which relies on a block fragmentation technique to handle large objects. With the addition of Ares, we also enable the use of an erasure-coded algorithm to further split the data and to potentially improve storage efficiency at the replica servers and operation latency. Our development is complemented with an in-depth experimental evaluation on the Emulab and AWS EC2 testbeds, illustrating the benefits of our approach, as well as interesting tradeoffs.
Cite as
Chryssis Georgiou, Nicolas Nicolaou, and Andria Trigeorgi. Fragmented ARES: Dynamic Storage for Large Objects. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 25:1-25:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{georgiou_et_al:LIPIcs.DISC.2022.25,
author = {Georgiou, Chryssis and Nicolaou, Nicolas and Trigeorgi, Andria},
title = {{Fragmented ARES: Dynamic Storage for Large Objects}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {25:1--25:24},
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.25},
URN = {urn:nbn:de:0030-drops-172161},
doi = {10.4230/LIPIcs.DISC.2022.25},
annote = {Keywords: Distributed storage, Large objects, Strong consistency, High access concurrency, Erasure code, Reconfiguration}
}
Document
Fast Distributed Vertex Splitting with Applications
Abstract
We present poly log log n-round randomized distributed algorithms to compute vertex splittings, a partition of the vertices of a graph into k parts such that a node of degree d(u) has ≈ d(u)/k neighbors in each part. Our techniques can be seen as the first progress towards general poly log log n-round algorithms for the Lovász Local Lemma.
As the main application of our result, we obtain a randomized poly log log n-round CONGEST algorithm for (1+ε)Δ-edge coloring n-node graphs of sufficiently large constant maximum degree Δ, for any ε > 0. Further, our results improve the computation of defective colorings and certain tight list coloring problems. All the results improve the state-of-the-art round complexity exponentially, even in the LOCAL model.
Cite as
Magnús M. Halldórsson, Yannic Maus, and Alexandre Nolin. Fast Distributed Vertex Splitting with Applications. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 26:1-26:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{halldorsson_et_al:LIPIcs.DISC.2022.26,
author = {Halld\'{o}rsson, Magn\'{u}s M. and Maus, Yannic and Nolin, Alexandre},
title = {{Fast Distributed Vertex Splitting with Applications}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {26:1--26:24},
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.26},
URN = {urn:nbn:de:0030-drops-172176},
doi = {10.4230/LIPIcs.DISC.2022.26},
annote = {Keywords: Graph problems, Edge coloring, List coloring, Lov\'{a}sz local lemma, LOCAL model, CONGEST model, Distributed computing}
}
Document
Broadcast CONGEST Algorithms Against Eavesdroppers
Abstract
An eavesdropper is a passive adversary that aims at extracting private information on the input and output values of the network’s participants, by listening to the traffic exchanged over a subset of edges in the graph. We consider secure congest algorithms for the basic broadcast task, in the presence of eavesdropper (edge) adversaries.
For D-diameter n-vertex graphs with edge connectivity Θ(f), we present f-secure broadcast algorithms that run in Õ(D+√{f n}) rounds. These algorithms transmit some broadcast message m^* to all the vertices in the graph, in a way that is information-theoretically secure against an eavesdropper controlling any subset of at most f edges in the graph. While our algorithms are heavily based on network coding (secret sharing), we also show that this is essential. For the basic problem of secure unicast we demonstrate a network coding gap of Ω(n) rounds.
In the presence of vertex adversaries, known as semi-honest, we introduce the Forbidden-Set Broadcast problem: In this problem, the vertices of the graph are partitioned into two sets, trusted and untrusted, denoted as R, F ⊆ V, respectively, such that G[R] is connected. It is then desired to exchange a secret message m^* between all the trusted vertices while leaking no information to the untrusted set F. Our algorithm works in Õ(D+√|R|) rounds and its security guarantees hold even when all the untrusted vertices F are controlled by a (centralized) adversary.
Cite as
Yael Hitron, Merav Parter, and Eylon Yogev. Broadcast CONGEST Algorithms Against Eavesdroppers. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{hitron_et_al:LIPIcs.DISC.2022.27,
author = {Hitron, Yael and Parter, Merav and Yogev, Eylon},
title = {{Broadcast CONGEST Algorithms Against Eavesdroppers}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {27:1--27:19},
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.27},
URN = {urn:nbn:de:0030-drops-172186},
doi = {10.4230/LIPIcs.DISC.2022.27},
annote = {Keywords: congest, edge-connectivity, secret sharing}
}
Document
Routing Schemes and Distance Oracles in the Hybrid Model
Abstract
The HYBRID model was introduced as a means for theoretical study of distributed networks that use various communication modes. Conceptually, it is a synchronous message passing model with a local communication mode, where in each round each node can send large messages to all its neighbors in a local network (a graph), and a global communication mode, where each node is allotted limited (polylogarithmic) bandwidth per round to communicate with any node in the network.
Prior work has often focused on shortest paths problems in the local network, as their global nature makes these an interesting case study how combining communication modes in the HYBRID model can overcome the individual lower bounds of either mode. In this work we consider a similar problem, namely computation of distance oracles and routing schemes. In the former, all nodes have to compute local tables, which allows them to look up the distance (estimates) to any target node in the local network when provided with the label of the target. In the latter, it suffices that nodes give the next node on an (approximately) shortest path to the target.
Our goal is to compute these local tables as fast as possible with labels as small as possible. We show that this can be done exactly in Õ(n^{1/3}) communication rounds and labels of size Θ(n^{2/3}) bits. For constant stretch approximations we achieve labels of size O(log n) in the same time. Further, as our main technical contribution, we provide computational lower bounds for a variety of problem parameters. For instance, we show that computing solutions with stretch below a certain constant takes Ω̃(n^{1/3}) rounds even for labels of size O(n^{2/3}).
Cite as
Fabian Kuhn and Philipp Schneider. Routing Schemes and Distance Oracles in the Hybrid Model. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 28:1-28:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{kuhn_et_al:LIPIcs.DISC.2022.28,
author = {Kuhn, Fabian and Schneider, Philipp},
title = {{Routing Schemes and Distance Oracles in the Hybrid Model}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {28:1--28:22},
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.28},
URN = {urn:nbn:de:0030-drops-172198},
doi = {10.4230/LIPIcs.DISC.2022.28},
annote = {Keywords: Distributed Computing, Graph Algorithms, Complexity Analysis}
}
Document
On Payment Channels in Asynchronous Money Transfer Systems
Abstract
Money transfer is an abstraction that realizes the core of cryptocurrencies. It has been shown that, contrary to common belief, money transfer in the presence of Byzantine faults can be implemented in asynchronous networks and does not require consensus. Nonetheless, existing implementations of money transfer still require a quadratic message complexity per payment, making attempts to scale hard. In common blockchains, such as Bitcoin and Ethereum, this cost is mitigated by payment channels implemented as a second layer on top of the blockchain allowing to make many off-chain payments between two users who share a channel. Such channels require only on-chain transactions for channel opening and closing, while the intermediate payments are done off-chain with constant message complexity. But payment channels in-use today require synchrony; therefore, they are inadequate for asynchronous money transfer systems.
In this paper, we provide a series of possibility and impossibility results for payment channels in asynchronous money transfer systems. We first prove a quadratic lower bound on the message complexity of on-chain transfers. Then, we explore two types of payment channels, unidirectional and bidirectional. We define them as shared memory abstractions and prove that in certain cases they can be implemented as a second layer on top of an asynchronous money transfer system whereas in other cases it is impossible.
Cite as
Oded Naor and Idit Keidar. On Payment Channels in Asynchronous Money Transfer Systems. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 29:1-29:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{naor_et_al:LIPIcs.DISC.2022.29,
author = {Naor, Oded and Keidar, Idit},
title = {{On Payment Channels in Asynchronous Money Transfer Systems}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {29:1--29: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.29},
URN = {urn:nbn:de:0030-drops-172201},
doi = {10.4230/LIPIcs.DISC.2022.29},
annote = {Keywords: Blockchains, Asynchrony, Byzantine faults, Payment channels}
}
Document
The Space Complexity of Scannable Objects with Bounded Components
Abstract
A fundamental task in the asynchronous shared memory model is obtaining a consistent view of a collection of shared objects while they are being modified concurrently by other processes. A scannable object addresses this problem. A scannable object is a sequence of readable objects called components, each of which can be accessed independently. It also supports the Scan operation, which simultaneously reads all of the components of the object. In this paper, we consider the space complexity of an n-process, k-component scannable object implementation from objects with bounded domain sizes. If the value of each component can change only a finite number of times, then there is a simple lock-free implementation from k objects. However, more objects are needed if each component is fully reusable, i.e. for every pair of values v, v', there is a sequence of operations that changes the value of the component from v to v'.
We considered the special case of scannable binary objects, where each component has domain {0, 1}, in PODC 2021. Here, we present upper and lower bounds on the space complexity of any n-process implementation of a scannable object O with k fully reusable components from an arbitrary set of objects with bounded domain sizes. We construct a lock-free implementation from k objects of the same types as the components of O along with ⌈n/b⌉ objects with domain size 2^b. By weakening the progress condition to obstruction-freedom, we construct an implementation from k objects of the same types as the components of O along with ⌈n/(b-1)⌉ objects with domain size b.
When the domain size of each component and each object used to implement O is equal to b and n ≤ b^k - bk + k, we prove that 1/2⋅ (k + (n-1)/b - log_b n) objects are required. This asymptotically matches our obstruction-free upper bound. When n > b^k - bk + k, we prove that 1/2⋅ (b^{k-1} - {(b-1)k + 1}/b) objects are required. We also present a lower bound on the number of objects needed when the domain sizes of the components and the objects used by the implementation are arbitrary and finite.
Cite as
Sean Ovens. The Space Complexity of Scannable Objects with Bounded Components. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 30:1-30:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{ovens:LIPIcs.DISC.2022.30,
author = {Ovens, Sean},
title = {{The Space Complexity of Scannable Objects with Bounded Components}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {30:1--30:18},
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.30},
URN = {urn:nbn:de:0030-drops-172213},
doi = {10.4230/LIPIcs.DISC.2022.30},
annote = {Keywords: space complexity, lower bound, shared memory, snapshot object}
}
Document
Near-Optimal Distributed Computation of Small Vertex Cuts
Abstract
We present near-optimal algorithms for detecting small vertex cuts in the {CONGEST} model of distributed computing. Despite extensive research in this area, our understanding of the vertex connectivity of a graph is still incomplete, especially in the distributed setting. To this date, all distributed algorithms for detecting cut vertices suffer from an inherent dependency in the maximum degree of the graph, Δ. Hence, in particular, there is no truly sub-linear time algorithm for this problem, not even for detecting a single cut vertex. We take a new algorithmic approach for vertex connectivity which allows us to bypass the existing Δ barrier.
- As a warm-up to our approach, we show a simple Õ(D)-round randomized algorithm for computing all cut vertices in a D-diameter n-vertex graph. This improves upon the O(D+Δ/log n)-round algorithm of [Pritchard and Thurimella, ICALP 2008].
- Our key technical contribution is an Õ(D)-round randomized algorithm for computing all cut pairs in the graph, improving upon the state-of-the-art O(Δ ⋅ D)⁴-round algorithm by [Parter, DISC '19]. Note that even for the considerably simpler setting of edge cuts, currently Õ(D)-round algorithms are currently known only for detecting pairs of cut edges.
Our approach is based on employing the well-known linear graph sketching technique [Ahn, Guha and McGregor, SODA 2012] along with the heavy-light tree decomposition of [Sleator and Tarjan, STOC 1981] . Combining this with a careful characterization of the survivable subgraphs, allows us to determine the connectivity of G ⧵ {x,y} for every pair x,y ∈ V, using Õ(D)-rounds. We believe that the tools provided in this paper are useful for omitting the Δ-dependency even for larger cut values.
Cite as
Merav Parter and Asaf Petruschka. Near-Optimal Distributed Computation of Small Vertex Cuts. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 31:1-31:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{parter_et_al:LIPIcs.DISC.2022.31,
author = {Parter, Merav and Petruschka, Asaf},
title = {{Near-Optimal Distributed Computation of Small Vertex Cuts}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {31:1--31:21},
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.31},
URN = {urn:nbn:de:0030-drops-172223},
doi = {10.4230/LIPIcs.DISC.2022.31},
annote = {Keywords: Vertex-connectivity, Congest, Graph Sketches}
}
Document
Õptimal Dual Vertex Failure Connectivity Labels
Abstract
In this paper we present succinct labeling schemes for supporting connectivity queries under vertex faults. For a given n-vertex graph G, an f-VFT (resp., EFT) connectivity labeling scheme is a distributed data structure that assigns each of the graph edges and vertices a short label, such that given the labels of a vertex pair u and v, and the labels of at most f failing vertices (resp., edges) F, one can determine if u and v are connected in G ⧵ F. The primary complexity measure is the length of the individual labels. Since their introduction by [Courcelle, Twigg, STACS '07], FT labeling schemes have been devised only for a limited collection of graph families. A recent work [Dory and Parter, PODC 2021] provided EFT labeling schemes for general graphs under edge failures, leaving the vertex failure case fairly open.
We provide the first sublinear f-VFT labeling schemes for f ≥ 2 for any n-vertex graph. Our key result is 2-VFT connectivity labels with O(log³ n) bits. Our constructions are based on analyzing the structure of dual failure replacement paths on top of the well-known heavy-light tree decomposition technique of [Sleator and Tarjan, STOC 1981]. We also provide f-VFT labels with sub-linear length (in |V|) for any f = o(log log n), that are based on a reduction to the existing EFT labels.
Cite as
Merav Parter and Asaf Petruschka. Õptimal Dual Vertex Failure Connectivity Labels. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 32:1-32:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{parter_et_al:LIPIcs.DISC.2022.32,
author = {Parter, Merav and Petruschka, Asaf},
title = {{\~{O}ptimal Dual Vertex Failure Connectivity Labels}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {32:1--32:19},
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.32},
URN = {urn:nbn:de:0030-drops-172239},
doi = {10.4230/LIPIcs.DISC.2022.32},
annote = {Keywords: Fault-Tolerance, Heavy-Light Decomposition, Labeling Schemes}
}
Document
Safe Permissionless Consensus
Abstract
Nakamoto’s consensus protocol works in a permissionless model, where nodes can join and leave without notice. However, it guarantees agreement only probabilistically. Is this weaker guarantee a necessary concession to the severe demands of supporting a permissionless model? This paper shows that, at least in a benign failure model, it is not. It presents Sandglass, the first permissionless consensus algorithm that guarantees deterministic agreement and termination with probability 1 under general omission failures. Like Nakamoto, Sandglass adopts a hybrid synchronous communication model, where, at all times, a majority of nodes (though their number is unknown) are correct and synchronously connected, and allows nodes to join and leave at any time.
Cite as
Youer Pu, Lorenzo Alvisi, and Ittay Eyal. Safe Permissionless Consensus. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{pu_et_al:LIPIcs.DISC.2022.33,
author = {Pu, Youer and Alvisi, Lorenzo and Eyal, Ittay},
title = {{Safe Permissionless Consensus}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {33:1--33:15},
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.33},
URN = {urn:nbn:de:0030-drops-172246},
doi = {10.4230/LIPIcs.DISC.2022.33},
annote = {Keywords: Consensus, Permissionless, Nakamoto, Deterministic Safety}
}
Document
Packet Forwarding with a Locally Bursty Adversary
Abstract
We consider packet forwarding in the adversarial queueing theory (AQT) model introduced by Borodin et al. We introduce a refinement of the AQT (ρ, σ)-bounded adversary, which we call a locally bursty adversary (LBA) that parameterizes injection patterns jointly by edge utilization and packet origin. For constant (O(1)) parameters, the LBA model is strictly more permissive than the (ρ, σ) model. For example, there are injection patterns in the LBA model with constant parameters that can only be realized as (ρ, σ)-bounded injection patterns with ρ + σ = Ω(n) (where n is the network size). We show that the LBA model (unlike the (ρ, σ) model) is closed under packet bundling and discretization operations. Thus, the LBA model allows one to reduce the study of general (uniform) capacity networks and inhomogenous packet sizes to unit capacity networks with homogeneous packets.
On the algorithmic side, we focus on information gathering networks - i.e., networks in which all packets share a common destination, and the union of packet routes forms a tree. We show that the Odd-Even Downhill (OED) forwarding protocol described independently by Dobrev et al. and Patt-Shamir and Rosenbaum achieves buffer space usage of O(log n) against all LBAs with constant parameters. OED is a local protocol, but we show that the upper bound is tight even when compared to centralized protocols. Our lower bound for the LBA model is in contrast to the (ρ, σ)-model, where centralized protocols can achieve worst-case buffer space usage O(1) for ρ, σ = O(1), while the O(log n) upper bound for OED is optimal only for local protocols.
Cite as
Will Rosenbaum. Packet Forwarding with a Locally Bursty Adversary. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 34:1-34:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{rosenbaum:LIPIcs.DISC.2022.34,
author = {Rosenbaum, Will},
title = {{Packet Forwarding with a Locally Bursty Adversary}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {34:1--34:18},
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.34},
URN = {urn:nbn:de:0030-drops-172254},
doi = {10.4230/LIPIcs.DISC.2022.34},
annote = {Keywords: packet forwarding, packet scheduling, adversarial queueing theory, network calculus, odd-even downhill forwarding, locally bursty adversary, local algorithms}
}
Document
The Weakest Failure Detector for Genuine Atomic Multicast
Abstract
Atomic broadcast is a group communication primitive to order messages across a set of distributed processes. Atomic multicast is its natural generalization where each message m is addressed to dst(m), a subset of the processes called its destination group. A solution to atomic multicast is genuine when a process takes steps only if a message is addressed to it. Genuine solutions are the ones used in practice because they have better performance.
Let 𝒢 be all the destination groups and ℱ be the cyclic families in it, that is the subsets of 𝒢 whose intersection graph is hamiltonian. This paper establishes that the weakest failure detector to solve genuine atomic multicast is 𝜇 = (∧_{g,h ∈ 𝒢} Σ_{g ∩ h}) ∧ (∧_{g ∈ 𝒢} Ω_g) ∧ γ, where Σ_P and Ω_P are the quorum and leader failure detectors restricted to the processes in P, and γ is a new failure detector that informs the processes in a cyclic family f ∈ ℱ when f is faulty.
We also study two classical variations of atomic multicast. The first variation requires that message delivery follows the real-time order. In this case, 𝜇 must be strengthened with 1^{g ∩ h}, the indicator failure detector that informs each process in g ∪ h when g ∩ h is faulty. The second variation requires a message to be delivered when the destination group runs in isolation. We prove that its weakest failure detector is at least 𝜇 ∧ (∧_{g, h ∈ 𝒢} Ω_{g ∩ h}). This value is attained when ℱ = ∅.
Cite as
Pierre Sutra. The Weakest Failure Detector for Genuine Atomic Multicast. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 35:1-35:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{sutra:LIPIcs.DISC.2022.35,
author = {Sutra, Pierre},
title = {{The Weakest Failure Detector for Genuine Atomic Multicast}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {35:1--35:19},
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.35},
URN = {urn:nbn:de:0030-drops-172267},
doi = {10.4230/LIPIcs.DISC.2022.35},
annote = {Keywords: Failure Detector, State Machine Replication, Consensus}
}
Document
On Implementing SWMR Registers from SWSR Registers in Systems with Byzantine Failures
Abstract
The implementation of registers from (potentially) weaker registers is a classical problem in the theory of distributed computing. Since Lamport’s pioneering work [Leslie Lamport, 1986], this problem has been extensively studied in the context of asynchronous processes with crash failures. In this paper, we investigate this problem in the context of Byzantine process failures, with and without process signatures. In particular, we first show a strong impossibility result, namely, that there is no wait-free linearizable implementation of a 1-writer n-reader register from atomic 1-writer (n-1)-reader registers. In fact, this impossibility result holds even if all the processes except the writer are given atomic 1-writer n-reader registers, and even if we assume that the writer can only crash and at most one reader is subject to Byzantine failures. In light of this impossibility result, we give two register implementations. The first one implements a 1-writer n-reader register from atomic 1-writer 1-reader registers. This implementation is linearizable (under any combination of Byzantine process failures), but it is wait-free only under the assumption that the writer is correct or no reader is Byzantine - thus matching the impossibility result. The second implementation assumes process signatures; it is wait-free and linearizable under any number and combination of Byzantine process failures.
Cite as
Xing Hu and Sam Toueg. On Implementing SWMR Registers from SWSR Registers in Systems with Byzantine Failures. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 36:1-36:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{hu_et_al:LIPIcs.DISC.2022.36,
author = {Hu, Xing and Toueg, Sam},
title = {{On Implementing SWMR Registers from SWSR Registers in Systems with Byzantine Failures}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {36:1--36:19},
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.36},
URN = {urn:nbn:de:0030-drops-172272},
doi = {10.4230/LIPIcs.DISC.2022.36},
annote = {Keywords: distributed computing, concurrency, linearizability, shared registers}
}
Document
Space-Stretch Tradeoff in Routing Revisited
Abstract
We present several new proofs of lower bounds for the space-stretch tradeoff in labeled network routing.
First, we give a new proof of an important result of Cyril Gavoille and Marc Gengler that any routing scheme with stretch < 3 must use Ω(n) bits of space at some node on some network with n vertices, even if port numbers can be changed. Compared to the original proof, our proof is significantly shorter and, we believe, conceptually and technically simpler. A small extension of the proof can show that, in fact, any constant fraction of the n nodes must use Ω(n) bits of space on some graph.
Our main contribution is a new result that if port numbers are chosen adversarially, then stretch < 2k+1 implies some node must use Ω(n^(1/k) log n) bits of space on some graph, assuming a girth conjecture by Erdős.
We conclude by showing that all known methods of proving a space lower bound in the labeled setting, in fact, require the girth conjecture.
Cite as
Anatoliy Zinovyev. Space-Stretch Tradeoff in Routing Revisited. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{zinovyev:LIPIcs.DISC.2022.37,
author = {Zinovyev, Anatoliy},
title = {{Space-Stretch Tradeoff in Routing Revisited}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {37:1--37:16},
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.37},
URN = {urn:nbn:de:0030-drops-172281},
doi = {10.4230/LIPIcs.DISC.2022.37},
annote = {Keywords: Compact routing, labeled network routing, lower bounds}
}
Document
Brief Announcement
Brief Announcement: Authenticated Consensus in Synchronous Systems with Mixed Faults
Abstract
Protocols solving authenticated consensus in synchronous networks with Byzantine faults have been widely researched and known to exists if and only if n > 2f for f Byzantine faults. Similarly, protocols solving authenticated consensus in partially synchronous networks are known to exist if n > 3f+2k for f Byzantine faults and k crash faults. In this work we fill a natural gap in our knowledge by presenting MixSync, an authenticated consensus protocol in synchronous networks resilient to f Byzantine faults and k crash faults if n > 2f+k. As a basic building block, we first define and then construct a publicly verifiable crusader agreement protocol with the same resilience. The protocol uses a simple double-send round to guarantee non-equivocation, a technique later used in the MixSync protocol. We then discuss how to construct a state machine replication protocol using these ideas, and how they can be used in general to make such protocols resilient to crash faults. Finally, we prove lower bounds showing that n > 2f+k is optimally resilient for consensus and state machine replication protocols.
Cite as
Ittai Abraham, Danny Dolev, Alon Kagan, and Gilad Stern. Brief Announcement: Authenticated Consensus in Synchronous Systems with Mixed Faults. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 38:1-38:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{abraham_et_al:LIPIcs.DISC.2022.38,
author = {Abraham, Ittai and Dolev, Danny and Kagan, Alon and Stern, Gilad},
title = {{Brief Announcement: Authenticated Consensus in Synchronous Systems with Mixed Faults}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {38:1--38:3},
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.38},
URN = {urn:nbn:de:0030-drops-172292},
doi = {10.4230/LIPIcs.DISC.2022.38},
annote = {Keywords: consensus, state machine replication, mixed faults, synchrony, lower bounds}
}
Document
Brief Announcement
Brief Announcement: It’s not easy to relax: liveness in chained BFT protocols
Abstract
Modern chained BFT SMR protocols have poor liveness under failures as they require multiple consecutive honest leaders to commit a single block. Siesta, our proposed new BFT SMR protocol, is instead able to commit a block that spans multiple non-consecutive honest leaders. Siesta reduces the expected commit latency of HotStuff by a factor of three under failures, and the worst-case latency by a factor of eight.
Cite as
Ittai Abraham, Natacha Crooks, Neil Giridharan, Heidi Howard, and Florian Suri-Payer. Brief Announcement: It’s not easy to relax: liveness in chained BFT protocols. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 39:1-39:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{abraham_et_al:LIPIcs.DISC.2022.39,
author = {Abraham, Ittai and Crooks, Natacha and Giridharan, Neil and Howard, Heidi and Suri-Payer, Florian},
title = {{Brief Announcement: It’s not easy to relax: liveness in chained BFT protocols}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {39:1--39:3},
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.39},
URN = {urn:nbn:de:0030-drops-172305},
doi = {10.4230/LIPIcs.DISC.2022.39},
annote = {Keywords: Consensus, blockchain, BFT}
}
Document
Brief Announcement
Brief Announcement: Distributed Algorithms for Minimum Dominating Set Problem and Beyond, a New Approach
Abstract
In this paper, we study the minimum dominating set (MDS) problem and the minimum total dominating set (MTDS) problem. We propose a new idea to compute approximate MDS and MTDS. This new approach can be implemented in a distributed model or parallel model. We also show how to use this new approach in other related problems such as set cover problem and k-distance dominating set problem.
Cite as
Sharareh Alipour and Mohammadhadi Salari. Brief Announcement: Distributed Algorithms for Minimum Dominating Set Problem and Beyond, a New Approach. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 40:1-40:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{alipour_et_al:LIPIcs.DISC.2022.40,
author = {Alipour, Sharareh and Salari, Mohammadhadi},
title = {{Brief Announcement: Distributed Algorithms for Minimum Dominating Set Problem and Beyond, a New Approach}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {40:1--40:3},
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.40},
URN = {urn:nbn:de:0030-drops-172315},
doi = {10.4230/LIPIcs.DISC.2022.40},
annote = {Keywords: Minimum dominating set problem, set cover problem, k-distance dominating set problem, distributed algorithms}
}
Document
Brief Announcement
Brief Announcement: Survey of Persistent Memory Correctness Conditions
Abstract
In this brief paper, we survey existing correctness definitions for concurrent persistent programs.
Cite as
Naama Ben-David, Michal Friedman, and Yuanhao Wei. Brief Announcement: Survey of Persistent Memory Correctness Conditions. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 41:1-41:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{bendavid_et_al:LIPIcs.DISC.2022.41,
author = {Ben-David, Naama and Friedman, Michal and Wei, Yuanhao},
title = {{Brief Announcement: Survey of Persistent Memory Correctness Conditions}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {41:1--41:4},
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.41},
URN = {urn:nbn:de:0030-drops-172328},
doi = {10.4230/LIPIcs.DISC.2022.41},
annote = {Keywords: Persistence, NVRAM, Correctness, Concurrency}
}
Document
Brief Announcement
Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies
Abstract
Emerging reconfigurable optical communication technologies enable demand-aware networks: networks whose static topology can be enhanced with demand-aware links optimized towards the traffic pattern the network serves. This paper studies the algorithmic problem of how to jointly optimize the topology and the routing in such demand-aware networks, to minimize congestion. We investigate this problem along two dimensions: (1) whether flows are splittable or unsplittable, and (2) whether routing on the hybrid topology is segregated or not, i.e., whether or not flows either have to use exclusively either the static network or the demand-aware connections. For splittable and segregated routing, we show that the problem is 2-approximable in general, but APX-hard even for uniform demands induced by a bipartite demand graph. For unsplittable and segregated routing, we show an upper bound of O(log m/ log log m) and a lower bound of Ω(log m/ log log m) for polynomial-time approximation algorithms, where m is the number of static links. Under splittable (resp., unsplittable) and non-segregated routing, even for demands of a single source (resp., destination), the problem cannot be approximated better than Ω(c_{max}/c_{min}) unless P=NP, where c_{max} (resp., c_{min}) denotes the maximum (resp., minimum) capacity. It is still NP-hard for uniform capacities, but can be solved efficiently for a single commodity and uniform capacities.
Cite as
Wenkai Dai, Michael Dinitz, Klaus-Tycho Foerster, and Stefan Schmid. Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 42:1-42:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{dai_et_al:LIPIcs.DISC.2022.42,
author = {Dai, Wenkai and Dinitz, Michael and Foerster, Klaus-Tycho and Schmid, Stefan},
title = {{Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {42:1--42:3},
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.42},
URN = {urn:nbn:de:0030-drops-172330},
doi = {10.4230/LIPIcs.DISC.2022.42},
annote = {Keywords: Congestion, Reconfigurable Networks, Algorithms, Complexity}
}
Document
Brief Announcement
Brief Announcement: Computing Power of Hybrid Models in Synchronous Networks
Abstract
During the last two decades, a small set of distributed computing models for networks have emerged, among which LOCAL, CONGEST, and Broadcast Congested Clique (BCC) play a prominent role. We consider hybrid models resulting from combining these three models. That is, we analyze the computing power of models allowing to, say, perform a constant number of rounds of CONGEST, then a constant number of rounds of LOCAL, then a constant number of rounds of BCC, possibly repeating this figure a constant number of times. We specifically focus on 2-round models, and we establish the complete picture of the relative powers of these models. That is, for every pair of such models, we determine whether one is (strictly) stronger than the other, or whether the two models are incomparable.
Cite as
Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos-Wilson, and Ioan Todinca. Brief Announcement: Computing Power of Hybrid Models in Synchronous Networks. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 43:1-43:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{fraigniaud_et_al:LIPIcs.DISC.2022.43,
author = {Fraigniaud, Pierre and Montealegre, Pedro and Paredes, Pablo and Rapaport, Ivan and R{\'\i}os-Wilson, Mart{\'\i}n and Todinca, Ioan},
title = {{Brief Announcement: Computing Power of Hybrid Models in Synchronous Networks}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {43:1--43:3},
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.43},
URN = {urn:nbn:de:0030-drops-172345},
doi = {10.4230/LIPIcs.DISC.2022.43},
annote = {Keywords: hybrid model, synchronous networks, LOCAL, CONGEST, Broadcast Congested Clique}
}
Document
Brief Announcement
Brief Announcement: New Clocks, Fast Line Formation and Self-Replication Population Protocols
Abstract
In this paper we consider a known variant of the standard population protocol model in which agents can be connected by edges, referred to as the network constructor model. During an interaction between two agents the relevant connecting edge can be formed, maintained or eliminated by the transition function. The state space of agents is fixed (constant size) and the size n of the population is not known, i.e., not hard-coded in the transition function.
Since pairs of agents are chosen uniformly at random the status of each edge is updated every Θ(n²) interactions in expectation which coincides with Θ(n) parallel time. This phenomenon provides a natural lower bound on the time complexity for any non-trivial network construction designed for this variant. This is in contrast with the standard population protocol model in which efficient protocols operate in O(polylog n) parallel time.
The main focus in this paper is on efficient manipulation of linear structures including formation, self-replication and distribution (including pipelining) of complex information in the adopted model.
- We propose and analyse a novel edge based phase clock counting parallel time Θ(nlog n) in the network constructor model, showing also that its leader based counterpart provides the same time guaranties in the standard population protocol model. Note that all currently known phase clocks can count parallel time not exceeding O(polylog n).
- The new clock enables a nearly optimal O(nlog n) parallel time spanning line construction (a key component of universal network construction), which improves dramatically on the best currently known O(n²) parallel time protocol, solving the main open problem in the considered model [O. Michail and P. Spirakis, 2016].
- We propose a new probabilistic bubble-sort algorithm in which random comparisons and transfers are allowed only between the adjacent positions in the sequence. Utilising a novel potential function reasoning we show that rather surprisingly this probabilistic sorting (via conditional pipelining) procedure requires O(n²) comparisons in expectation and whp, and is on par with its deterministic counterpart.
- We propose the first population protocol allowing self-replication of a strand of an arbitrary length k (carrying a k-bit message of size independent of the state space) in parallel time O(n(k+log n)). The pipelining mechanism and the time complexity analysis of the strand self-replication protocol mimic those used in the probabilistic bubble-sort. The new protocol permits also simultaneous self-replication, where l copies of the strand can be created in time O(n(k+log n)log l). Finally, we discuss application of the strand self-replication protocol to pattern matching. Our protocols are always correct and provide time guaranties with high probability defined as 1-n^{-η}, for a constant η > 0.
Cite as
Leszek Gąsieniec, Paul Spirakis, and Grzegorz Stachowiak. Brief Announcement: New Clocks, Fast Line Formation and Self-Replication Population Protocols. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 44:1-44:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{gasieniec_et_al:LIPIcs.DISC.2022.44,
author = {G\k{a}sieniec, Leszek and Spirakis, Paul and Stachowiak, Grzegorz},
title = {{Brief Announcement: New Clocks, Fast Line Formation and Self-Replication Population Protocols}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {44:1--44:3},
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.44},
URN = {urn:nbn:de:0030-drops-172351},
doi = {10.4230/LIPIcs.DISC.2022.44},
annote = {Keywords: Population protocols, network constructors, probabilistic bubble-sort, self-replication}
}
Document
Brief Announcement
Brief Announcement: Performance Anomalies in Concurrent Data Structure Microbenchmarks
Abstract
Recent decades have witnessed a surge in the development of concurrent data structures with an increasing interest in data structures implementing concurrent sets (CSets). Microbenchmarking tools are frequently utilized to evaluate and compare performance differences across concurrent data structures. The underlying structure and design of the microbenchmarks themselves can play a hidden but influential role in performance results. However, the impact of microbenchmark design has not been well investigated. In this work, we illustrate instances where concurrent data structure performance results reported by a microbenchmark can vary 10-100x depending on the microbenchmark implementation details. We investigate factors leading to performance variance across three popular microbenchmarks and outline cases in which flawed microbenchmark design can lead to an inversion of performance results between two concurrent data structure implementations. We further derive a prescriptive approach for best practices in the design and utilization of concurrent data structure microbenchmarks.
Cite as
Rosina F. Kharal and Trevor Brown. Brief Announcement: Performance Anomalies in Concurrent Data Structure Microbenchmarks. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 45:1-45:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{kharal_et_al:LIPIcs.DISC.2022.45,
author = {Kharal, Rosina F. and Brown, Trevor},
title = {{Brief Announcement: Performance Anomalies in Concurrent Data Structure Microbenchmarks}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {45:1--45:3},
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.45},
URN = {urn:nbn:de:0030-drops-172363},
doi = {10.4230/LIPIcs.DISC.2022.45},
annote = {Keywords: concurrent microbenchmarks, concurrent data structures, high performance simulations, PRNGs}
}
Document
Brief Announcement
Brief Announcement: Gathering Despite Defected View
Abstract
In this paper, we provide a new perspective on the observation by robots; a robot cannot necessarily observe all other robots regardless of distances to them. We introduce a new computational model with defected views called a (N,k)-defected model where k robots among N-1 other robots can be observed. We propose two gathering algorithms: one in the adversarial (N,N-2)-defected model for N ≥ 5 (where N is the number of robots) and the other in the distance-based (4,2)-defected model. Moreover, we present two impossibility results for a (3,1)-defected model and a relaxed (N, N-2)-defected model respectively. This announcement is short; the full paper is available at [Yonghwan Kim and others, 2022].
Cite as
Yonghwan Kim, Masahiro Shibata, Yuichi Sudo, Junya Nakamura, Yoshiaki Katayama, and Toshimitsu Masuzawa. Brief Announcement: Gathering Despite Defected View. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 46:1-46:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{kim_et_al:LIPIcs.DISC.2022.46,
author = {Kim, Yonghwan and Shibata, Masahiro and Sudo, Yuichi and Nakamura, Junya and Katayama, Yoshiaki and Masuzawa, Toshimitsu},
title = {{Brief Announcement: Gathering Despite Defected View}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {46:1--46:3},
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.46},
URN = {urn:nbn:de:0030-drops-172377},
doi = {10.4230/LIPIcs.DISC.2022.46},
annote = {Keywords: mobile robot, gathering, defected view model}
}
Document
Brief Announcement
Brief Announcement: An Effective Geometric Communication Structure for Programmable Matter
Abstract
The concept of programmable matter envisions a very large number of tiny and simple robot particles forming a smart material that can change its physical properties and shape based on the outcome of computation and movement performed by the individual particles in a concurrent manner. We use geometric insights to develop a new type of shortest path tree for programmable matter systems. Our feather trees utilize geometry to allow particles and information to traverse the programmable matter structure via shortest paths even in the presence of multiple overlapping trees.
Cite as
Irina Kostitsyna, Tom Peters, and Bettina Speckmann. Brief Announcement: An Effective Geometric Communication Structure for Programmable Matter. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 47:1-47:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{kostitsyna_et_al:LIPIcs.DISC.2022.47,
author = {Kostitsyna, Irina and Peters, Tom and Speckmann, Bettina},
title = {{Brief Announcement: An Effective Geometric Communication Structure for Programmable Matter}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {47:1--47:3},
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.47},
URN = {urn:nbn:de:0030-drops-172386},
doi = {10.4230/LIPIcs.DISC.2022.47},
annote = {Keywords: Programmable matter, amoebot model, shape reconfiguration}
}
Document
Brief Announcement
Brief Announcement: Distributed Quantum Interactive Proofs
Abstract
The study of distributed interactive proofs was initiated by Kol, Oshman, and Saxena [PODC 2018] as a generalization of distributed decision mechanisms (proof-labeling schemes, etc.), and has received a lot of attention in recent years. In distributed interactive proofs, the nodes of an n-node network G can exchange short messages (called certificates) with a powerful prover. The goal is to decide if the input (including G itself) belongs to some language, with as few turns of interaction and as few bits exchanged between nodes and the prover as possible. There are several results showing that the size of certificates can be reduced drastically with a constant number of interactions compared to non-interactive distributed proofs.
In this brief announcement, we introduce the quantum counterpart of distributed interactive proofs: certificates can now be quantum bits, and the nodes of the network can perform quantum computation. The main result of this paper shows that by using quantum distributed interactive proofs, the number of interactions can be significantly reduced. More precisely, our main result shows that for any constant k, the class of languages that can be decided by a k-turn classical (i.e., non-quantum) distributed interactive protocol with f(n)-bit certificate size is contained in the class of languages that can be decided by a 5-turn distributed quantum interactive protocol with O(f(n))-bit certificate size. We also show that if we allow to use shared randomness, the number of turns can be reduced to 3-turn. Since no similar turn-reduction classical technique is currently known, our result gives evidence of the power of quantum computation in the setting of distributed interactive proofs as well.
Cite as
François Le Gall, Masayuki Miyamoto, and Harumichi Nishimura. Brief Announcement: Distributed Quantum Interactive Proofs. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 48:1-48:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{legall_et_al:LIPIcs.DISC.2022.48,
author = {Le Gall, Fran\c{c}ois and Miyamoto, Masayuki and Nishimura, Harumichi},
title = {{Brief Announcement: Distributed Quantum Interactive Proofs}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {48:1--48:3},
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.48},
URN = {urn:nbn:de:0030-drops-172396},
doi = {10.4230/LIPIcs.DISC.2022.48},
annote = {Keywords: distributed interactive proofs, distributed verification, quantum computation}
}
Document
Brief Announcement
Brief Announcement: Null Messages, Information and Coordination
Abstract
This paper investigates how null messages can transfer information in fault-prone synchronous systems. The notion of an f-resilient message block is defined and is shown to capture the fundamental communication pattern for knowledge transfer. In general, this pattern combines both null messages and explicit messages. It thus provides a fault-tolerant extension of the classic notion of a message-chain. Based on the above, we provide tight necessary and sufficient characterizations of the generalized communication patterns that can serve to solve the distributed tasks of (nice-run) Signalling and Ordered Response.
Cite as
Raïssa Nataf, Guy Goren, and Yoram Moses. Brief Announcement: Null Messages, Information and Coordination. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 49:1-49:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{nataf_et_al:LIPIcs.DISC.2022.49,
author = {Nataf, Ra\"{i}ssa and Goren, Guy and Moses, Yoram},
title = {{Brief Announcement: Null Messages, Information and Coordination}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {49:1--49:3},
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.49},
URN = {urn:nbn:de:0030-drops-172409},
doi = {10.4230/LIPIcs.DISC.2022.49},
annote = {Keywords: null messages, fault tolerance, coordination, information flow}
}
Document
Brief Announcement
Brief Announcement: Asymmetric Mutual Exclusion for RDMA
Abstract
In this brief announcement, we define operation asymmetry, which captures how processes may interact with an object differently, and discuss its implications in the context of a popular network communication technology, remote direct memory access (RDMA). Then, we present a novel approach to mutual exclusion for RDMA-based distributed synchronization under operation asymmetry. Our approach avoids RDMA loopback for local processes and guarantees starvation-freedom and fairness.
Cite as
Jacob Nelson-Slivon, Lewis Tseng, and Roberto Palmieri. Brief Announcement: Asymmetric Mutual Exclusion for RDMA. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 50:1-50:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{nelsonslivon_et_al:LIPIcs.DISC.2022.50,
author = {Nelson-Slivon, Jacob and Tseng, Lewis and Palmieri, Roberto},
title = {{Brief Announcement: Asymmetric Mutual Exclusion for RDMA}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {50:1--50:3},
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.50},
URN = {urn:nbn:de:0030-drops-172417},
doi = {10.4230/LIPIcs.DISC.2022.50},
annote = {Keywords: Mutual exclusion, Synchronization, Remote direct memory access (RDMA)}
}
Document
Brief Announcement
Brief Announcement: Foraging in Particle Systems via Self-Induced Phase Changes
Abstract
The foraging problem asks how a collective of particles with limited computational, communication and movement capabilities can autonomously compress around a food source and disperse when the food is depleted or shifted, which may occur at arbitrary times. We would like the particles to iteratively self-organize, using only local interactions, to correctly gather whenever a food particle remains in a position long enough and search if no food particle has existed recently. Unlike previous approaches, these search and gather phases should be self-induced so as to be indefinitely repeatable as the food evolves, with microscopic changes to the food triggering macroscopic, system-wide phase transitions. We present a stochastic foraging algorithm based on a phase change in the fixed magnetization Ising model from statistical physics: Our algorithm is the first to leverage self-induced phase changes as an algorithmic tool. A key component of our algorithm is a careful token passing mechanism ensuring a dispersion broadcast wave will always outpace a compression wave.
Cite as
Shunhao Oh, Dana Randall, and Andréa W. Richa. Brief Announcement: Foraging in Particle Systems via Self-Induced Phase Changes. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 51:1-51:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{oh_et_al:LIPIcs.DISC.2022.51,
author = {Oh, Shunhao and Randall, Dana and Richa, Andr\'{e}a W.},
title = {{Brief Announcement: Foraging in Particle Systems via Self-Induced Phase Changes}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {51:1--51:3},
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.51},
URN = {urn:nbn:de:0030-drops-172423},
doi = {10.4230/LIPIcs.DISC.2022.51},
annote = {Keywords: Foraging, self-organized particle systems, compression, phase changes}
}
Document
Brief Announcement
Brief Announcement: Temporal Locality in Online Algorithms
Abstract
Online algorithms make decisions based on past inputs, with the goal of being competitive against an algorithm that sees also future inputs. In this work, we introduce time-local online algorithms; these are online algorithms in which the output at any given time is a function of only T latest inputs. Our main observation is that time-local online algorithms are closely connected to local distributed graph algorithms: distributed algorithms make decisions based on the local information in the spatial dimension, while time-local online algorithms make decisions based on the local information in the temporal dimension. We formalize this connection, and show how we can directly use the tools developed to study distributed approximability of graph optimization problems to prove upper and lower bounds on the competitive ratio achieved with time-local online algorithms. Moreover, we show how to use computational techniques to synthesize optimal time-local algorithms.
Cite as
Maciej Pacut, Mahmoud Parham, Joel Rybicki, Stefan Schmid, Jukka Suomela, and Aleksandr Tereshchenko. Brief Announcement: Temporal Locality in Online Algorithms. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 52:1-52:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{pacut_et_al:LIPIcs.DISC.2022.52,
author = {Pacut, Maciej and Parham, Mahmoud and Rybicki, Joel and Schmid, Stefan and Suomela, Jukka and Tereshchenko, Aleksandr},
title = {{Brief Announcement: Temporal Locality in Online Algorithms}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {52:1--52:3},
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.52},
URN = {urn:nbn:de:0030-drops-172431},
doi = {10.4230/LIPIcs.DISC.2022.52},
annote = {Keywords: Online algorithms, distributed algorithms}
}