Volume
LIPIcs, Volume 253
26th International Conference on Principles of Distributed Systems (OPODIS 2022)
Event
OPODIS 2022, December 13-15, 2022, Brussels, BelgiumEditors
Publication Details
- published at: 2023-02-15
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-265-5
- DBLP: db/conf/opodis/opodis2022
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 253, OPODIS 2022, Complete Volume
Abstract
LIPIcs, Volume 253, OPODIS 2022, Complete Volume
Cite as
26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 1-536, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@Proceedings{hillel_et_al:LIPIcs.OPODIS.2022,
title = {{LIPIcs, Volume 253, OPODIS 2022, Complete Volume}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {1--536},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022},
URN = {urn:nbn:de:0030-drops-176190},
doi = {10.4230/LIPIcs.OPODIS.2022},
annote = {Keywords: LIPIcs, Volume 253, OPODIS 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
26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{hillel_et_al:LIPIcs.OPODIS.2022.0,
author = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {0:i--0:xiv},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.0},
URN = {urn:nbn:de:0030-drops-176203},
doi = {10.4230/LIPIcs.OPODIS.2022.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
Theory Meets Practice in the Algorand Blockchain (Invited Talk)
Abstract
Robust and effective distributed systems require good theory and good engineering, not separately but in concert: user requirements and system constraints are not merely implementation details but often must inform the design of algorithms for such systems. Blockchains are an excellent example. The heart of a blockchain is its (Byzantine) consensus protocol, and consensus protocols have been extensively studied in the theory community for decades. But traditional consensus protocols are not directly applicable to blockchains, which have, or hope to have, millions of participants. Furthermore, public blockchains, which allow anyone to participate, must have some mechanism to guarantee the security of the protocol, and traditional fault models do not adequately capture the assumptions of such mechanisms. In this talk, I will discuss these and other ways in which theory and practice meet in the context of the Algorand blockchain, and how Algorand is able to achieve high transaction throughput with low latency.
Cite as
Victor Luchangco. Theory Meets Practice in the Algorand Blockchain (Invited Talk). In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{luchangco:LIPIcs.OPODIS.2022.1,
author = {Luchangco, Victor},
title = {{Theory Meets Practice in the Algorand Blockchain}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {1:1--1:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.1},
URN = {urn:nbn:de:0030-drops-176219},
doi = {10.4230/LIPIcs.OPODIS.2022.1},
annote = {Keywords: Theory and practice, Design of distributed systems, Blockchain, Consensus, Algorand}
}
Document
Invited Talk
Recoverable Computing (Invited Talk)
Abstract
Non-Volatile Memory (NVM) is an emerging memory technology which aims to address the high computational demands of modern applications and support recovery from crashes. Recovery ensures that after a crash every executed operation is able to recover and return a correct response. This talk will shed light on different aspects of the question "How does concurrent computing change in systems with NVM and what will the impact of persistent memory be on the way we compute?". Specifically, this talk addresses the following four main challenges in NVM computing.
- Challenge 1: How to appropriately model and abstract fundamental aspects of NVM computing? The talk will provide an overview of the theoretical framework for NVM computing, including a discussion of correctness conditions, progress guarantees, failure types, etc.
- Challenge 2: How to compute in a recoverable way at no significant cost? The talk will summarize state-of-the-art generic approaches for deriving recoverable synchronization algorithms, as well as recoverable implementations of many widely-used concurrent data structures on top of them. The collection of data structures includes fundamental structures, such as stacks and queues, but also more complex structures that implement sets, such as linked-lists and trees.
- Challenge 3: How to analyze the cost of recoverable algorithms? The talk will present a way of analyzing the cost of persistence instructions, not by simply counting them but by separating them into categories based on the impact they have on the performance. This analysis reveals that understanding the actual persistence cost of an algorithm in machines with NVM, is more complicated than previously thought, and requires a thorough evaluation, since the performance impact of different persistence instructions may greatly vary.
- Challenge 4: When is Recoverable Consensus Harder Than Consensus? The talk will briefly discuss the ability of different shared object types to solve recoverable consensus using NVM when processes crash and recover, and it will compare the difficulty of solving recoverable consensus to the difficulty of solving the standard consensus problem in a system with halting failures. For each of the above challenges, the talk will present main results, provide some of the details of the best-performing techniques, and discuss open problems and directions for further research. Some of the results that will be discussed in detail have appeared in [Attiya et al., 2022; Delporte-Gallet et al., 2022; Fatourou et al., 2022].
Cite as
Panagiota Fatourou. Recoverable Computing (Invited Talk). In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{fatourou:LIPIcs.OPODIS.2022.2,
author = {Fatourou, Panagiota},
title = {{Recoverable Computing}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {2:1--2:2},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.2},
URN = {urn:nbn:de:0030-drops-176221},
doi = {10.4230/LIPIcs.OPODIS.2022.2},
annote = {Keywords: non-volatile memory, persistence, detectability, durability, recoverable algorithms, recoverable data structures, persistent objects, stacks, queues, heaps, synchronization, universal constructions, software combining, lock-freedom, wait-freedom, persistence cost analysis}
}
Document
Invited Talk
Realistic Self-Stabilization (Invited Talk)
Abstract
It is almost fifty years since Dijkstra coined the term "self-stabilization" to denote a distributed system able to recover correct behavior starting from any arbitrary (even unreachable) configuration. His seminal paper triggered many works since then, exploring over the years new variants of the original concept, new application domains, and new complexity results. While the huge majority of those contributions relates to theory, considering computability and worst case complexity issues, this talk revisits old and recent contributions from the prism of "realistic" distributed systems, aiming to address the following question: is self-stabilization relevant in practice for distributed systems?
Cite as
Sébastien Tixeuil. Realistic Self-Stabilization (Invited Talk). In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{tixeuil:LIPIcs.OPODIS.2022.3,
author = {Tixeuil, S\'{e}bastien},
title = {{Realistic Self-Stabilization}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {3:1--3:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.3},
URN = {urn:nbn:de:0030-drops-176232},
doi = {10.4230/LIPIcs.OPODIS.2022.3},
annote = {Keywords: Self-stabilization, Distributed systems, Probable stabilization, Performance evaluation, Asynchronous message passing, Multi-tolerance}
}
Document
Efficient Wait-Free Queue Algorithms with Multiple Enqueuers and Multiple Dequeuers
Abstract
Despite the widespread usage of FIFO queues in distributed applications, designing efficient wait-free implementations of queues remains a challenge. The majority of wait-free queue implementations restrict either the number of dequeuers or the number of enqueuers that can operate on the queue, even when they use strong synchronization primitives, like the Compare&Swap. If we do not limit the number of processes that can perform enqueue and dequeue operations, the best-known upper bound on the worst case step complexity for a wait-free queue is given by [Khanchandani and Wattenhofer, 2018]. In particular, they present an implementation of a multiple dequeuer multiple enqueuer wait-free queue whose worst case step complexity is in O(√n), where n is the number of processes. In this work, we investigate whether it is possible to improve this bound. In particular, we present a wait-free FIFO queue implementation that supports n enqueuers and k dequeuers where the worst case step complexity of an Enqueue operation is in O(log n) and of a Dequeue operation is in O(k log n).
Then, we show that if the semantics of the queue can be relaxed, by allowing concurrent Dequeue operations to retrieve the same element, then we can achieve O(log n) worst-case step complexity for both the Enqueue and Dequeue operations.
Cite as
Colette Johnen, Adnane Khattabi, and Alessia Milani. Efficient Wait-Free Queue Algorithms with Multiple Enqueuers and Multiple Dequeuers. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{johnen_et_al:LIPIcs.OPODIS.2022.4,
author = {Johnen, Colette and Khattabi, Adnane and Milani, Alessia},
title = {{Efficient Wait-Free Queue Algorithms with Multiple Enqueuers and Multiple Dequeuers}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {4:1--4:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.4},
URN = {urn:nbn:de:0030-drops-176240},
doi = {10.4230/LIPIcs.OPODIS.2022.4},
annote = {Keywords: Distributed computing, distributed algorithms, FIFO queue, shared memory, fault tolerance, concurrent data structures, relaxed specifications, complexity}
}
Document
EEMARQ: Efficient Lock-Free Range Queries with Memory Reclamation
Abstract
Multi-Version Concurrency Control (MVCC) is a common mechanism for achieving linearizable range queries in database systems and concurrent data-structures. The core idea is to keep previous versions of nodes to serve range queries, while still providing atomic reads and updates. Existing concurrent data-structure implementations, that support linearizable range queries, are either slow, use locks, or rely on blocking reclamation schemes. We present EEMARQ, the first scheme that uses MVCC with lock-free memory reclamation to obtain a fully lock-free data-structure supporting linearizable inserts, deletes, contains, and range queries. Evaluation shows that EEMARQ outperforms existing solutions across most workloads, with lower space overhead and while providing full lock freedom.
Cite as
Gali Sheffi, Pedro Ramalhete, and Erez Petrank. EEMARQ: Efficient Lock-Free Range Queries with Memory Reclamation. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 5:1-5:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{sheffi_et_al:LIPIcs.OPODIS.2022.5,
author = {Sheffi, Gali and Ramalhete, Pedro and Petrank, Erez},
title = {{EEMARQ: Efficient Lock-Free Range Queries with Memory Reclamation}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {5:1--5:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.5},
URN = {urn:nbn:de:0030-drops-176253},
doi = {10.4230/LIPIcs.OPODIS.2022.5},
annote = {Keywords: safe memory reclamation, lock-freedom, snapshot, concurrency, range query}
}
Document
The Step Complexity of Multidimensional Approximate Agreement
Abstract
Approximate agreement allows a set of n processes to obtain outputs that are within a specified distance ε > 0 of one another and within the convex hull of the inputs.
When the inputs are real numbers, there is a wait-free shared-memory approximate agreement algorithm [Moran, 1995] whose step complexity is in O(n log(S/ε)), where S, the spread of the inputs, is the maximal distance between inputs. There is another wait-free algorithm [Schenk, 1995] that avoids the dependence on n and achieves O(log(M/ε)) step complexity where M, the magnitude of the inputs, is the absolute value of the maximal input.
This paper considers whether it is possible to obtain an approximate agreement algorithm whose step complexity depends on neither n nor the magnitude of the inputs, which can be much larger than their spread. On the negative side, we prove that Ω(min{(log M)/(log log M), (√log n)/(log log n)}) is a lower bound on the step complexity of approximate agreement, even when the inputs are real numbers. On the positive side, we prove that a polylogarithmic dependence on n and S/ε can be achieved, by presenting an approximate agreement algorithm with O(log n (log n + log(S/ε))) step complexity. Our algorithm works for multidimensional domains. The step complexity can be further restricted to be in O(min{log n (log n + log (S/ε)), log(M/ε)}) when the inputs are real numbers.
Cite as
Hagit Attiya and Faith Ellen. The Step Complexity of Multidimensional Approximate Agreement. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{attiya_et_al:LIPIcs.OPODIS.2022.6,
author = {Attiya, Hagit and Ellen, Faith},
title = {{The Step Complexity of Multidimensional Approximate Agreement}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {6:1--6:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.6},
URN = {urn:nbn:de:0030-drops-176261},
doi = {10.4230/LIPIcs.OPODIS.2022.6},
annote = {Keywords: approximate agreement, conflict detection, shared memory, wait-freedom, step complexity}
}
Document
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 the 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 set of recommendations for best practices in the design and usage of concurrent data structure microbenchmarks and explore advanced features in the Setbench microbenchmark.
Cite as
Rosina F. Kharal and Trevor Brown. Performance Anomalies in Concurrent Data Structure Microbenchmarks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{kharal_et_al:LIPIcs.OPODIS.2022.7,
author = {Kharal, Rosina F. and Brown, Trevor},
title = {{Performance Anomalies in Concurrent Data Structure Microbenchmarks}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {7:1--7:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.7},
URN = {urn:nbn:de:0030-drops-176273},
doi = {10.4230/LIPIcs.OPODIS.2022.7},
annote = {Keywords: concurrent microbenchmarks, concurrent data structures, concurrent performance evaluation, PRNGs, parallel computing}
}
Document
Robust and Fast Blockchain State Synchronization
Abstract
State synchronization, the process by which a new or recovering peer catches up with the state of other operational peers, is critical to the operation of blockchain-based systems. Existing approaches to state synchronization typically involve downloading snapshots of system state. Such approaches introduce an attack vector from malicious peers that can significantly degrade performance. Moreover, the process of creating snapshots leads to performance hiccups. This paper presents a technique for peers to catch up with operational peers without trusting any particular peer and gracefully recover from misbehavior during the process. We have integrated our design into a production blockchain middleware. Our evaluation shows that during operation, the transaction throughput is consistently higher without pauses for snapshot construction. Moreover, the time it takes for a new peer to join the blockchain is halved, while at the same time tolerating Byzantine peers.
Cite as
Enrique Fynn, Ethan Buchman, Zarko Milosevic, Robert Soulé, and Fernando Pedone. Robust and Fast Blockchain State Synchronization. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{fynn_et_al:LIPIcs.OPODIS.2022.8,
author = {Fynn, Enrique and Buchman, Ethan and Milosevic, Zarko and Soul\'{e}, Robert and Pedone, Fernando},
title = {{Robust and Fast Blockchain State Synchronization}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {8:1--8:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.8},
URN = {urn:nbn:de:0030-drops-176280},
doi = {10.4230/LIPIcs.OPODIS.2022.8},
annote = {Keywords: state synchronization, replication, blockchain}
}
Document
A Privacy-Preserving and Transparent Certification System for Digital Credentials
Abstract
A certification system is responsible for issuing digital credentials, which attest claims about a subject, e.g., an academic diploma. Such credentials are valuable for individuals and society, and widespread adoption requires a trusted certification system. Trust can be gained by being transparent when issuing and verifying digital credentials. However, there is a fundamental tradeoff between privacy and transparency. For instance, admitting a student to an academic program must preserve the student’s privacy, i.e., the student’s grades must not be revealed to unauthorized parties. At the same time, other applicants may demand transparency to ensure fairness in the admission process. Thus, building a certification system with the right balance between privacy and transparency is challenging.
This paper proposes a novel design for a certification system that provides sufficient transparency and preserves privacy through selective disclosure of claims such that authorized parties can verify them. Moreover, unauthorized parties can also verify the correctness of the certification process without compromising privacy. We achieve this using an incremental Merkle tree of cryptographic commitments to users' credentials. The commitments are added to the tree based on verifying zero-knowledge issuance proofs. Users store credentials off-chain and can prove the ownership and authenticity of credentials without revealing their commitments. Further, our approach enables users to prove statements about the credential’s claims in zero-knowledge. Our design offers a cost-efficient solution, reducing the amount of linkable on-chain data by up to 79% per credential compared to prior work, while maintaining transparency.
Cite as
Rodrigo Q. Saramago, Hein Meling, and Leander N. Jehl. A Privacy-Preserving and Transparent Certification System for Digital Credentials. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 9:1-9:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{saramago_et_al:LIPIcs.OPODIS.2022.9,
author = {Saramago, Rodrigo Q. and Meling, Hein and Jehl, Leander N.},
title = {{A Privacy-Preserving and Transparent Certification System for Digital Credentials}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {9:1--9:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.9},
URN = {urn:nbn:de:0030-drops-176294},
doi = {10.4230/LIPIcs.OPODIS.2022.9},
annote = {Keywords: verifiable credentials, privacy-preserving, zero-knowledge, blockchain}
}
Document
When Is Spring Coming? A Security Analysis of Avalanche Consensus
Abstract
Avalanche is a blockchain consensus protocol with exceptionally low latency and high throughput. This has swiftly established the corresponding token as a top-tier cryptocurrency. Avalanche achieves such remarkable metrics by substituting proof of work with a random sampling mechanism. The protocol also differs from Bitcoin, Ethereum, and many others by forming a directed acyclic graph (DAG) instead of a chain. It does not totally order all transactions, establishes a partial order among them, and accepts transactions in the DAG that satisfy specific properties. Such parallelism is widely regarded as a technique that increases the efficiency of consensus.
Despite its success, Avalanche consensus lacks a complete abstract specification and a matching formal analysis. To address this drawback, this work provides first a detailed formulation of Avalanche through pseudocode. This includes features that are omitted from the original whitepaper or are only vaguely explained in the documentation. Second, the paper gives an analysis of the formal properties fulfilled by Avalanche in the sense of a generic broadcast protocol that only orders related transactions. Last but not least, the analysis reveals a vulnerability that affects the liveness of the protocol. A possible solution that addresses the problem is also proposed.
Cite as
Ignacio Amores-Sesar, Christian Cachin, and Enrico Tedeschi. When Is Spring Coming? A Security Analysis of Avalanche Consensus. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{amoressesar_et_al:LIPIcs.OPODIS.2022.10,
author = {Amores-Sesar, Ignacio and Cachin, Christian and Tedeschi, Enrico},
title = {{When Is Spring Coming? A Security Analysis of Avalanche Consensus}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {10:1--10:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.10},
URN = {urn:nbn:de:0030-drops-176307},
doi = {10.4230/LIPIcs.OPODIS.2022.10},
annote = {Keywords: Avalanche, security analysis, generic broadcast}
}
Document
Computational Power of a Single Oblivious Mobile Agent in Two-Edge-Connected Graphs
Abstract
We investigated the computational power of a single mobile agent in an n-node graph with storage (i.e., node memory). Generally, a system with one-bit agent memory and O(1)-bit storage is as powerful as that with O(n)-bit agent memory and O(1)-bit storage. Thus, we focus on the difference between one-bit memory and oblivious (i.e., zero-bit memory) agents. Although their computational powers are not equivalent, all the known results exhibiting such a difference rely on the fact that oblivious agents cannot transfer any information from one side to the other across the bridge edge. Hence, our main question is as follows: Are the computational powers of one-bit memory and oblivious agents equivalent in 2-edge-connected graphs or not? The main contribution of this study is to answer this question under the relaxed assumption that each node has O(logΔ)-bit storage (where Δ is the maximum degree of the graph). We present an algorithm for simulating any algorithm for a single one-bit memory agent using an oblivious agent with O(n²)-time overhead per round. Our results imply that the topological structure of graphs differentiating the computational powers of oblivious and non-oblivious agents is completely characterized by the existence of bridge edges.
Cite as
Taichi Inoue, Naoki Kitamura, Taisuke Izumi, and Toshimitsu Masuzawa. Computational Power of a Single Oblivious Mobile Agent in Two-Edge-Connected Graphs. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{inoue_et_al:LIPIcs.OPODIS.2022.11,
author = {Inoue, Taichi and Kitamura, Naoki and Izumi, Taisuke and Masuzawa, Toshimitsu},
title = {{Computational Power of a Single Oblivious Mobile Agent in Two-Edge-Connected Graphs}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {11:1--11:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.11},
URN = {urn:nbn:de:0030-drops-176311},
doi = {10.4230/LIPIcs.OPODIS.2022.11},
annote = {Keywords: mobile agent, depth-first search, space complexity}
}
Document
Line Search for an Oblivious Moving Target
Abstract
Consider search on an infinite line involving an autonomous robot starting at the origin of the line and an oblivious moving target at initial distance d ≥ 1 from it. The robot can change direction and move anywhere on the line with constant maximum speed 1 while the target is also moving on the line with constant speed v > 0 but is unable to change its speed or direction. The goal is for the robot to catch up to the target in as little time as possible.
The classic case where v = 0 and the target’s initial distance d is unknown to the robot is the well-studied "cow-path problem". Alpert and Gal [Steve Alpern and Shmuel Gal, 2003] gave an optimal algorithm for the case where a target with unknown initial distance d is moving away from the robot with a known speed v < 1. In this paper we design and analyze search algorithms for the remaining possible knowledge situations, namely, when d and v are known, when v is known but d is unknown, when d is known but v is unknown, and when both v and d are unknown. Furthermore, for each of these knowledge models we consider separately the case where the target is moving away from the origin and the case where it is moving toward the origin. We design algorithms and analyze competitive ratios for all eight cases above. The resulting competitive ratios are shown to be optimal when the target is moving towards the origin as well as when v is known and the target is moving away from the origin.
Cite as
Jared Coleman, Evangelos Kranakis, Danny Krizanc, and Oscar Morales-Ponce. Line Search for an Oblivious Moving Target. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{coleman_et_al:LIPIcs.OPODIS.2022.12,
author = {Coleman, Jared and Kranakis, Evangelos and Krizanc, Danny and Morales-Ponce, Oscar},
title = {{Line Search for an Oblivious Moving Target}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {12:1--12:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.12},
URN = {urn:nbn:de:0030-drops-176325},
doi = {10.4230/LIPIcs.OPODIS.2022.12},
annote = {Keywords: Infinite Line, Knowledge, Oblivious, Robot, Search, Search-Time, Speed, Target}
}
Document
Randomized Byzantine Gathering in Rings
Abstract
We study the problem of gathering k anonymous mobile agents on a ring with n nodes. Importantly, f out of the k anonymous agents are Byzantine. The agents operate synchronously and in an autonomous fashion. In each round, each agent can communicate with other agents co-located with it by broadcasting a message. After receiving all the messages, each agent decides to either move to a neighbouring node or stay put. We begin with the k agents placed arbitrarily on the ring, and the task is to gather all the good agents in a single node. The task is made harder by the presence of Byzantine agents, which are controlled by a single Byzantine adversary. Byzantine agents can deviate arbitrarily from the protocol. The Byzantine adversary is computationally unbounded. Additionally, the Byzantine adversary is adaptive in the sense that it can capitalize on information gained over time (including the current round) to choreograph the actions of Byzantine agents. Specifically, the entire state of the system, which includes messages sent by all the agents and any random bits generated by the agents, is known to the Byzantine adversary before all the agents move. Thus the Byzantine adversary can compute the positioning of good agents across the ring and choreograph the movement of Byzantine agents accordingly. Moreover, we consider two settings: standard and visual tracking setting. With visual tracking, agents have the ability to track other agents that are moving along with them. In the standard setting, agents do not have such an ability.
In the standard setting we can achieve gathering in 𝒪(nlog nlog k) rounds with high probability and can handle 𝒪(k/(log k)) number of Byzantine agents. With visual tracking, we can achieve gathering faster in 𝒪(n log n) rounds whp and can handle any constant fraction of the total number of agents being Byzantine.
Cite as
John Augustine, Arnhav Datar, and Nischith Shadagopan. Randomized Byzantine Gathering in Rings. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{augustine_et_al:LIPIcs.OPODIS.2022.13,
author = {Augustine, John and Datar, Arnhav and Shadagopan, Nischith},
title = {{Randomized Byzantine Gathering in Rings}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {13:1--13:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.13},
URN = {urn:nbn:de:0030-drops-176333},
doi = {10.4230/LIPIcs.OPODIS.2022.13},
annote = {Keywords: Mobile agents and robots}
}
Document
Gathering of Mobile Robots with Defected Views
Abstract
An autonomous mobile robot system consisting of many mobile computational entities (called robots) attracts much attention of researchers, and it is an emerging issue for a recent couple of decades to clarify the relation between the capabilities of robots and solvability of the problems.
Generally, each robot can observe all other robots as long as there are no restrictions on visibility range or obstructions, regardless of the number of robots. 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 call this new computational model the defected view model. Under this model, in this paper, we consider the gathering problem that requires all the robots to gather at the same non-predetermined point and propose two algorithms to solve the gathering problem in the adversarial (N,N-2)-defected model for N ≥ 5 (where each robot observes at most N-2 robots chosen adversarially) and the distance-based (4,2)-defected model (where each robot observes at most two robots closest to itself), respectively, where N is the number of robots. Moreover, we present an impossibility result showing that there is no (deterministic) gathering algorithm in the adversarial or distance-based (3,1)-defected model, and we also show an impossibility result for the gathering in a relaxed (N, N-2)-defected model.
Cite as
Yonghwan Kim, Masahiro Shibata, Yuichi Sudo, Junya Nakamura, Yoshiaki Katayama, and Toshimitsu Masuzawa. Gathering of Mobile Robots with Defected Views. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{kim_et_al:LIPIcs.OPODIS.2022.14,
author = {Kim, Yonghwan and Shibata, Masahiro and Sudo, Yuichi and Nakamura, Junya and Katayama, Yoshiaki and Masuzawa, Toshimitsu},
title = {{Gathering of Mobile Robots with Defected Views}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {14:1--14:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.14},
URN = {urn:nbn:de:0030-drops-176349},
doi = {10.4230/LIPIcs.OPODIS.2022.14},
annote = {Keywords: mobile robot, gathering, defected view model}
}
Document
A Unifying Approach to Efficient (Near)-Gathering of Disoriented Robots with Limited Visibility
Abstract
We consider a swarm of n robots in a d-dimensional Euclidean space. The robots are oblivious (no persistent memory), disoriented (no common coordinate system/compass), and have limited visibility (observe other robots up to a constant distance). The basic formation task Gathering requires that all robots reach the same, not predefined position. In the related NearGathering task, they must reach distinct positions in close proximity such that every robot sees the entire swarm. In the considered setting, Gathering can be solved in 𝒪(n + Δ²) synchronous rounds both in two and three dimensions, where Δ denotes the initial maximal distance of two robots [Hideki Ando et al., 1999; Michael Braun et al., 2020; Bastian Degener et al., 2011].
In this work, we formalize a key property of efficient Gathering protocols and use it to define λ-contracting protocols. Any such protocol gathers n robots in the d-dimensional space in 𝒪(Δ²) synchronous rounds, for d ≥ 2. For d = 1, any λ-contracting protocol gathers in optimal time 𝒪(Δ). Moreover, we prove a corresponding lower bound stating that any protocol in which robots move to target points inside the local convex hulls of their neighborhoods - λ-contracting protocols have this property - requires Ω(Δ²) rounds to gather all robots (d > 1). Among others, we prove that the d-dimensional generalization of the GTC-protocol [Hideki Ando et al., 1999] is λ-contracting. Remarkably, our improved and generalized runtime bound is independent of n and d.
We also introduce an approach to make any λ-contracting protocol collision-free (robots never occupy the same position) to solve NearGathering. The resulting protocols maintain the runtime of Θ (Δ²) and work even in the semi-synchronous model. This yields the first NearGathering protocols for disoriented robots and the first proven runtime bound. In particular, combined with results from [Paola Flocchini et al., 2017] for robots with global visibility, we obtain the first protocol to solve Uniform Circle Formation (arrange the robots on the vertices of a regular n-gon) for oblivious, disoriented robots with limited visibility.
Cite as
Jannik Castenow, Jonas Harbig, Daniel Jung, Peter Kling, Till Knollmann, and Friedhelm Meyer auf der Heide. A Unifying Approach to Efficient (Near)-Gathering of Disoriented Robots with Limited Visibility. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 15:1-15:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{castenow_et_al:LIPIcs.OPODIS.2022.15,
author = {Castenow, Jannik and Harbig, Jonas and Jung, Daniel and Kling, Peter and Knollmann, Till and Meyer auf der Heide, Friedhelm},
title = {{A Unifying Approach to Efficient (Near)-Gathering of Disoriented Robots with Limited Visibility}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {15:1--15:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.15},
URN = {urn:nbn:de:0030-drops-176350},
doi = {10.4230/LIPIcs.OPODIS.2022.15},
annote = {Keywords: mobile robots, gathering, limited visibility, runtime, collision avoidance, near-gathering}
}
Document
New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks
Abstract
In 1985, Dolev and Reischuk proved a fundamental communication lower bounds on protocols achieving fault tolerant synchronous broadcast and consensus: any deterministic protocol solving those tasks (even against omission faults) requires at least a quadratic number of messages to be sent by nonfaulty parties. In contrast, many blockchain systems achieve consensus with seemingly linear communication per instance against Byzantine faults. We explore this dissonance in three main ways. First, we extend the Dolev-Reischuk family of lower bounds and prove a new lower bound for Crusader Broadcast protocols. Our lower bound for crusader broadcast requires non-trivial extensions and a much stronger Byzantine adversary with the ability to simulate honest parties. Secondly, we extend our lower bounds to all-but-m Crusader Broadcast, in which up to m parties are allowed to output a different value. Finally, we discuss the ways in which these lower bounds relate to the security of blockchain systems. We show how Eclipse-style attacks in such systems can be viewed as specific instances of the attacks used in our lower bound for Crusader Broadcast. This connection suggests a more systematic way of analyzing and reasoning about Eclipse-style attacks through the lens of the Dolev-Reischuk family of attacks.
Cite as
Ittai Abraham and Gilad Stern. New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{abraham_et_al:LIPIcs.OPODIS.2022.16,
author = {Abraham, Ittai and Stern, Gilad},
title = {{New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {16:1--16:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.16},
URN = {urn:nbn:de:0030-drops-176368},
doi = {10.4230/LIPIcs.OPODIS.2022.16},
annote = {Keywords: consensus, crusader broadcast, Byzantine fault tolerance, blockchain, synchrony, lower bounds}
}
Document
Quorum Systems in Permissionless Networks
Abstract
Fail-prone systems, and their quorum systems, are useful tools for the design of distributed algorithms. However, fail-prone systems as studied so far require every process to know the full system membership in order to guarantee safety through globally intersecting quorums. Thus, they are of little help in an open, permissionless setting, where such knowledge may not be available. We propose to generalize the theory of fail-prone systems to make it applicable to permissionless systems. We do so by enabling processes not only to make assumptions about failures, but also to make assumptions about the assumptions of other processes. Thus, by transitivity, processes that do not even know of any common process may nevertheless have intersecting quorums and solve, for example, reliable broadcast. Our model generalizes existing models such as the classic fail-prone system model [Malkhi and Reiter, 1998] and the asymmetric fail-prone system model [Cachin and Tackmann, OPODIS 2019]. Moreover, it gives a characterization with standard formalism of the model used by the Stellar blockchain.
Cite as
Christian Cachin, Giuliano Losa, and Luca Zanolini. Quorum Systems in Permissionless Networks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 17:1-17:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{cachin_et_al:LIPIcs.OPODIS.2022.17,
author = {Cachin, Christian and Losa, Giuliano and Zanolini, Luca},
title = {{Quorum Systems in Permissionless Networks}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {17:1--17:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.17},
URN = {urn:nbn:de:0030-drops-176379},
doi = {10.4230/LIPIcs.OPODIS.2022.17},
annote = {Keywords: Permissionless systems, fail-prone system, quorum system}
}
Document
Make Every Word Count: Adaptive Byzantine Agreement with Fewer Words
Abstract
Byzantine Agreement (BA) is a key component in many distributed systems. While Dolev and Reischuk have proven a long time ago that quadratic communication complexity is necessary for worst-case runs, the question of what can be done in practically common runs with fewer failures remained open. In this paper we present the first Byzantine Broadcast algorithm with O(n(f+1)) communication complexity in a model with resilience of n = 2t+1, where 0 ≤ f ≤ t is the actual number of process failures in a run. And for BA with strong unanimity, we present the first optimal-resilience algorithm that has linear communication complexity in the failure-free case and a quadratic cost otherwise.
Cite as
Shir Cohen, Idit Keidar, and Alexander Spiegelman. Make Every Word Count: Adaptive Byzantine Agreement with Fewer Words. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 18:1-18:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{cohen_et_al:LIPIcs.OPODIS.2022.18,
author = {Cohen, Shir and Keidar, Idit and Spiegelman, Alexander},
title = {{Make Every Word Count: Adaptive Byzantine Agreement with Fewer Words}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {18:1--18:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.18},
URN = {urn:nbn:de:0030-drops-176385},
doi = {10.4230/LIPIcs.OPODIS.2022.18},
annote = {Keywords: Byzantine Agreement, Byzantine Broadcast, Adaptive communication}
}
Document
Modeling Resources in Permissionless Longest-Chain Total-Order Broadcast
Abstract
Blockchain protocols implement total-order broadcast in a permissionless setting, where processes can freely join and leave. In such a setting, to safeguard against Sybil attacks, correct processes rely on cryptographic proofs tied to a particular type of resource to make them eligible to order transactions. For example, in the case of Proof-of-Work (PoW), this resource is computation, and the proof is a solution to a computationally hard puzzle. Conversely, in Proof-of-Stake (PoS), the resource corresponds to the number of coins that every process in the system owns, and a secure lottery selects a process for participation proportionally to its coin holdings.
Although many resource-based blockchain protocols are formally proven secure in the literature, the existing security proofs fail to demonstrate why particular types of resources cause the blockchain protocols to be vulnerable to distinct classes of attacks. For instance, PoS systems are more vulnerable to long-range attacks, where an adversary corrupts past processes to re-write the history, than PoW and Proof-of-Storage systems. Proof-of-Storage-based and PoS-based protocols are both more susceptible to private double-spending attacks than PoW-based protocols; in this case, an adversary mines its chain in secret without sharing its blocks with the rest of the processes until the end of the attack.
In this paper, we formally characterize the properties of resources through an abstraction called resource allocator and give a framework for understanding longest-chain consensus protocols based on different underlying resources. In addition, we use this resource allocator to demonstrate security trade-offs between various resources focusing on well-known attacks (e.g., the long-range attack and nothing-at-stake attacks).
Cite as
Sarah Azouvi, Christian Cachin, Duc V. Le, Marko Vukolić, and Luca Zanolini. Modeling Resources in Permissionless Longest-Chain Total-Order Broadcast. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 19:1-19:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{azouvi_et_al:LIPIcs.OPODIS.2022.19,
author = {Azouvi, Sarah and Cachin, Christian and Le, Duc V. and Vukoli\'{c}, Marko and Zanolini, Luca},
title = {{Modeling Resources in Permissionless Longest-Chain Total-Order Broadcast}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {19:1--19:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.19},
URN = {urn:nbn:de:0030-drops-176398},
doi = {10.4230/LIPIcs.OPODIS.2022.19},
annote = {Keywords: blockchain, consensus, resource, broadcast}
}
Document
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. The separation results are obtained by approaching communication complexity through an original angle, which may be of an independent interest. The two players are not bounded to compute the value of a binary function, but the combined outputs of the two players are constrained by this value. In particular, we introduce the XOR-Index problem, in which Alice is given a binary vector x ∈ {0,1}ⁿ together with an index i ∈ [n], Bob is given a binary vector y ∈ {0,1}ⁿ together with an index j ∈ [n], and, after a single round of 2-way communication, Alice must output a boolean out_A, and Bob must output a boolean out_B, such that out_A ∧ out_B = x_j⊕ y_i. We show that the communication complexity of XOR-Index is Ω(n) bits.
Cite as
Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos-Wilson, and Ioan Todinca. Computing Power of Hybrid Models in Synchronous Networks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{fraigniaud_et_al:LIPIcs.OPODIS.2022.20,
author = {Fraigniaud, Pierre and Montealegre, Pedro and Paredes, Pablo and Rapaport, Ivan and R{\'\i}os-Wilson, Mart{\'\i}n and Todinca, Ioan},
title = {{Computing Power of Hybrid Models in Synchronous Networks}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {20:1--20:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.20},
URN = {urn:nbn:de:0030-drops-176401},
doi = {10.4230/LIPIcs.OPODIS.2022.20},
annote = {Keywords: hybrid model, synchronous networks, LOCAL, CONGEST, Broadcast Congested Clique}
}
Document
Mending Partial Solutions with Few Changes
Abstract
In this paper, we study the notion of mending: given a partial solution to a graph problem, how much effort is needed to take one step towards a proper solution? For example, if we have a partial coloring of a graph, how hard is it to properly color one more node?
In prior work (SIROCCO 2022), this question was formalized and studied from the perspective of mending radius: if there is a hole that we need to patch, how far do we need to modify the solution? In this work, we investigate a complementary notion of mending volume: how many nodes need to be modified to patch a hole?
We focus on the case of locally checkable labeling problems (LCLs) in trees, and show that already in this setting there are two infinite hierarchies of problems: for infinitely many values 0 < α ≤ 1, there is an LCL problem with mending volume Θ(n^α), and for infinitely many values k ≥ 1, there is an LCL problem with mending volume Θ(log^k n). Hence the mendability of LCL problems on trees is a much more fine-grained question than what one would expect based on the mending radius alone.
Cite as
Darya Melnyk, Jukka Suomela, and Neven Villani. Mending Partial Solutions with Few Changes. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{melnyk_et_al:LIPIcs.OPODIS.2022.21,
author = {Melnyk, Darya and Suomela, Jukka and Villani, Neven},
title = {{Mending Partial Solutions with Few Changes}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {21:1--21:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.21},
URN = {urn:nbn:de:0030-drops-176413},
doi = {10.4230/LIPIcs.OPODIS.2022.21},
annote = {Keywords: mending, LCL problems, volume model}
}
Document
The Impossibility of Approximate Agreement on a Larger Class of Graphs
Abstract
Approximate agreement is a variant of consensus in which processes receive input values from a domain and must output values in that domain that are sufficiently close to one another. We study the problem when the input domain is the vertex set of a connected graph. In asynchronous systems where processes communicate using shared registers, there are wait-free approximate agreement algorithms when the graph is a path or a tree, but not when the graph is a cycle of length at least 4. For many graphs, it is unknown whether a wait-free solution for approximate agreement exists.
We introduce a set of impossibility conditions and prove that approximate agreement on graphs satisfying these conditions cannot be solved in a wait-free manner. In particular, the graphs of all triangulated d-dimensional spheres that are not cliques, satisfy these conditions. The vertices and edges of an octahedron is an example of such a graph. We also present a family of reductions from approximate agreement on one graph to another graph. This allows us to extend known impossibility results to even more graphs.
Cite as
Shihao Liu. The Impossibility of Approximate Agreement on a Larger Class of Graphs. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{liu:LIPIcs.OPODIS.2022.22,
author = {Liu, Shihao},
title = {{The Impossibility of Approximate Agreement on a Larger Class of Graphs}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {22:1--22:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.22},
URN = {urn:nbn:de:0030-drops-176420},
doi = {10.4230/LIPIcs.OPODIS.2022.22},
annote = {Keywords: Approximate agreement on graph, wait-free solvability, triangulated sphere}
}
Document
On the Hierarchy of Distributed Majority Protocols
Abstract
We study the consensus problem among n agents, defined as follows. Initially, each agent holds one of two possible opinions. The goal is to reach a consensus configuration in which every agent shares the same opinion. To this end, agents randomly sample other agents and update their opinion according to a simple update function depending on the sampled opinions.
We consider two communication models: the gossip model and a variant of the population model. In the gossip model, agents are activated in parallel, synchronous rounds. In the population model, one agent is activated after the other in a sequence of discrete time steps. For both models we analyze the following natural family of majority processes called j-Majority: when activated, every agent samples j other agents uniformly at random (with replacement) and adopts the majority opinion among the sample (breaking ties uniformly at random). As our main result we show a hierarchy among majority protocols: (j+1)-Majority (for j > 1) converges stochastically faster than j-Majority for any initial opinion configuration. In our analysis we use Strassen’s Theorem to prove the existence of a coupling. This gives an affirmative answer for the case of two opinions to an open question asked by Berenbrink et al. [PODC 2017].
Cite as
Petra Berenbrink, Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser, and Malin Rau. On the Hierarchy of Distributed Majority Protocols. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{berenbrink_et_al:LIPIcs.OPODIS.2022.23,
author = {Berenbrink, Petra and Coja-Oghlan, Amin and Gebhard, Oliver and Hahn-Klimroth, Max and Kaaser, Dominik and Rau, Malin},
title = {{On the Hierarchy of Distributed Majority Protocols}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {23:1--23:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.23},
URN = {urn:nbn:de:0030-drops-176434},
doi = {10.4230/LIPIcs.OPODIS.2022.23},
annote = {Keywords: Consensus, Majority, Hierarchy, Stochastic Dominance, Population Protocols, Gossip Model, Strassen’s Theorem}
}
Document
Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption
Abstract
Agreement protocols for partially synchronous networks tolerate fewer than one-third Byzantine faults. If parties are equipped with trusted hardware that prevents equivocation, then fault tolerance can be improved to fewer than one-half Byzantine faults, but typically at the cost of increased communication complexity. In this work, we present results that use small trusted hardware without worsening communication complexity assuming the adversary controls a fraction of the network that is less than one-half. In particular, we show a version of HotStuff that retains linear communication complexity in each view, leveraging trusted hardware to tolerate a minority of corruptions. Our result uses expander graph techniques to achieve efficient communication in a manner that may be of independent interest.
Cite as
Sravya Yandamuri, Ittai Abraham, Kartik Nayak, and Michael K. Reiter. Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{yandamuri_et_al:LIPIcs.OPODIS.2022.24,
author = {Yandamuri, Sravya and Abraham, Ittai and Nayak, Kartik and Reiter, Michael K.},
title = {{Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {24:1--24:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.24},
URN = {urn:nbn:de:0030-drops-176448},
doi = {10.4230/LIPIcs.OPODIS.2022.24},
annote = {Keywords: communication complexity, consensus, trusted hardware}
}
Document
Chopin: Combining Distributed and Centralized Schedulers for Self-Adjusting Datacenter Networks
Abstract
The performance of distributed and data-centric applications often critically depends on the interconnecting network. Emerging reconfigurable datacenter networks (RDCNs) are a particularly innovative approach to improve datacenter throughput. Relying on a dynamic optical topology which can be adjusted towards the workload in a demand-aware manner, RDCNs allow to exploit temporal and spatial locality in the communication pattern, and to provide topological shortcuts for frequently communicating racks. The key challenge, however, concerns how to realize demand-awareness in RDCNs in a scalable fashion.
This paper presents and evaluates Chopin, a hybrid scheduler for self-adjusting networks that provides demand-awareness at low overhead, by combining centralized and distributed approaches. Chopin allocates optical circuits to elephant flows, through its slower centralized scheduler, utilizing global information. Chopin’s distributed scheduler is orders of magnitude faster and can swiftly react to changes in the traffic and adjust the optical circuits accordingly, by using only local information and running at each rack separately.
Cite as
Neta Rozen-Schiff, Klaus-Tycho Foerster, Stefan Schmid, and David Hay. Chopin: Combining Distributed and Centralized Schedulers for Self-Adjusting Datacenter Networks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 25:1-25:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{rozenschiff_et_al:LIPIcs.OPODIS.2022.25,
author = {Rozen-Schiff, Neta and Foerster, Klaus-Tycho and Schmid, Stefan and Hay, David},
title = {{Chopin: Combining Distributed and Centralized Schedulers for Self-Adjusting Datacenter Networks}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {25:1--25:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.25},
URN = {urn:nbn:de:0030-drops-176457},
doi = {10.4230/LIPIcs.OPODIS.2022.25},
annote = {Keywords: reconfigurable optical networks, centralized scheduler, distributed scheduler}
}
Document
A Modular Approach to Construct Signature-Free BRB Algorithms Under a Message Adversary
Abstract
This paper explores how reliable broadcast can be implemented without signatures when facing a dual adversary that can both corrupt processes and remove messages. More precisely, we consider an asynchronous n-process message-passing system in which up to t processes are Byzantine and where, at the network level, for each message broadcast by a correct process, an adversary can prevent up to d processes from receiving it (the integer d defines the power of the message adversary). So, unlike previous works, this work considers that not only can computing entities be faulty (Byzantine processes), but, in addition, that the network can also lose messages. To this end, the paper adopts a modular strategy and first introduces a new basic communication abstraction denoted k2𝓁-cast, which simplifies quorum engineering, and studies its properties in this new adversarial context. Then, the paper deconstructs existing signature-free Byzantine-tolerant asynchronous broadcast algorithms and, with the help of the k2𝓁-cast communication abstraction, reconstructs versions of them that tolerate both Byzantine processes and message adversaries. Interestingly, these reconstructed algorithms are also more efficient than the Byzantine-tolerant-only algorithms from which they originate.
Cite as
Timothé Albouy, Davide Frey, Michel Raynal, and François Taïani. A Modular Approach to Construct Signature-Free BRB Algorithms Under a Message Adversary. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 26:1-26:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{albouy_et_al:LIPIcs.OPODIS.2022.26,
author = {Albouy, Timoth\'{e} and Frey, Davide and Raynal, Michel and Ta\"{i}ani, Fran\c{c}ois},
title = {{A Modular Approach to Construct Signature-Free BRB Algorithms Under a Message Adversary}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {26:1--26:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.26},
URN = {urn:nbn:de:0030-drops-176464},
doi = {10.4230/LIPIcs.OPODIS.2022.26},
annote = {Keywords: Asynchronous system, Byzantine processes, Communication abstraction, Delivery predicate, Fault-Tolerance, Forwarding predicate, Message adversary, Message loss, Modularity, Quorum, Reliable broadcast, Signature-free algorithm, Two-phase commit}
}
Document
Design of Self-Stabilizing Approximation Algorithms via a Primal-Dual Approach
Abstract
Self-stabilization is an important concept in the realm of fault-tolerant distributed computing. In this paper, we propose a new approach that relies on the properties of linear programming duality to obtain self-stabilizing approximation algorithms for distributed graph optimization problems. The power of this new approach is demonstrated by the following results:
- A self-stabilizing 2(1+ε)-approximation algorithm for minimum weight vertex cover that converges in O(logΔ /(εlog log Δ)) synchronous rounds.
- A self-stabilizing Δ-approximation algorithm for maximum weight independent set that converges in O(Δ+log^* n) synchronous rounds.
- A self-stabilizing ((2ρ+1)(1+ε))-approximation algorithm for minimum weight dominating set in ρ-arboricity graphs that converges in O((logΔ)/ε) synchronous rounds. In all of the above, Δ denotes the maximum degree. Our technique improves upon previous results in terms of time complexity while incurring only an additive O(log n) overhead to the message size. In addition, to the best of our knowledge, we provide the first self-stabilizing algorithms for the weighted versions of minimum vertex cover and maximum independent set.
Cite as
Yuval Emek, Yuval Gil, and Noga Harlev. Design of Self-Stabilizing Approximation Algorithms via a Primal-Dual Approach. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{emek_et_al:LIPIcs.OPODIS.2022.27,
author = {Emek, Yuval and Gil, Yuval and Harlev, Noga},
title = {{Design of Self-Stabilizing Approximation Algorithms via a Primal-Dual Approach}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {27:1--27:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.27},
URN = {urn:nbn:de:0030-drops-176474},
doi = {10.4230/LIPIcs.OPODIS.2022.27},
annote = {Keywords: self-stabilization, approximation algorithms, primal-dual}
}
Document
Self-Stabilizing Clock Synchronization in Dynamic Networks
Abstract
We consider the fundamental problem of periodic clock synchronization in a synchronous multi-agent system. Each agent holds a clock with an arbitrary initial value, and clocks must eventually be congruent, modulo some positive integer P. Previous algorithms worked in static networks with drastic connectivity properties and assumed that global informations are available at each node. In this paper, we propose a finite-state algorithm for time-varying topologies that does not require any global knowledge on the network. The only assumption is the existence of some integer D such that any two nodes can communicate in each sequence of D consecutive rounds, which extends the notion of strong connectivity in static network to dynamic communication patterns. The smallest such D is called the dynamic diameter of the network. If an upper bound on the diameter is provided, then our algorithm achieves synchronization within 3D rounds, whatever the value of the upper bound. Otherwise, using an adaptive mechanism, synchronization is achieved with little performance overhead. Our algorithm is parameterized by a function g, which can be tuned to favor either time or space complexity. Then, we explore a further relaxation of the connectivity requirement: our algorithm still works if there exists a positive integer R such that the network is rooted over each sequence of R consecutive rounds, and if eventually the set of roots is stable. In particular, it works in any rooted static network.
Cite as
Bernadette Charron-Bost and Louis Penet de Monterno. Self-Stabilizing Clock Synchronization in Dynamic Networks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{charronbost_et_al:LIPIcs.OPODIS.2022.28,
author = {Charron-Bost, Bernadette and Penet de Monterno, Louis},
title = {{Self-Stabilizing Clock Synchronization in Dynamic Networks}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {28:1--28:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.28},
URN = {urn:nbn:de:0030-drops-176480},
doi = {10.4230/LIPIcs.OPODIS.2022.28},
annote = {Keywords: Self-stabilization, Clock synchronization, Dynamic networks}
}