Volume
LIPIcs, Volume 286
27th International Conference on Principles of Distributed Systems (OPODIS 2023)
Event
OPODIS 2023, December 6-8, 2023, Tokyo, JapanEditors
Publication Details
- published at: 2024-01-18
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-308-9
- DBLP: db/conf/opodis/opodis2023
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 286, OPODIS 2023, Complete Volume
Abstract
LIPIcs, Volume 286, OPODIS 2023, Complete Volume
Cite as
27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 1-702, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@Proceedings{bessani_et_al:LIPIcs.OPODIS.2023,
title = {{LIPIcs, Volume 286, OPODIS 2023, Complete Volume}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {1--702},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023},
URN = {urn:nbn:de:0030-drops-194896},
doi = {10.4230/LIPIcs.OPODIS.2023},
annote = {Keywords: LIPIcs, Volume 286, OPODIS 2023, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{bessani_et_al:LIPIcs.OPODIS.2023.0,
author = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {0:i--0:xvi},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.0},
URN = {urn:nbn:de:0030-drops-194903},
doi = {10.4230/LIPIcs.OPODIS.2023.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
From Consensus Research to Redbelly Network Pty Ltd (Invited Talk)
Abstract
Designing and implementing correctly a blockchain system requires collaborations across places and research fields. Redbelly, a company across Australia, India and USA, illustrates well this idea.
It started in 2005 at OPODIS, where we published the Reconfigurable Distributed Storage to replace distributed participants offering a service without disrupting its availability. This line of work [V. Gramoli et al., 2021] was instrumental to reconfigure blockchains without introducing hard forks. The research on the consensus problem we initiated at IRISA [V. Gramoli, 2022] led to rethinking PBFT-like algorithms for the context of blockchain by getting rid of the leader that can act as the bottleneck of large networks [V. Gramoli and Q. Tang, 2023]. Our work on security led to disclosing vulnerabilities in Ethereum [Parinya Ekparinya et al., 2020] and then motivated us to formally verify blockchain consensus [Nathalie Bertrand et al., 2022]. Our work at the frontier of economics [Michael Spain et al., 2019] led us to prevent front-running attacks [Pouriya Zarbafian and Vincent Gramoli, 2023] and to incentivize rational players to behave [Alejandro Ranchal-Pedrosa and Vincent Gramoli, 2022]. Our system work at Cornell and then at EPFL was foundational in experimenting blockchains across the globe [Vincent Gramoli et al., 2023].
Although not anticipated at the time, this series of work progressively led the University of Sydney and CSIRO, and later Redbelly Network Pty Ltd, to design the Redbelly Blockchain [Tyler Crain et al., 2021; Deepal Tennakoon et al., 2023], the platform of choice for compliant asset tokenisation.
Cite as
Vincent Gramoli. From Consensus Research to Redbelly Network Pty Ltd (Invited Talk). In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 1:1-1:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{gramoli:LIPIcs.OPODIS.2023.1,
author = {Gramoli, Vincent},
title = {{From Consensus Research to Redbelly Network Pty Ltd}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {1:1--1:2},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.1},
URN = {urn:nbn:de:0030-drops-194915},
doi = {10.4230/LIPIcs.OPODIS.2023.1},
annote = {Keywords: Innovations, Commercialisation}
}
Document
Invited Talk
Quantum Distributed Computing: Potential and Limitations (Invited Talk)
Abstract
The subject of this talk is quantum distributed computing, i.e., distributed computing where the processors of the network can exchange quantum messages. In the first part of the talk I survey recent results [Taisuke Izumi and François Le Gall, 2019; Taisuke Izumi et al., 2020; François Le Gall and Frédéric Magniez, 2018; François Le Gall et al., 2019; Xudong Wu and Penghui Yao, 2022] and some older results [Michael Ben-Or and Avinatan Hassidim, 2005; Seiichiro Tani et al., 2012] that show the potential of quantum distributed algorithms. In the second part I present our recent work [Xavier Coiteux-Roy et al., 2023] showing the limitations of quantum distributed algorithms for approximate graph coloring. Finally, I mention interesting and important open questions in quantum distributed computing.
Cite as
François Le Gall. Quantum Distributed Computing: Potential and Limitations (Invited Talk). In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{legall:LIPIcs.OPODIS.2023.2,
author = {Le Gall, Fran\c{c}ois},
title = {{Quantum Distributed Computing: Potential and Limitations}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {2:1--2:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.2},
URN = {urn:nbn:de:0030-drops-194925},
doi = {10.4230/LIPIcs.OPODIS.2023.2},
annote = {Keywords: Quantum computing, distributed algorithms, CONGEST model, LOCAL model}
}
Document
Invited Talk
Distributed Algorithms as a Gateway To Deductive Learning (Invited Talk)
Abstract
With the book Thinking Fast and Slow, Daniel Kahneman popularized the idea that the human brain can think in two different modes. The fast mode is instinctive and automatic, while the slow mode is deliberative and logical. As of 2023, one can argue that machine learning understands how to think fast. Deep neural networks are remarkably successful in rapidly classifying and regressing data. Thinking slow on the other hand is still a mystery. Large language models may provide an illusion of being able to think slow. However, prompts that need multiple deductive steps are generally beyond the capabilities of large language models. Distributed algorithms have the potential to help understanding deductive reasoning. Distributed algorithms usually consist of several little steps, iteratively applied, each step being easily learnable. As such distributed computing may provide an interesting bridge towards understanding deduction, extrapolation, reasoning, and everything else needed to think slow. In the talk, we will discuss some exciting case studies from graph generation to origami folding.
Cite as
Roger Wattenhofer. Distributed Algorithms as a Gateway To Deductive Learning (Invited Talk). In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{wattenhofer:LIPIcs.OPODIS.2023.3,
author = {Wattenhofer, Roger},
title = {{Distributed Algorithms as a Gateway To Deductive Learning}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {3:1--3:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.3},
URN = {urn:nbn:de:0030-drops-194936},
doi = {10.4230/LIPIcs.OPODIS.2023.3},
annote = {Keywords: abstract visual reasoning, agent-based reasoning, classic algorithm benchmarks, differentiable status registers, explainable graphs, graph generation algorithms, integer sequences, neural combinatorial circuits, recurrent network algorithms, origami folding, Tatham’s puzzles}
}
Document
The Synchronization Power of Auditable Registers
Abstract
Auditability allows to track all the read operations performed on a register. It abstracts the need of data owners to control access to their data, tracking who read which information. This work considers possible formalizations of auditing and their ramification for the possibility of providing it.
The natural definition is to require a linearization of all write, read and audit operations together (atomic auditing). The paper shows that atomic auditing is a powerful tool, as it can be used to solve consensus. The number of processes that can solve consensus using atomic audit depends on the number of processes that can read or audit the register. If there is a single reader or a single auditor (the writer), then consensus can be solved among two processes. If multiple readers and auditors are possible, then consensus can be solved among the same number of processes. This means that strong synchronization primitives are needed to support atomic auditing.
We give implementations of atomic audit when there are either multiple readers or multiple auditors (but not both) using primitives with consensus number 2 (swap and fetch&add). When there are multiple readers and multiple auditors, the implementation uses compare&swap.
These findings motivate a weaker definition, in which audit operations are not linearized together with read and write operations (regular auditing). We prove that regular auditing can be implemented from ordinary reads and writes on atomic registers.
Cite as
Hagit Attiya, Antonella Del Pozzo, Alessia Milani, Ulysse Pavloff, and Alexandre Rapetti. The Synchronization Power of Auditable Registers. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{attiya_et_al:LIPIcs.OPODIS.2023.4,
author = {Attiya, Hagit and Del Pozzo, Antonella and Milani, Alessia and Pavloff, Ulysse and Rapetti, Alexandre},
title = {{The Synchronization Power of Auditable Registers}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {4:1--4:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.4},
URN = {urn:nbn:de:0030-drops-194940},
doi = {10.4230/LIPIcs.OPODIS.2023.4},
annote = {Keywords: Auditability, atomic register, fault tolerance, consensus number}
}
Document
𝒪(log{n})-Time Uniform Circle Formation for Asynchronous Opaque Luminous Robots
Abstract
We study the Uniform Circle Formation (UCF) problem for a distributed system of n robots which are required to displace on the vertices of a regular n-gon. We consider a well-studied model of autonomous, anonymous, mobile robots that act on the plane through Look-Compute-Move cycles. Moreover, robots are unaware of the cardinality of the system, they are punctiform, completely disoriented, opaque, and luminous. Collisions among robots are not tolerated.
In the literature, the UCF problem has been solved for such a model by a deterministic algorithm in the asynchronous mode, using a constant amount of light colors and 𝒪(n) epochs in the worst case. In this paper, we provide an improved algorithm for solving the UCF problem for asynchronous robots, which uses 𝒪(log n) epochs still maintaining a constant amount of colors.
Cite as
Caterina Feletti, Carlo Mereghetti, and Beatrice Palano. 𝒪(log{n})-Time Uniform Circle Formation for Asynchronous Opaque Luminous Robots. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{feletti_et_al:LIPIcs.OPODIS.2023.5,
author = {Feletti, Caterina and Mereghetti, Carlo and Palano, Beatrice},
title = {{𝒪(log\{n\})-Time Uniform Circle Formation for Asynchronous Opaque Luminous Robots}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {5:1--5:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.5},
URN = {urn:nbn:de:0030-drops-194956},
doi = {10.4230/LIPIcs.OPODIS.2023.5},
annote = {Keywords: Autonomous mobile robots, Opaque robots, Luminous robots, Pattern formation}
}
Document
Multi-Valued Connected Consensus: A New Perspective on Crusader Agreement and Adopt-Commit
Abstract
Algorithms to solve fault-tolerant consensus in asynchronous systems often rely on primitives such as crusader agreement, adopt-commit, and graded broadcast, which provide weaker agreement properties than consensus. Although these primitives have a similar flavor, they have been defined and implemented separately in ad hoc ways. We propose a new problem called connected consensus that has as special cases crusader agreement, adopt-commit, and graded broadcast, and generalizes them to handle multi-valued inputs. The generalization is accomplished by relating the problem to approximate agreement on graphs.
We present three algorithms for multi-valued connected consensus in asynchronous message-passing systems, one tolerating crash failures and two tolerating malicious (unauthenticated Byzantine) failures. We extend the definition of binding, a desirable property recently identified as supporting binary consensus algorithms that are correct against adaptive adversaries, to the multi-valued input case and show that all our algorithms satisfy the property. Our crash-resilient algorithm has failure-resilience and time complexity that we show are optimal. When restricted to the case of binary inputs, the algorithm has improved time complexity over prior algorithms. Our two algorithms for malicious failures trade off failure resilience and time complexity. The first algorithm has time complexity that we prove is optimal but worse failure-resilience, while the second has failure-resilience that we prove is optimal but worse time complexity. When restricted to the case of binary inputs, the time complexity (as well as resilience) of the second algorithm matches that of prior algorithms.
The contributions of the paper are first, a deeper insight into the connections between primitives commonly used to solve the fundamental problem of fault-tolerant consensus, and second, implementations of these primitives that can contribute to improved consensus algorithms.
Cite as
Hagit Attiya and Jennifer L. Welch. Multi-Valued Connected Consensus: A New Perspective on Crusader Agreement and Adopt-Commit. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{attiya_et_al:LIPIcs.OPODIS.2023.6,
author = {Attiya, Hagit and Welch, Jennifer L.},
title = {{Multi-Valued Connected Consensus: A New Perspective on Crusader Agreement and Adopt-Commit}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {6:1--6:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.6},
URN = {urn:nbn:de:0030-drops-194967},
doi = {10.4230/LIPIcs.OPODIS.2023.6},
annote = {Keywords: graded broadcast, gradecast, binding, approximate agreement}
}
Document
Energy-Constrained Programmable Matter Under Unfair Adversaries
Abstract
Individual modules of programmable matter participate in their system’s collective behavior by expending energy to perform actions. However, not all modules may have access to the external energy source powering the system, necessitating a local and distributed strategy for supplying energy to modules. In this work, we present a general energy distribution framework for the canonical amoebot model of programmable matter that transforms energy-agnostic algorithms into energy-constrained ones with equivalent behavior and an 𝒪(n²)-round runtime overhead - even under an unfair adversary - provided the original algorithms satisfy certain conventions. We then prove that existing amoebot algorithms for leader election (ICDCN 2023) and shape formation (Distributed Computing, 2023) are compatible with this framework and show simulations of their energy-constrained counterparts, demonstrating how other unfair algorithms can be generalized to the energy-constrained setting with relatively little effort. Finally, we show that our energy distribution framework can be composed with the concurrency control framework for amoebot algorithms (Distributed Computing, 2023), allowing algorithm designers to focus on the simpler energy-agnostic, sequential setting but gain the general applicability of energy-constrained, asynchronous correctness.
Cite as
Jamison W. Weber, Tishya Chhabra, Andréa W. Richa, and Joshua J. Daymude. Energy-Constrained Programmable Matter Under Unfair Adversaries. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{weber_et_al:LIPIcs.OPODIS.2023.7,
author = {Weber, Jamison W. and Chhabra, Tishya and Richa, Andr\'{e}a W. and Daymude, Joshua J.},
title = {{Energy-Constrained Programmable Matter Under Unfair Adversaries}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {7:1--7:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.7},
URN = {urn:nbn:de:0030-drops-194971},
doi = {10.4230/LIPIcs.OPODIS.2023.7},
annote = {Keywords: Programmable matter, amoebot model, energy distribution, concurrency}
}
Document
A Fair and Resilient Decentralized Clock Network for Transaction Ordering
Abstract
Traditional blockchain design gives miners or validators full control over transaction ordering, i.e., they can freely choose which transactions to include or exclude, as well as in which order. While not an issue initially, the emergence of decentralized finance has introduced new transaction order dependencies allowing parties in control of the ordering to make a profit by front-running others' transactions. In this work, we present the Decentralized Clock Network, a new approach for achieving fair transaction ordering. Users submit their transactions to the network’s clocks, which run an agreement protocol that provides each transaction with a timestamp of receipt which is then used to define the transactions' order. By separating agreement from ordering, our protocol is efficient and has a simpler design compared to other available solutions. Moreover, our protocol brings to the blockchain world the paradigm of asynchronous fallback, where the algorithm operates with stronger fairness guarantees during periods of synchronous use, switching to an asynchronous mode only during times of increased network delay.
Cite as
Andrei Constantinescu, Diana Ghinea, Lioba Heimbach, Zilin Wang, and Roger Wattenhofer. A Fair and Resilient Decentralized Clock Network for Transaction Ordering. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{constantinescu_et_al:LIPIcs.OPODIS.2023.8,
author = {Constantinescu, Andrei and Ghinea, Diana and Heimbach, Lioba and Wang, Zilin and Wattenhofer, Roger},
title = {{A Fair and Resilient Decentralized Clock Network for Transaction Ordering}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {8:1--8:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.8},
URN = {urn:nbn:de:0030-drops-194989},
doi = {10.4230/LIPIcs.OPODIS.2023.8},
annote = {Keywords: Median Validity, Blockchain, Fair Ordering, Front-running Prevention, Miner Extractable Value}
}
Document
Byzantine Consensus in Abstract MAC Layer
Abstract
This paper studies the design of Byzantine consensus algorithms in an asynchronous single-hop network equipped with the "abstract MAC layer" [DISC09], which captures core properties of modern wireless MAC protocols. Newport [PODC14], Newport and Robinson [DISC18], and Tseng and Zhang [PODC22] study crash-tolerant consensus in the model. In our setting, a Byzantine faulty node may behave arbitrarily, but it cannot break the guarantees provided by the underlying abstract MAC layer. To our knowledge, we are the first to study Byzantine faults in this model.
We harness the power of the abstract MAC layer to develop a Byzantine approximate consensus algorithm and a Byzantine randomized binary consensus algorithm. Both of our algorithms require only the knowledge of the upper bound on the number of faulty nodes f, and do not require the knowledge of the number of nodes n. This demonstrates the "power" of the abstract MAC layer, as consensus algorithms in traditional message-passing models require the knowledge of both n and f. Additionally, we show that it is necessary to know f in order to reach consensus. Hence, from this perspective, our algorithms require the minimal knowledge.
The lack of knowledge of n brings the challenge of identifying a quorum explicitly, which is a common technique in traditional message-passing algorithms. A key technical novelty of our algorithms is to identify "implicit quorums" which have the necessary information for reaching consensus. The quorums are implicit because nodes do not know the identity of the quorums - such notion is only used in the analysis.
Cite as
Lewis Tseng and Callie Sardina. Byzantine Consensus in Abstract MAC Layer. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{tseng_et_al:LIPIcs.OPODIS.2023.9,
author = {Tseng, Lewis and Sardina, Callie},
title = {{Byzantine Consensus in Abstract MAC Layer}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {9:1--9:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.9},
URN = {urn:nbn:de:0030-drops-194992},
doi = {10.4230/LIPIcs.OPODIS.2023.9},
annote = {Keywords: Byzantine, Randomized Consensus, Approximate Consensus, Abstract MAC}
}
Document
Discrete Incremental Voting
Abstract
We consider a type of pull voting suitable for discrete numeric opinions which can be compared on a linear scale, for example, 1 ("disagree strongly"), 2 ("disagree"), …, 5 ("agree strongly"). On observing the opinion of a random neighbour, a vertex changes its opinion incrementally towards the value of the neighbour’s opinion, if different. For opinions drawn from a set {1,2,…,k}, the opinion of the vertex would change by +1 if the opinion of the neighbour is larger, or by -1, if it is smaller.
It is not clear how to predict the outcome of this process, but we observe that the total weight of the system, that is, the sum of the individual opinions of all vertices, is a martingale. This allows us analyse the outcome of the process on some classes of dense expanders such as complete graphs K_n and random graphs G_{n,p} for suitably large p. If the average of the original opinions satisfies i ≤ c ≤ i+1 for some integer i, then the asymptotic probability that opinion i wins is i+1-c, and the probability that opinion i+1 wins is c-i. With high probability, the winning opinion cannot be other than i or i+1.
To contrast this, we show that for a path and opinions 0,1,2 arranged initially in non-decreasing order along the path, the outcome is very different. Any of the opinions can win with constant probability, provided that each of the two extreme opinions 0 and 2 is initially supported by a constant fraction of vertices.
Cite as
Colin Cooper, Tomasz Radzik, and Takeharu Shiraga. Discrete Incremental Voting. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{cooper_et_al:LIPIcs.OPODIS.2023.10,
author = {Cooper, Colin and Radzik, Tomasz and Shiraga, Takeharu},
title = {{Discrete Incremental Voting}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {10:1--10:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.10},
URN = {urn:nbn:de:0030-drops-195005},
doi = {10.4230/LIPIcs.OPODIS.2023.10},
annote = {Keywords: Random distributed processes, Pull voting}
}
Document
On the Convergence Time in Graphical Games: A Locality-Sensitive Approach
Abstract
Graphical games are a useful framework for modeling the interactions of (selfish) agents who are connected via an underlying topology and whose behaviors influence each other. They have wide applications ranging from computer science to economics and biology. Yet, even though an agent’s payoff only depends on the actions of their direct neighbors in graphical games, computing the Nash equilibria and making statements about the convergence time of "natural" local dynamics in particular can be highly challenging. In this work, we present a novel approach for classifying complexity of Nash equilibria in graphical games by establishing a connection to local graph algorithms, a subfield of distributed computing. In particular, we make the observation that the equilibria of graphical games are equivalent to locally verifiable labelings (LVL) in graphs; vertex labelings which are verifiable with constant-round local algorithms. This connection allows us to derive novel lower bounds on the convergence time to equilibrium of best-response dynamics in graphical games. Since we establish that distributed convergence can sometimes be provably slow, we also introduce and give bounds on an intuitive notion of "time-constrained" inefficiency of best responses. We exemplify how our results can be used in the implementation of mechanisms that ensure convergence of best responses to a Nash equilibrium. Our results thus also give insight into the convergence of strategy-proof algorithms for graphical games, which is still not well understood.
Cite as
Juho Hirvonen, Laura Schmid, Krishnendu Chatterjee, and Stefan Schmid. On the Convergence Time in Graphical Games: A Locality-Sensitive Approach. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 11:1-11:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{hirvonen_et_al:LIPIcs.OPODIS.2023.11,
author = {Hirvonen, Juho and Schmid, Laura and Chatterjee, Krishnendu and Schmid, Stefan},
title = {{On the Convergence Time in Graphical Games: A Locality-Sensitive Approach}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {11:1--11:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.11},
URN = {urn:nbn:de:0030-drops-195015},
doi = {10.4230/LIPIcs.OPODIS.2023.11},
annote = {Keywords: distributed computing, Nash equilibria, mechanism design, best-response dynamics}
}
Document
Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks
Abstract
Traditional blockchains grant the miner of a block full control not only over which transactions but also their order. This constitutes a major flaw discovered with the introduction of decentralized finance and allows miners to perform MEV attacks. In this paper, we address the issue of sandwich attacks by providing a construction that takes as input a blockchain protocol and outputs a new blockchain protocol with the same security but in which sandwich attacks are not profitable. Furthermore, our protocol is fully decentralized with no trusted third parties or heavy cryptography primitives and carries a linear increase in latency and minimum computation overhead.
Cite as
Orestis Alpos, Ignacio Amores-Sesar, Christian Cachin, and Michelle Yeo. Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{alpos_et_al:LIPIcs.OPODIS.2023.12,
author = {Alpos, Orestis and Amores-Sesar, Ignacio and Cachin, Christian and Yeo, Michelle},
title = {{Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {12:1--12:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.12},
URN = {urn:nbn:de:0030-drops-195029},
doi = {10.4230/LIPIcs.OPODIS.2023.12},
annote = {Keywords: Consensus, MEV, Byzantine behavior, Rational behavior}
}
Document
Improved Distributed Algorithms for Random Colorings
Abstract
Markov Chain Monte Carlo (MCMC) algorithms are a widely-used algorithmic tool for sampling from high-dimensional distributions, a notable example is the equilibirum distribution of graphical models. The Glauber dynamics, also known as the Gibbs sampler, is the simplest example of an MCMC algorithm; the transitions of the chain update the configuration at a randomly chosen coordinate at each step. Several works have studied distributed versions of the Glauber dynamics and we extend these efforts to a more general family of Markov chains. An important combinatorial problem in the study of MCMC algorithms is random colorings. Given a graph G of maximum degree Δ and an integer k ≥ Δ+1, the goal is to generate a random proper vertex k-coloring of G.
Jerrum (1995) proved that the Glauber dynamics has O(nlog{n}) mixing time when k > 2Δ. Fischer and Ghaffari (2018), and independently Feng, Hayes, and Yin (2018), presented a parallel and distributed version of the Glauber dynamics which converges in O(log{n}) rounds for k > (2+ε)Δ for any ε > 0. We improve this result to k > (11/6-δ)Δ for a fixed δ > 0. This matches the state of the art for randomly sampling colorings of general graphs in the sequential setting. Whereas previous works focused on distributed variants of the Glauber dynamics, our work presents a parallel and distributed version of the more general flip dynamics presented by Vigoda (2000) (and refined by Chen, Delcourt, Moitra, Perarnau, and Postle (2019)), which recolors local maximal two-colored components in each step.
Cite as
Charlie Carlson, Daniel Frishberg, and Eric Vigoda. Improved Distributed Algorithms for Random Colorings. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{carlson_et_al:LIPIcs.OPODIS.2023.13,
author = {Carlson, Charlie and Frishberg, Daniel and Vigoda, Eric},
title = {{Improved Distributed Algorithms for Random Colorings}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {13:1--13:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.13},
URN = {urn:nbn:de:0030-drops-195030},
doi = {10.4230/LIPIcs.OPODIS.2023.13},
annote = {Keywords: Distributed Graph Algorithms, Local Algorithms, Coloring, Glauber Dynamics, Sampling, Markov Chains}
}
Document
Fever: Optimal Responsive View Synchronisation
Abstract
View synchronisation is an important component of many modern Byzantine Fault Tolerant State Machine Replication (SMR) systems in the partial synchrony model. Roughly, the efficiency of view synchronisation is measured as the word complexity and latency required for moving from being synchronised in a view of one correct leader to being synchronised in the view of the next correct leader. The efficiency of view synchronisation has emerged as a major bottleneck in the efficiency of SMR systems as a whole. A key question remained open: Do there exist view synchronisation protocols with asymptotically optimal quadratic worst-case word complexity that also obtain linear complexity and responsiveness when moving between consecutive correct leaders?
We answer this question affirmatively with a new view synchronisation protocol for partial synchrony assuming partial initial clock synchronisation, called Fever. If n is the number of processors and t is the largest integer < n/3, then Fever has resilience t, and in all executions with at most 0 ≤ f ≤ t Byzantine parties and network delays of at most δ ≤ Δ after GST (where f and δ are unknown), Fever has worst-case word complexity O(fn+n) and worst-case latency O(Δ f + δ).
Cite as
Andrew Lewis-Pye and Ittai Abraham. Fever: Optimal Responsive View Synchronisation. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{lewispye_et_al:LIPIcs.OPODIS.2023.14,
author = {Lewis-Pye, Andrew and Abraham, Ittai},
title = {{Fever: Optimal Responsive View Synchronisation}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {14:1--14:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.14},
URN = {urn:nbn:de:0030-drops-195041},
doi = {10.4230/LIPIcs.OPODIS.2023.14},
annote = {Keywords: Distributed Systems, State Machine Replication}
}
Document
Nova: Safe Off-Heap Memory Allocation and Reclamation
Abstract
In recent years, we begin to see Java-based systems embrace off-heap allocation for their big data demands. As of today, these system rely on simple ad-hoc garbage-collection solutions, which restrict the usage of off-heap data. This paper introduces the abstraction of safe off-heap memory allocation and reclamation (SOMAR), a thread-safe memory allocation and reclamation scheme for off-heap data in otherwise managed environments. SOMAR allows multi-threaded Java programs to use off-heap memory seamlessly. To realize this abstraction, we present Nova, Novel Off-heap Versioned Allocator, a lock-free SOMAR implementation. Our experiments show that Nova can be used to store off-heap data in Java data structures with better performance than ones managed by Java’s automatic GC. We further integrate Nova into the open-source Oak concurrent map library, which allows Oak to reclaim keys while the data structure is being accessed.
Cite as
Ramy Fakhoury, Anastasia Braginsky, Idit Keidar, and Yoav Zuriel. Nova: Safe Off-Heap Memory Allocation and Reclamation. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{fakhoury_et_al:LIPIcs.OPODIS.2023.15,
author = {Fakhoury, Ramy and Braginsky, Anastasia and Keidar, Idit and Zuriel, Yoav},
title = {{Nova: Safe Off-Heap Memory Allocation and Reclamation}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {15:1--15:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.15},
URN = {urn:nbn:de:0030-drops-195052},
doi = {10.4230/LIPIcs.OPODIS.2023.15},
annote = {Keywords: memory reclamation, concurrency, performance, off-heap allocation}
}
Document
Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs
Abstract
We design new deterministic CONGEST approximation algorithms for maximum weight independent set (MWIS) in sparse graphs. As our main results, we obtain new Δ(1+ε)-approximation algorithms as well as algorithms whose approximation ratio depend strictly on α, in graphs with maximum degree Δ and arboricity α. For (deterministic) Δ(1+ε)-approximation, the current state-of-the-art is due to a recent breakthrough by Faour et al. [SODA 2023] that showed an O(log² (Δ W)⋅ log (1/ε)+log ^{*}n)-round algorithm, where W is the largest node-weight (this bound translates to O(log² n⋅log (1/ε)) under the common assumption that W = poly(n)). As for α-dependent approximations, a deterministic CONGEST (8(1+ε)⋅α)-approximation algorithm with runtime O(log³ n⋅log (1/ε)) can be derived by combining the aforementioned algorithm of Faour et al. with a method presented by Kawarabayashi et al. [DISC 2020]. As our main results, we show the following.
- A deterministic CONGEST algorithm that computes an α^{1+τ}-approximation for MWIS in O(log nlog α) rounds for any constant τ > 0. To the best of our knowledge, this is the fastest runtime of any deterministic non-trivial approximation algorithm for MWIS to date. Furthermore, for the large class of graphs where α = Δ^{1-Θ(1)}, it implies a deterministic Δ^{1-Θ(1)}-approximation algorithm with a runtime of O(log nlog α) which improves upon the result of Faour et al. in both approximation ratio (by a Δ^{Θ(1)} factor) and runtime (by an O(log n/log α) factor).
- A deterministic CONGEST algorithm that computes an O(α)-approximation for MWIS in O(α^{τ}log n) rounds for any (desirably small) constant τ > 0. This improves the runtime of the best known deterministic O(α)-approximation algorithm in the case that α = O(polylog n). This also leads to a deterministic Δ(1+ε)-approximation algorithm with a runtime of O(α^{τ}log nlog (1/ε)) which improves upon the runtime of Faour et al. in the case that α = O(polylog n).
- A deterministic CONGEST algorithm that computes a (⌊(2+ε)α⌋)-approximation for MWIS in O(αlog n) rounds. This improves upon the best known α-dependent approximation ratio by a constant factor.
- A deterministic CONGEST algorithm that computes a 2d²-approximation for MWIS in time O(d²+log ^{*}n) in a directed graph with out-degree at most d. The dependency on n is (asymptotically) optimal due to a lower bound by Czygrinow et al. [DISC 2008] and Lenzen and Wattenhofer [DISC 2008]. We note that a key ingredient to all of our algorithms is a novel deterministic method that computes a high-weight subset of nodes whose induced subgraph is sparse.
Cite as
Yuval Gil. Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{gil:LIPIcs.OPODIS.2023.16,
author = {Gil, Yuval},
title = {{Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {16:1--16:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.16},
URN = {urn:nbn:de:0030-drops-195067},
doi = {10.4230/LIPIcs.OPODIS.2023.16},
annote = {Keywords: Approximation algorithms, Sparse graphs, The CONGEST model}
}
Document
A Wait-Free Deque With Polylogarithmic Step Complexity
Abstract
The amortized step complexity of operations on all previous lock-free implementations of double-ended queues is linear in the number of processes. This paper presents the first concurrent double-ended queue where the amortized step complexity of each operation is polylogarithmic. Since a stack is a special case of a double-ended queue, this is also the first concurrent stack with polylogarithmic step complexity. The implementation is wait-free and the amortized step complexity is O(log² p + log q) per operation, where p is the number of processes and q is the size of the double-ended queue.
Cite as
Shalom M. Asbell and Eric Ruppert. A Wait-Free Deque With Polylogarithmic Step Complexity. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 17:1-17:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{asbell_et_al:LIPIcs.OPODIS.2023.17,
author = {Asbell, Shalom M. and Ruppert, Eric},
title = {{A Wait-Free Deque With Polylogarithmic Step Complexity}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {17:1--17:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.17},
URN = {urn:nbn:de:0030-drops-195073},
doi = {10.4230/LIPIcs.OPODIS.2023.17},
annote = {Keywords: Lock-Free, Wait-Free, Double-Ended Queue, Deque, Stack, Space-Bounded, Polylogarithmic, Linearizable}
}
Document
Reliable Broadcast Despite Mobile Byzantine Faults
Abstract
We investigate the solvability of the Byzantine Reliable Broadcast and Byzantine Broadcast Channel problems in distributed systems affected by Mobile Byzantine Faults. We show that both problems are not solvable even in one of the most constrained system models for mobile Byzantine faults defined so far. By endowing processes with an additional local failure oracle, we provide a solution to the Byzantine Broadcast Channel problem.
Cite as
Silvia Bonomi, Giovanni Farina, and Sébastien Tixeuil. Reliable Broadcast Despite Mobile Byzantine Faults. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 18:1-18:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{bonomi_et_al:LIPIcs.OPODIS.2023.18,
author = {Bonomi, Silvia and Farina, Giovanni and Tixeuil, S\'{e}bastien},
title = {{Reliable Broadcast Despite Mobile Byzantine Faults}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {18:1--18:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.18},
URN = {urn:nbn:de:0030-drops-195083},
doi = {10.4230/LIPIcs.OPODIS.2023.18},
annote = {Keywords: Byzantine fault-tolerance, Reliable Broadcast, Mobile Byzantine Faults}
}
Document
Probable Approximate Coordination
Abstract
We study the problem of how to coordinate the actions of independent agents in a distributed system where message arrival times are unbounded, but are determined by an exponential probability distribution. Asynchronous protocols executed in such a model are guaranteed to succeed with probability 1. We demonstrate a case in which the best asynchronous protocol can be improved on significantly. Specifically, we focus on the task of performing actions by different agents in a linear temporal order - a problem known in the literature as Ordered Response. In asynchronous systems, ensuring such an ordering requires the construction of a message chain that passes through each acting agent, in order. Solving Ordered Response in this way in our model will terminate in time that grows linearly in the number of participating agents n, in expectation. We show that relaxing the specification slightly allows for a significant saving in time. Namely, if Ordered Response should be guaranteed with high probability (arbitrarily close to 1), it is possible to significantly shorten the expected execution time of the protocol. We present two protocols that adhere to the relaxed specification. One of our protocols executes exponentially faster than a message chain, when the number of participating agents n is large, while the other is roughly quadratically faster. For small values of n, it is also possible to achieve similar results by using a hybrid protocol.
Cite as
Ariel Livshits and Yoram Moses. Probable Approximate Coordination. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 19:1-19:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{livshits_et_al:LIPIcs.OPODIS.2023.19,
author = {Livshits, Ariel and Moses, Yoram},
title = {{Probable Approximate Coordination}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {19:1--19:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.19},
URN = {urn:nbn:de:0030-drops-195090},
doi = {10.4230/LIPIcs.OPODIS.2023.19},
annote = {Keywords: Distributed coordination, ordered response, exponentially distributed delay}
}
Document
Flooding with Absorption: An Efficient Protocol for Heterogeneous Bandits over Complex Networks
Abstract
Multi-armed bandits are extensively used to model sequential decision-making, making them ubiquitous in many real-life applications such as online recommender systems and wireless networking. We consider a multi-agent setting where each agent solves their own bandit instance endowed with a different set of arms. Their goal is to minimize their group regret while collaborating via some communication protocol over a given network. Previous literature on this problem only considered arm heterogeneity and networked agents separately. In this work, we introduce a setting that encompasses both features. For this novel setting, we first provide a rigorous regret analysis for a standard flooding protocol combined with the classic UCB policy. Then, to mitigate the issue of high communication costs incurred by flooding in complex networks, we propose a new protocol called Flooding with Absorption (FwA). We provide a theoretical analysis of the resulting regret bound and discuss the advantages of using FwA over flooding. Lastly, we experimentally verify on various scenarios, including dynamic networks, that FwA leads to significantly lower communication costs despite minimal regret performance loss compared to other network protocols.
Cite as
Junghyun Lee, Laura Schmid, and Se-Young Yun. Flooding with Absorption: An Efficient Protocol for Heterogeneous Bandits over Complex Networks. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 20:1-20:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{lee_et_al:LIPIcs.OPODIS.2023.20,
author = {Lee, Junghyun and Schmid, Laura and Yun, Se-Young},
title = {{Flooding with Absorption: An Efficient Protocol for Heterogeneous Bandits over Complex Networks}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {20:1--20:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.20},
URN = {urn:nbn:de:0030-drops-195100},
doi = {10.4230/LIPIcs.OPODIS.2023.20},
annote = {Keywords: multi-armed bandits, multi-agent systems, collaborative learning, network protocol, flooding}
}
Document
Fault-Tolerant Computing with Unreliable Channels
Abstract
We study implementations of basic fault-tolerant primitives, such as consensus and registers, in message-passing systems subject to process crashes and a broad range of communication failures. Our results characterize the necessary and sufficient conditions for implementing these primitives as a function of the connectivity constraints and synchrony assumptions. Our main contribution is a new algorithm for partially synchronous consensus that is resilient to process crashes and channel failures and is optimal in its connectivity requirements. In contrast to prior work, our algorithm assumes the most general model of message loss where faulty channels are flaky, i.e., can lose messages without any guarantee of fairness. This failure model is particularly challenging for consensus algorithms, as it rules out standard solutions based on leader oracles and failure detectors. To circumvent this limitation, we construct our solution using a new variant of the recently proposed view synchronizer abstraction, which we adapt to the crash-prone setting with flaky channels.
Cite as
Alejandro Naser-Pastoriza, Gregory Chockler, and Alexey Gotsman. Fault-Tolerant Computing with Unreliable Channels. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 21:1-21:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{naserpastoriza_et_al:LIPIcs.OPODIS.2023.21,
author = {Naser-Pastoriza, Alejandro and Chockler, Gregory and Gotsman, Alexey},
title = {{Fault-Tolerant Computing with Unreliable Channels}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {21:1--21:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.21},
URN = {urn:nbn:de:0030-drops-195118},
doi = {10.4230/LIPIcs.OPODIS.2023.21},
annote = {Keywords: Consensus, network partitions, liveness, synchronizers}
}
Document
Local Recurrent Problems in the SUPPORTED Model
Abstract
We study the SUPPORTED model of distributed computing introduced by Schmid and Suomela [Schmid and Suomela, 2013], which generalizes the LOCAL and CONGEST models. In this framework, multiple instances of the same problem, differing from each other by the subnetwork to which they apply. recur over time, and need to be solved efficiently online. To do that, one may rely on an initial preprocessing phase for computing some useful information. This preprocessing phase makes it possible, in some cases, to obtain improved distributed algorithms, overcoming locality-based time lower bounds.
Our main contribution is to expand the class of problems to which the SUPPORTED model applies, by handling also multiple recurring instances of the same problem that differ from each other by some problem specific input, and not only the subnetwork to which they apply. We illustrate this by considering two extended problem classes. The first class, denoted PCS, concerns problems where client nodes of the network need to be served, and each recurring instance applies to some Partial Client Set. The second class, denoted PFO, concerns situations where each recurrent instance of the problem includes a partially fixed output, which needs to be completed to a full consistent solution.
Specifically, we propose some natural recurrent variants of the dominating set problem and the coloring problem that are of interest particularly in the distributed setting. For these problems, we show that information about the topology can be used to overcome locality-based lower bounds. We also categorize the round complexity of Locally Checkable Labellings in the SUPPORTED model for the simple case of paths. Finally we present some interesting open problems and some partial results towards resolving them.
Cite as
Akanksha Agrawal, John Augustine, David Peleg, and Srikkanth Ramachandran. Local Recurrent Problems in the SUPPORTED Model. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{agrawal_et_al:LIPIcs.OPODIS.2023.22,
author = {Agrawal, Akanksha and Augustine, John and Peleg, David and Ramachandran, Srikkanth},
title = {{Local Recurrent Problems in the SUPPORTED Model}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {22:1--22:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.22},
URN = {urn:nbn:de:0030-drops-195124},
doi = {10.4230/LIPIcs.OPODIS.2023.22},
annote = {Keywords: Distributed Algorithms, LOCAL Model, SUPPORTED Model}
}
Document
A Holistic Approach for Trustworthy Distributed Systems with WebAssembly and TEEs
Abstract
Publish/subscribe systems play a key role in enabling communication between numerous devices in distributed and large-scale architectures. While widely adopted, securing such systems often trades portability for additional integrity and attestation guarantees. Trusted Execution Environments (TEEs) offer a potential solution with enclaves to enhance security and trust. However, application development for TEEs is complex, and many existing solutions are tied to specific TEE architectures, limiting adaptability. Current communication protocols also inadequately manage attestation proofs or expose essential attestation information. This paper introduces a novel approach using WebAssembly to address these issues, a key enabling technology nowadays capturing academia and industry attention. We present the design of a portable and fully attested publish/subscribe middleware system as a holistic approach for trustworthy and distributed communication between various systems. Based on this proposal, we have implemented and evaluated in-depth a fully-fledged publish/subscribe broker running within Intel SGX, compiled in WebAssembly, and built on top of industry-battled frameworks and standards, i.e., MQTT and TLS protocols. Our extended TLS protocol preserves the privacy of attestation information, among other benefits. Our experimental results showcase most overheads, revealing a 1.55× decrease in message throughput when using a trusted broker. We open-source the contributions of this work to the research community to facilitate experimental reproducibility.
Cite as
Jämes Ménétrey, Aeneas Grüter, Peterson Yuhala, Julius Oeftiger, Pascal Felber, Marcelo Pasin, and Valerio Schiavoni. A Holistic Approach for Trustworthy Distributed Systems with WebAssembly and TEEs. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 23:1-23:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{menetrey_et_al:LIPIcs.OPODIS.2023.23,
author = {M\'{e}n\'{e}trey, J\"{a}mes and Gr\"{u}ter, Aeneas and Yuhala, Peterson and Oeftiger, Julius and Felber, Pascal and Pasin, Marcelo and Schiavoni, Valerio},
title = {{A Holistic Approach for Trustworthy Distributed Systems with WebAssembly and TEEs}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {23:1--23:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.23},
URN = {urn:nbn:de:0030-drops-195132},
doi = {10.4230/LIPIcs.OPODIS.2023.23},
annote = {Keywords: Publish/Subscribe, WebAssembly, Attestation, TLS, Trusted Execution Environment, Cloud-Edge Continuum}
}
Document
Recoverable and Detectable Self-Implementations of Swap
Abstract
Recoverable algorithms tolerate failures and recoveries of processes by using non-volatile memory. Of particular interest are self-implementations of key operations, in which a recoverable operation is implemented from its non-recoverable counterpart (in addition to reads and writes).
This paper presents two self-implementations of the swap operation. One works in the system-wide failures model, where all processes fail and recover together, and the other in the independent failures model, where each process crashes and recovers independently of the other processes.
Both algorithms are wait-free in crash-free executions, but their recovery code is blocking. We prove that this is inherent for the independent failures model. The impossibility result is proved for implementations of distinguishable operations using interfering functions, and in particular, it applies to a recoverable self-implementation of swap.
Cite as
Tomer Lev Lehman, Hagit Attiya, and Danny Hendler. Recoverable and Detectable Self-Implementations of Swap. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 24:1-24:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{levlehman_et_al:LIPIcs.OPODIS.2023.24,
author = {Lev Lehman, Tomer and Attiya, Hagit and Hendler, Danny},
title = {{Recoverable and Detectable Self-Implementations of Swap}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {24:1--24:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.24},
URN = {urn:nbn:de:0030-drops-195140},
doi = {10.4230/LIPIcs.OPODIS.2023.24},
annote = {Keywords: Multi-core algorithms, persistent memory, non-volatile memory, recoverable objects, detectablitly}
}
Document
Silent Programmable Matter: Coating
Abstract
By Programmable Matter (PM) is usually meant a system of weak and self-organizing computational entities, called particles, which can be programmed via distributed algorithms to collectively achieve some global tasks. We consider the SILBOT model where particles are modeled as finite state automata, living and operating in the cells of a hexagonal grid. Particles are all identical, executing the same deterministic algorithm which is based on local observation of the surroundings, up to two hops. Particles are asynchronous, without any direct means of communication and disoriented but sharing a common handedness, i.e., chirality is assumed. Within such a basic model, we consider a foundational primitive for PM, that is Coating: a set of n particles must move so as to ensure the closed surrounding of an object occupying some connected cells of the grid. We present an optimal deterministic distributed algorithm - along with the correctness proof, that in Θ(n²) rounds solves the Coating problem, where a round concerns the minimal time window within which each particle is activated at least once.
Cite as
Alfredo Navarra and Francesco Piselli. Silent Programmable Matter: Coating. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{navarra_et_al:LIPIcs.OPODIS.2023.25,
author = {Navarra, Alfredo and Piselli, Francesco},
title = {{Silent Programmable Matter: Coating}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {25:1--25:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.25},
URN = {urn:nbn:de:0030-drops-195150},
doi = {10.4230/LIPIcs.OPODIS.2023.25},
annote = {Keywords: Programmable Matter, Coating, Asynchrony, Stigmergy}
}
Document
Tight Bounds on the Message Complexity of Distributed Tree Verification
Abstract
We consider the message complexity of verifying whether a given subgraph of the communication network forms a tree with specific properties both in the KT_ρ (nodes know their ρ-hop neighborhood, including node ids) and the KT₀ (nodes do not have this knowledge) models. We develop a rather general framework that helps in establishing tight lower bounds for various tree verification problems. We also consider two different verification requirements: namely that every node detects in the case the input is incorrect, as well as the requirement that at least one node detects. The results are stronger than previous ones in the sense that we assume that each node knows the number n of nodes in the graph (in some cases) or an α approximation of n (in other cases). For spanning tree verification, we show that the message complexity inherently depends on the quality of the given approximation of n: We show a tight lower bound of Ω(n²) for the case α ≥ √2 and a much better upper bound (i.e., O(n log n)) when nodes are given a tighter approximation. On the other hand, our framework also yields an Ω(n²) lower bound on the message complexity of verifying a minimum spanning tree (MST), which reveals a polynomial separation between ST verification and MST verification. This result holds for randomized algorithms with perfect knowledge of the network size, and even when just one node detects illegal inputs, thus improving over the work of Kor, Korman, and Peleg (2013). For verifying a d-approximate BFS tree, we show that the same lower bound holds even if nodes know n exactly, however, the lower bounds is sensitive to d, which is the stretch parameter. First, under the KT₀ assumption, we show a tight message complexity lower bound of Ω(n²) in the LOCAL model, when d ≤ n/(2+Ω(1)). For the KT_ρ assumption, we obtain an upper bound on the message complexity of O(nlog n) in the CONGEST model, when d ≥ (n-1)/max{2,ρ+1}, and use a novel charging argument to show that Ω((1/ρ)(n/ρ)^{1+c/ρ}) messages are required even in the LOCAL model for comparison-based algorithms. For the well-studied special case of KT₁, we obtain a tight lower bound of Ω(n²).
Cite as
Shay Kutten, Peter Robinson, and Ming Ming Tan. Tight Bounds on the Message Complexity of Distributed Tree Verification. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{kutten_et_al:LIPIcs.OPODIS.2023.26,
author = {Kutten, Shay and Robinson, Peter and Tan, Ming Ming},
title = {{Tight Bounds on the Message Complexity of Distributed Tree Verification}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {26:1--26:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.26},
URN = {urn:nbn:de:0030-drops-195163},
doi = {10.4230/LIPIcs.OPODIS.2023.26},
annote = {Keywords: Distributed Graph Algorithm, Lower Bound}
}
Document
On Polynomial Time Local Decision
Abstract
The field of distributed local decision studies the power of local network algorithms, where each network can see only its own local neighborhood, and must act based on this restricted information. Traditionally, the nodes of the network are assumed to have unbounded local computation power, and this makes the model incomparable with centralized notions of efficiency, namely, the classes 𝖯 and NP. In this work we seek to bridge this gap by studying local algorithms where the nodes are required to be computationally efficient: we introduce the classes PLD and NPLD of polynomial-time local decision and non-deterministic polynomial-time local decision, respectively, and compare them to the centralized complexity classes 𝖯 and NP, and to the distributed classes LD and NLD, which correspond to local deterministic and non-deterministic decision, respectively.
We show that for deterministic algorithms, requiring both computational and distributed efficiency is likely to be more restrictive than either requirement alone: if the nodes do not know the network size, then PLD ⊊ LD ∩ 𝖯 holds unconditionally; if the network size is known to all nodes, then the same separation holds under a widely believed complexity assumption (UP ∩ coUP ≠ 𝖯). However, when nondeterminism is introduced, this distinction vanishes, and NPLD = NLD ∩ NP. To complete the picture, we extend the classes PLD and NPLD into a hierarchy akin to the centralized polynomial hierarchy, and we characterize its connections to the centralized polynomial hierarchy and to the distributed local decision hierarchy of Balliu, D'Angelo, Fraigniaud, and Olivetti.
Cite as
Eden Aldema Tshuva and Rotem Oshman. On Polynomial Time Local Decision. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{aldematshuva_et_al:LIPIcs.OPODIS.2023.27,
author = {Aldema Tshuva, Eden and Oshman, Rotem},
title = {{On Polynomial Time Local Decision}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {27:1--27:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.27},
URN = {urn:nbn:de:0030-drops-195179},
doi = {10.4230/LIPIcs.OPODIS.2023.27},
annote = {Keywords: Local Decision, Polynomial-Time, LD, NLD}
}
Document
On Asynchrony, Memory, and Communication: Separations and Landscapes
Abstract
Research on distributed computing by a team of identical mobile computational entities, called robots, operating in a Euclidean space in Look-Compute-Move (LCM) cycles, has recently focused on better understanding how the computational power of robots depends on the interplay between their internal capabilities (i.e., persistent memory, communication), captured by the four standard computational models (OBLOT, LUMI, FSTA, and FCOM) and the conditions imposed by the external environment, controlling the activation of the robots and their synchronization of their activities, perceived and modeled as an adversarial scheduler.
We consider a set of adversarial asynchronous schedulers ranging from the classical semi-synchronous (Ssynch) and fully asynchronous (Asynch) settings, including schedulers (emerging when studying the atomicity of the combination of operations in the LCM cycles) whose adversarial power is in between those two. We ask the question: what is the computational relationship between a model M₁ under adversarial scheduler K₁ (M₁(K₁)) and a model M₂ under scheduler K₂ (M₂(K₂))? For example, are the robots in M₁(K₁) more powerful (i.e., they can solve more problems) than those in M₂(K₂)?
We answer all these questions by providing, through cross-model analysis, a complete characterization of the computational relationship between the power of the four models of robots under the considered asynchronous schedulers. In this process, we also provide qualified answers to several open questions, including the outstanding one on the proper dominance of Ssynch over Asynch in the case of unrestricted visibility.
Cite as
Paola Flocchini, Nicola Santoro, Yuichi Sudo, and Koichi Wada. On Asynchrony, Memory, and Communication: Separations and Landscapes. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 28:1-28:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{flocchini_et_al:LIPIcs.OPODIS.2023.28,
author = {Flocchini, Paola and Santoro, Nicola and Sudo, Yuichi and Wada, Koichi},
title = {{On Asynchrony, Memory, and Communication: Separations and Landscapes}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {28:1--28:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.28},
URN = {urn:nbn:de:0030-drops-195188},
doi = {10.4230/LIPIcs.OPODIS.2023.28},
annote = {Keywords: Look-Compute-Move, Oblivious mobile robots, Robots with lights, Memory versus Communication, Moving and Computing, Asynchrony}
}
Document
On the Round Complexity of Asynchronous Crusader Agreement
Abstract
We present new lower and upper bounds on the number of communication rounds required for asynchronous Crusader Agreement (CA) and Binding Crusader Agreement (BCA), two primitives that are used for solving binary consensus. We show results for the information theoretic and authenticated settings. In doing so, we present a generic model for proving round complexity lower bounds in the asynchronous setting. In some settings, our attempts to prove lower bounds on round complexity fail. Instead, we show new, tight, rather surprising round complexity upper bounds for Byzantine fault tolerant BCA with and without a PKI setup.
Cite as
Ittai Abraham, Naama Ben-David, Gilad Stern, and Sravya Yandamuri. On the Round Complexity of Asynchronous Crusader Agreement. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 29:1-29:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{abraham_et_al:LIPIcs.OPODIS.2023.29,
author = {Abraham, Ittai and Ben-David, Naama and Stern, Gilad and Yandamuri, Sravya},
title = {{On the Round Complexity of Asynchronous Crusader Agreement}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {29:1--29:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.29},
URN = {urn:nbn:de:0030-drops-195195},
doi = {10.4230/LIPIcs.OPODIS.2023.29},
annote = {Keywords: lower bounds, asynchronous protocols, round complexity}
}
Document
Distributed Partial Coloring via Gradual Rounding
Abstract
For k ≥ 0, k-partial (k+1)-coloring asks to color the nodes of an n-node graph using a palette of k+1 colors such that every node v has at least min{k,deg(v)} neighbors colored with colors different from its own color. Hence, proper (Δ+1)-coloring is the special case of k-partial (k+1)-coloring when k = Δ. Ghaffari and Kuhn [FOCS 2021] recently proved that there exists a deterministic distributed algorithm that solves proper (Δ+1)-coloring of n-node graphs with maximum degree Δ in O(log n ⋅ log²Δ) rounds under the LOCAL model of distributed computing. This breakthrough result is achieved via an original iterated rounding approach. Using the same technique, Ghaffari and Kuhn also showed that there exists a deterministic algorithm that solves proper O(a)-coloring of n-node graphs with arboricity a in O(log n ⋅ log³a) rounds. It directly follows from this latter result that k-partial O(k)-coloring can be solved deterministically in O(log n ⋅ log³k) rounds.
We develop an extension of the Ghaffari and Kuhn algorithm for proper (Δ+1)-coloring, and show that it solves k-partial (k+1)-coloring, thus generalizing their main result. Our algorithm runs in O(log n ⋅ log³k) rounds, like the algorithm that follows from Ghaffari and Kuhn’s algorithm for graphs with bounded arboricity, but uses only k+1 color, i.e., the smallest number c of colors such that every graph has a k-partial c-coloring. Like all the previously mentioned algorithms, our algorithm actually solves the general list-coloring version of the problem. Specifically, every node v receives as input an integer demand d(v) ≤ deg(v), and a list of at least d(v)+1 colors. Every node must then output a color from its list such that the resulting coloring satisfies that every node v has at least d(v) neighbors with colors different from its own. Our algorithm solves this problem in O(log n ⋅ log³k) rounds where k = max_v d(v). Moreover, in the specific case where all lists of colors given to the nodes as input share a common colors c^* known to all nodes, one can save one log k factor. In particular, for standard k-partial (k+1)-coloring, which corresponds to the case where all nodes are given the same list {1,… ,k+1}, one can modify our algorithm so that it runs in O(log n ⋅ log²k) rounds, and thus matches the complexity of Ghaffari and Kuhn’s algorithm for (Δ+1)-coloring for k = Δ.
Cite as
Avinandan Das, Pierre Fraigniaud, and Adi Rosén. Distributed Partial Coloring via Gradual Rounding. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 30:1-30:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{das_et_al:LIPIcs.OPODIS.2023.30,
author = {Das, Avinandan and Fraigniaud, Pierre and Ros\'{e}n, Adi},
title = {{Distributed Partial Coloring via Gradual Rounding}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {30:1--30:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.30},
URN = {urn:nbn:de:0030-drops-195205},
doi = {10.4230/LIPIcs.OPODIS.2023.30},
annote = {Keywords: Distributed graph coloring, partial coloring, weak coloring}
}
Document
A Tight Bound on Multiple Spending in Decentralized Cryptocurrencies
Abstract
The last decade has seen a variety of Asset-Transfer systems designed for decentralized environments. The major problem these systems address is double-spending, and solving it inherently imposes strong trust assumptions on the system participants. In this paper, we take a non-orthodox approach to the double-spending problem that might suit better realistic environments in which these systems are to be deployed. We consider the decentralized trust setting, where each user may independently choose who to trust by forming their local quorums. In this setting, we define k-Spending Asset Transfer, a relaxed version of asset transfer which bounds the number of times a system participant may spend an asset it received. We establish a precise relationship between the decentralized trust assumptions and k, the optimal spending number of the system.
Cite as
João Paulo Bezerra and Petr Kuznetsov. A Tight Bound on Multiple Spending in Decentralized Cryptocurrencies. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 31:1-31:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{bezerra_et_al:LIPIcs.OPODIS.2023.31,
author = {Bezerra, Jo\~{a}o Paulo and Kuznetsov, Petr},
title = {{A Tight Bound on Multiple Spending in Decentralized Cryptocurrencies}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {31:1--31:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.31},
URN = {urn:nbn:de:0030-drops-195210},
doi = {10.4230/LIPIcs.OPODIS.2023.31},
annote = {Keywords: Quorum systems, decentralized trust, consistency measure, asset transfer, accountability}
}
Document
Bounds on Worst-Case Responsiveness for Agreement Algorithms
Abstract
We study the worst-case time complexity of solving two agreement problems, consensus and broadcast, in systems with n processes subject to no more than t process failures. In both problems, correct processes must decide on a common value; in the consensus problem, each process has an input and if the inputs of correct processes are all the same, then that must be the common decision, whereas in the broadcast problem, only one process (the sender) has an input and if the sender is correct, then its input must be the common decision. We focus on systems where there is an upper bound Δ on the message delivery time but it is expected that typically, messages arrive much faster, say within some time d. While Δ may or may not be known in advance, d is inherently unknown and specific to each execution. The goal is to design deterministic algorithms whose running times have minimal to no dependence on Δ, a property called responsiveness.
We present a generic algorithm transformation that, when applied to appropriate eventually-synchronous consensus (or broadcast) algorithms, results in consensus (or broadcast) algorithms for send omission failures, authenticated Byzantine failures, and unauthenticated Byzantine failures whose running times have no dependence on Δ; their worst-case time complexities are all O(td), which is asymptotically optimal. The algorithm for send omission failures requires n > 2t, while those for Byzantine failures, both authenticated and unauthenticated, require n > 3t. The failure-resilience of the unauthenticated Byzantine algorithm is optimal.
For authenticated Byzantine failures, existing agreement algorithms provide worst-case time complexity O(t Δ) when n is at most 3t. (When n ≤ 2t, broadcast is solvable while consensus is not.) We prove a lower bound on the worst-case time complexity of ⌊(3t-n)/2⌋ d + Δ when n is at most 3t. Although lower bounds of Δ and (t+1)d were already known, our new lower bound indicates that, at least when n ≤ 2t, it is impossible for an algorithm to pay these bounds in parallel.
Cite as
Hagit Attiya and Jennifer L. Welch. Bounds on Worst-Case Responsiveness for Agreement Algorithms. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 32:1-32:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{attiya_et_al:LIPIcs.OPODIS.2023.32,
author = {Attiya, Hagit and Welch, Jennifer L.},
title = {{Bounds on Worst-Case Responsiveness for Agreement Algorithms}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {32:1--32:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.32},
URN = {urn:nbn:de:0030-drops-195229},
doi = {10.4230/LIPIcs.OPODIS.2023.32},
annote = {Keywords: bounded-delay model, basic round model, omission failures, Byzantine failures}
}
Document
Black Hole Search in Dynamic Rings: The Scattered Case
Abstract
In this paper we investigate the problem of searching for a black hole in a dynamic graph by a set of scattered agents (i.e., the agents start from arbitrary locations of the graph). The black hole is a node that silently destroys any agent visiting it. This kind of malicious node nicely models network failures such as a crashed host or a virus that erases the visiting agents. The black hole search problem is solved when at least one agent survives, and it has the entire map of the graph with the location of the black hole. We consider the case in which the underlining graph is a dynamic 1-interval connected ring: a ring graph in which at each round at most one edge can be missing. We first show that the problem cannot be solved if the agents can only communicate by using a face-to-face mechanism: this holds for any set of agents of constant size, with respect to the size n of the ring.
To circumvent this impossibility we consider agents equipped with movable pebbles that can be left on nodes as a form of communication with other agents. When pebbles are available, three agents can localize the black hole in O(n²) moves. We show that such a number of agents is optimal. We also show that the complexity is tight, that is Ω(n²) moves are required for any algorithm solving the problem with three agents, even with stronger communication mechanisms (e.g., a whiteboard on each node on which agents can write messages of unlimited size). To the best of our knowledge this is the first paper examining the problem of searching a black hole in a dynamic environment with scattered agents.
Cite as
Giuseppe A. Di Luna, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Black Hole Search in Dynamic Rings: The Scattered Case. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 33:1-33:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{diluna_et_al:LIPIcs.OPODIS.2023.33,
author = {Di Luna, Giuseppe A. and Flocchini, Paola and Prencipe, Giuseppe and Santoro, Nicola},
title = {{Black Hole Search in Dynamic Rings: The Scattered Case}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {33:1--33:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.33},
URN = {urn:nbn:de:0030-drops-195233},
doi = {10.4230/LIPIcs.OPODIS.2023.33},
annote = {Keywords: Black hole search, mobile agents, dynamic graph}
}
Document
Sketching the Path to Efficiency: Lightweight Learned Cache Replacement
Abstract
Cache management policies are responsible for selecting the items that should be kept in the cache, and are therefore a fundamental design choice for obtaining an effective caching solution. Heuristic approaches have been used to identify access patterns that affect cache management decisions. However, their behavior is inconsistent, as they can perform well for certain access patterns and poorly for others. Given machine learning’s (ML) remarkable achievements in predicting diverse problems, ML techniques can be applied to create a cache management policy. Yet a significant challenge arises from the memory overhead associated with ML components. These components retain per item information and must be invoked on each access, contradicting the goal of minimizing the cache’s resource signature.
In this work, we propose ALPS, a light-weight cache management policy that takes into account the cost of the ML component. ALPS combines ML with traditional heuristic-based approaches and facilitates learning by identifying several statistical features derived from space-efficient sketches. ALPS’s ML process derives its features from these sketches, resulting in a lightweight and highly effective meta-policy for cache management. We evaluate our approach over real-world workloads run against five popular heuristic cache management policies as well as a state-of-the-art ML-based policy. In our experiments, ALPS always obtained the best hit ratio. Specifically, ALPS improves the hit ratio compared to LRU by up to 20%, Hyperbolic by up to 31%, ARC by up to 9% and W-TinyLFU by up to 26% on various real-world workloads. Its resource requirements are orders of magnitude lower than previous ML-based approaches.
Cite as
Rana Shahout and Roy Friedman. Sketching the Path to Efficiency: Lightweight Learned Cache Replacement. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 34:1-34:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{shahout_et_al:LIPIcs.OPODIS.2023.34,
author = {Shahout, Rana and Friedman, Roy},
title = {{Sketching the Path to Efficiency: Lightweight Learned Cache Replacement}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {34:1--34:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.34},
URN = {urn:nbn:de:0030-drops-195249},
doi = {10.4230/LIPIcs.OPODIS.2023.34},
annote = {Keywords: Data streams, Memory Management, Cache Policy, ML}
}
Document
Atomic Register Abstractions for Byzantine-Prone Distributed Systems
Abstract
The construction of the atomic register abstraction over crash-prone asynchronous message-passing systems has been extensively studied since the founding work of Attiya, Bar-Noy, and Dolev. It has been shown that t < n/2 (where t is the maximal number of processes that may be faulty) is a necessary and sufficient requirement to build an atomic register. However, little attention has been paid to systems where faulty processes may exhibit a Byzantine behavior. This paper studies three definitions of linearizable single-writer multi-reader registers encountered in the state of the art: Read/Write registers whose read perations return the last written value, Read/Write-Increment registers whose read perations return both the last written value and the number of previously written values, and Read/Append registers whose read perations return the sequence of all previously written values. More specifically, it compares their computing power and the necessary and sufficient conditions on the maximum ratio t/n which makes it possible to build reductions from one register to another. Namely, we prove that t < n/3 is necessary and sufficient to implement a Read/Write-Increment register from Read/Write registers whereas this bound is only t < n/2 for a reduction from a Read/Append register to Read/Write-Increment registers. Reduction algorithms meeting these bounds are also provided.
Cite as
Vincent Kowalski, Achour Mostéfaoui, and Matthieu Perrin. Atomic Register Abstractions for Byzantine-Prone Distributed Systems. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
Copy BibTex To Clipboard
@InProceedings{kowalski_et_al:LIPIcs.OPODIS.2023.35,
author = {Kowalski, Vincent and Most\'{e}faoui, Achour and Perrin, Matthieu},
title = {{Atomic Register Abstractions for Byzantine-Prone Distributed Systems}},
booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
pages = {35:1--35:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-308-9},
ISSN = {1868-8969},
year = {2024},
volume = {286},
editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.35},
URN = {urn:nbn:de:0030-drops-195257},
doi = {10.4230/LIPIcs.OPODIS.2023.35},
annote = {Keywords: Byzantine processes, Concurrent Object, Linearizability, Shared Register}
}