47 Search Results for "Wada, Koichi"

Volume

LIPIcs, Volume 286

27th International Conference on Principles of Distributed Systems (OPODIS 2023)

OPODIS 2023, December 6-8, 2023, Tokyo, Japan

Editors: Alysson Bessani, Xavier Défago, Junya Nakamura, Koichi Wada, and Yukiko Yamauchi

Document
DOI: 10.4230/LIPIcs.MFCS.2024.60
On the Complexity of Community-Aware Network Sparsification

Authors: Emanuel Herrendorf, Christian Komusiewicz, Nils Morawietz, and Frank Sommer

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
In the NP-hard Π-Network Sparsification problem, we are given an edge-weighted graph G, a collection 𝒞 of c subsets of V(G), called communities, and two numbers 𝓁 and b, and the question is whether there exists a spanning subgraph G' of G with at most 𝓁 edges of total weight at most b such that G'[C] fulfills Π for each community C ∈ 𝒞. We study the fine-grained and parameterized complexity of two special cases of this problem: Connectivity NWS where Π is the connectivity property and Stars NWS, where Π is the property of having a spanning star. First, we provide a tight 2^Ω(n²+c)-time running time lower bound based on the ETH for both problems, where n is the number of vertices in G even if all communities have size at most 4, G is a clique, and every edge has unit weight. For the connectivity property, the unit weight case with G being a clique is the well-studied problem of computing a hypergraph support with a minimum number of edges. We then study the complexity of both problems parameterized by the feedback edge number t of the solution graph G'. For Stars NWS, we present an XP-algorithm for t answering an open question by Korach and Stern [Discret. Appl. Math. '08] who asked for the existence of polynomial-time algorithms for t = 0. In contrast, we show for Connectivity NWS that known polynomial-time algorithms for t = 0 [Korach and Stern, Math. Program. '03; Klemz et al., SWAT '14] cannot be extended to larger values of t by showing NP-hardness for t = 1.
Cite as

Emanuel Herrendorf, Christian Komusiewicz, Nils Morawietz, and Frank Sommer. On the Complexity of Community-Aware Network Sparsification. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 60:1-60:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{herrendorf_et_al:LIPIcs.MFCS.2024.60,
  author =	{Herrendorf, Emanuel and Komusiewicz, Christian and Morawietz, Nils and Sommer, Frank},
  title =	{{On the Complexity of Community-Aware Network Sparsification}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{60:1--60:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.60},
  URN =		{urn:nbn:de:0030-drops-206169},
  doi =		{10.4230/LIPIcs.MFCS.2024.60},
  annote =	{Keywords: parameterized complexity, hypergraph support, above guarantee parameterization, exponential-time-hypothesis}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.OPODIS.2023
LIPIcs, Volume 286, OPODIS 2023, Complete Volume

Authors: Alysson Bessani, Xavier Défago, Junya Nakamura, Koichi Wada, and Yukiko Yamauchi

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

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.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
DOI: 10.4230/LIPIcs.OPODIS.2023.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Alysson Bessani, Xavier Défago, Junya Nakamura, Koichi Wada, and Yukiko Yamauchi

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

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.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
DOI: 10.4230/LIPIcs.OPODIS.2023.1
From Consensus Research to Redbelly Network Pty Ltd (Invited Talk)

Authors: Vincent Gramoli

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

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.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
DOI: 10.4230/LIPIcs.OPODIS.2023.2
Quantum Distributed Computing: Potential and Limitations (Invited Talk)

Authors: François Le Gall

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

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.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
DOI: 10.4230/LIPIcs.OPODIS.2023.3
Distributed Algorithms as a Gateway To Deductive Learning (Invited Talk)

Authors: Roger Wattenhofer

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

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.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
DOI: 10.4230/LIPIcs.OPODIS.2023.4
The Synchronization Power of Auditable Registers

Authors: Hagit Attiya, Antonella Del Pozzo, Alessia Milani, Ulysse Pavloff, and Alexandre Rapetti

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

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.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
DOI: 10.4230/LIPIcs.OPODIS.2023.5
𝒪(log{n})-Time Uniform Circle Formation for Asynchronous Opaque Luminous Robots

Authors: Caterina Feletti, Carlo Mereghetti, and Beatrice Palano

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

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.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
DOI: 10.4230/LIPIcs.OPODIS.2023.6
Multi-Valued Connected Consensus: A New Perspective on Crusader Agreement and Adopt-Commit

Authors: Hagit Attiya and Jennifer L. Welch

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

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.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
DOI: 10.4230/LIPIcs.OPODIS.2023.7
Energy-Constrained Programmable Matter Under Unfair Adversaries

Authors: Jamison W. Weber, Tishya Chhabra, Andréa W. Richa, and Joshua J. Daymude

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

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.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
DOI: 10.4230/LIPIcs.OPODIS.2023.8
A Fair and Resilient Decentralized Clock Network for Transaction Ordering

Authors: Andrei Constantinescu, Diana Ghinea, Lioba Heimbach, Zilin Wang, and Roger Wattenhofer

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

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.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
DOI: 10.4230/LIPIcs.OPODIS.2023.9
Byzantine Consensus in Abstract MAC Layer

Authors: Lewis Tseng and Callie Sardina

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

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.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
DOI: 10.4230/LIPIcs.OPODIS.2023.10
Discrete Incremental Voting

Authors: Colin Cooper, Tomasz Radzik, and Takeharu Shiraga

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

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.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
DOI: 10.4230/LIPIcs.OPODIS.2023.11
On the Convergence Time in Graphical Games: A Locality-Sensitive Approach

Authors: Juho Hirvonen, Laura Schmid, Krishnendu Chatterjee, and Stefan Schmid

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

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.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}
}
  • Refine by Author
  • 10 Wada, Koichi
  • 4 Attiya, Hagit
  • 4 Défago, Xavier
  • 4 Tixeuil, Sébastien
  • 3 Flocchini, Paola
  • Show More...

  • Refine by Classification
  • 25 Theory of computation → Distributed algorithms
  • 6 Computing methodologies → Distributed algorithms
  • 5 Theory of computation → Distributed computing models
  • 4 Computer systems organization → Dependable and fault-tolerant systems and networks
  • 4 Security and privacy → Distributed systems security
  • Show More...

  • Refine by Keyword
  • 3 Autonomous mobile robots
  • 2 Asynchrony
  • 2 Consensus
  • 2 Lights
  • 2 Look-Compute-Move
  • Show More...

  • Refine by Type
  • 46 document
  • 1 volume

  • Refine by Publication Year
  • 39 2024
  • 5 2019
  • 2 2020
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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