42 Search Results for "Pedone, Fernando"

Volume

LIPIcs, Volume 70

20th International Conference on Principles of Distributed Systems (OPODIS 2016)

OPODIS 2016, December 13-16, 2016, Madrid, Spain

Editors: Panagiota Fatourou, Ernesto Jiménez, and Fernando Pedone

Document
DOI: 10.4230/LIPIcs.OPODIS.2025.9
Contention-Aware Cooperation

Authors: Timothé Albouy, Davide Frey, Mathieu Gestin, Michel Raynal, and François Taïani

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
As shown by Reliable Broadcast and Consensus, cooperation among a set of independent computing entities (sequential processes) is crucial in fault-tolerant distributed computing. Considering n-process asynchronous message-passing systems where some processes may be Byzantine, this paper introduces a novel cooperation abstraction, Contention-Aware Cooperation (CAC). While Reliable Broadcast is a one-to-n cooperation abstraction and Consensus is an n-to-n cooperation abstraction, CAC is a d-to-n cooperation abstraction where d (1 ≤ d ≤ n) varies with each run and remains unknown to the processes. Correct processes accept the same set of 𝓁 pairs ⟨ v,i ⟩ (v is the value proposed by p_i) from the d proposer processes, where 1 ≤ 𝓁 ≤ d and (as d) 𝓁 remains unknown to the processes (except in specific cases). Those 𝓁 values are accepted one at a time, potentially in different orders at each process. In addition, CAC provides each process with an imperfect oracle that provides insights into the values that they may accept in the future. Interestingly, the CAC abstraction is particularly efficient in favorable circumstances, when the oracle becomes accurate, which processes can detect. To illustrate its practical utility, the paper details two applications leveraging CAC: a fast consensus implementation optimized for low contention (named Cascading Consensus), and a novel naming problem that can be solved under full asynchrony. All algorithms presented require signatures.
Cite as

Timothé Albouy, Davide Frey, Mathieu Gestin, Michel Raynal, and François Taïani. Contention-Aware Cooperation. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{albouy_et_al:LIPIcs.OPODIS.2025.9,
  author =	{Albouy, Timoth\'{e} and Frey, Davide and Gestin, Mathieu and Raynal, Michel and Ta\"{i}ani, Fran\c{c}ois},
  title =	{{Contention-Aware Cooperation}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.9},
  URN =		{urn:nbn:de:0030-drops-251823},
  doi =		{10.4230/LIPIcs.OPODIS.2025.9},
  annote =	{Keywords: Agreement, Asynchronous message-passing system, Byzantine processes, Conflict detection, Consensus, Cooperation abstraction, Distributed computing, Fault tolerance, Optimistically terminating consensus, Short-naming}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.20
How Robust Are Synchronous Consensus Protocols?

Authors: Nenad Milošević, Daniel Cason, Zarko Milošević, and Fernando Pedone

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
Synchronous Byzantine fault-tolerant (BFT) protocols have long been a reality in an academic setting, yet their practicality remains debated. The main concern of skeptics of synchronous systems is that the correctness of these protocols depends on the timely delivery of all messages within a predefined synchronous bound, Δ. This dependency creates a challenging tradeoff between protocol correctness and performance, as Δ directly impacts both. In this paper, we examine this tradeoff in detail. Specifically, we introduce BoundBFT, a new synchronous BFT consensus protocol. We analyze how BoundBFT’s correctness can be compromised and use this analysis to design and implement the most effective attack strategies that malicious processes could employ. Furthermore, we experimentally determine the synchronous bound Δ that provides sufficient confidence in maintaining protocol correctness even in the presence of malicious replicas. Finally, we apply this discovered bound to BoundBFT, evaluate its performance, and compare it to state-of-the-art synchronous and partially synchronous protocols.
Cite as

Nenad Milošević, Daniel Cason, Zarko Milošević, and Fernando Pedone. How Robust Are Synchronous Consensus Protocols?. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 20:1-20:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{milosevic_et_al:LIPIcs.OPODIS.2024.20,
  author =	{Milo\v{s}evi\'{c}, Nenad and Cason, Daniel and Milo\v{s}evi\'{c}, Zarko and Pedone, Fernando},
  title =	{{How Robust Are Synchronous Consensus Protocols?}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{20:1--20:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.20},
  URN =		{urn:nbn:de:0030-drops-225560},
  doi =		{10.4230/LIPIcs.OPODIS.2024.20},
  annote =	{Keywords: Synchronous Consensus, Byzantine Failures, Blockchain}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.21
No Symmetric Broadcast Abstraction Characterizes k-Set-Agreement in Message-Passing Systems

Authors: Sylvain Gay, Achour Mostéfaoui, and Matthieu Perrin

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
This paper explores the relationship between broadcast abstractions and the k-set agreement (k-SA) problem in crash-prone asynchronous distributed systems. It specifically investigates whether any broadcast abstraction is computationally equivalent to k-SA in message-passing systems. A key contribution of the paper is the delineation of the realm of "meaningful" broadcast abstractions, through the introduction of two new symmetry properties: compositionality and content-neutrality, inspired by the principle of network neutrality. Such preciseness in definition is essential for this paper’s scope, as our aim is not to characterize the computing power of a specific broadcast abstraction, but rather to explore the domain of broadcast abstractions as a whole, in search of a broadcast abstraction with certain characteristics. The paper’s main contribution is the proof that no broadcast abstraction, which is both content-neutral and compositional, is computationally equivalent to k-set agreement when 1 < k < n, in the crash-prone asynchronous message-passing model. To the best of our knowledge, this result represents the first instance of showing that a coordination problem cannot be expressed by an equivalent broadcast abstraction. It does not establish the absence of an implementation, but rather the absence of a specification that possesses certain properties.
Cite as

Sylvain Gay, Achour Mostéfaoui, and Matthieu Perrin. No Symmetric Broadcast Abstraction Characterizes k-Set-Agreement in Message-Passing Systems. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 21:1-21:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gay_et_al:LIPIcs.OPODIS.2024.21,
  author =	{Gay, Sylvain and Most\'{e}faoui, Achour and Perrin, Matthieu},
  title =	{{No Symmetric Broadcast Abstraction Characterizes k-Set-Agreement in Message-Passing Systems}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{21:1--21:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.21},
  URN =		{urn:nbn:de:0030-drops-225573},
  doi =		{10.4230/LIPIcs.OPODIS.2024.21},
  annote =	{Keywords: Agreement problem, Asynchronous system, Broadcast abstraction, Communication abstraction, Compositionality, Message-passing system, Network neutrality, Process crash, k-Set agreement, Wait-free model, Total order broadcast}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.8
Robust and Fast Blockchain State Synchronization

Authors: Enrique Fynn, Ethan Buchman, Zarko Milosevic, Robert Soulé, and Fernando Pedone

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
State synchronization, the process by which a new or recovering peer catches up with the state of other operational peers, is critical to the operation of blockchain-based systems. Existing approaches to state synchronization typically involve downloading snapshots of system state. Such approaches introduce an attack vector from malicious peers that can significantly degrade performance. Moreover, the process of creating snapshots leads to performance hiccups. This paper presents a technique for peers to catch up with operational peers without trusting any particular peer and gracefully recover from misbehavior during the process. We have integrated our design into a production blockchain middleware. Our evaluation shows that during operation, the transaction throughput is consistently higher without pauses for snapshot construction. Moreover, the time it takes for a new peer to join the blockchain is halved, while at the same time tolerating Byzantine peers.
Cite as

Enrique Fynn, Ethan Buchman, Zarko Milosevic, Robert Soulé, and Fernando Pedone. Robust and Fast Blockchain State Synchronization. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{fynn_et_al:LIPIcs.OPODIS.2022.8,
  author =	{Fynn, Enrique and Buchman, Ethan and Milosevic, Zarko and Soul\'{e}, Robert and Pedone, Fernando},
  title =	{{Robust and Fast Blockchain State Synchronization}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{8:1--8:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.8},
  URN =		{urn:nbn:de:0030-drops-176280},
  doi =		{10.4230/LIPIcs.OPODIS.2022.8},
  annote =	{Keywords: state synchronization, replication, blockchain}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.OPODIS.2016
LIPIcs, Volume 70, OPODIS'16, Complete Volume

Authors: Panagiota Fatourou, Ernesto Jiménez, and Fernando Pedone

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
LIPIcs, Volume 70, OPODIS'16, Complete Volume
Cite as

20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Proceedings{fatourou_et_al:LIPIcs.OPODIS.2016,
  title =	{{LIPIcs, Volume 70, OPODIS'16, Complete Volume}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016},
  URN =		{urn:nbn:de:0030-drops-71111},
  doi =		{10.4230/LIPIcs.OPODIS.2016},
  annote =	{Keywords: Distributed Systems, Performance of Systems, Concurrent Programming, Data Structures, Modes of Computation}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.OPODIS.2016.0
Front Matter, Table of Contents, Preface, Committees, List of Authors

Authors: Panagiota Fatourou, Ernesto Jiménez, and Fernando Pedone

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
Front Matter, Table of Contents, Preface, Committees, List of Authors
Cite as

20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{fatourou_et_al:LIPIcs.OPODIS.2016.0,
  author =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  title =	{{Front Matter, Table of Contents, Preface, Committees, List of Authors}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{0:i--0:xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.0},
  URN =		{urn:nbn:de:0030-drops-70699},
  doi =		{10.4230/LIPIcs.OPODIS.2016.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Committees, List of Authors}
}
Document
Keynote Abstract
DOI: 10.4230/LIPIcs.OPODIS.2016.1
High Throughput Connectomics (Keynote Abstract)

Authors: Nir Shavit

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
Connectomics is an emerging field of neurobiology that uses cutting edge machine learning and image processing to extract brain connectivity graphs from electron microscopy images. It has long been assumed that the processing of connectomics data will require mass storage and farms of CPUs and GPUs and will take months if not years. This talk will discuss the feasibility of designing a high-throughput connectomics-on-demand system that runs on a multicore machine with less than 100 cores and extracts connectomes at the terabyte per hour pace of modern electron microscopes. Building this system required solving algorithmic and performance engineering issues related to scaling machine learning on multicore architectures, and may have important lessons for other problem spaces in the natural sciences, where until now large distributed server or GPU farms seemed to be the only way to go.
Cite as

Nir Shavit. High Throughput Connectomics (Keynote Abstract). In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{shavit:LIPIcs.OPODIS.2016.1,
  author =	{Shavit, Nir},
  title =	{{High Throughput Connectomics}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.1},
  URN =		{urn:nbn:de:0030-drops-70705},
  doi =		{10.4230/LIPIcs.OPODIS.2016.1},
  annote =	{Keywords: Machine learning, multicore architectures}
}
Document
Keynote Abstract
DOI: 10.4230/LIPIcs.OPODIS.2016.2
Blockchain - From the Anarchy of Cryptocurrencies to the Enterprise (Keynote Abstract)

Authors: Christian Cachin

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
A blockchain is a public ledger for recording transactions, maintained by many nodes without central authority through a distributed cryptographic protocol. All nodes validate the information to be appended to the blockchain, and a consensus protocol ensures that the nodes agree on a unique order in which entries are appended. Distributed protocols tolerating faults and adversarial attacks, coupled with cryptographic tools are needed for this. The recent interest in blockchains has revived research on consensus protocols, ranging from the proof-of-work method in Bitcoin's "mining" protocol to classical Byzantine agreement. Going far beyond its use in cryptocurrencies, blockchain is today viewed as a promising technology to simplify trusted exchanges of data and goods among companies. In this context, the Hyperledger Project has been established in early 2016 as an industry-wide collaborative effort to develop an open-source blockchain. This talk will present an overview of blockchain concepts, cryptographic building blocks and consensus mechanisms. It will also introduce Hyperledger Fabric, an implementation of blockchain technology intended for enterprise applications. Being one of the key partners in the Hyperledger Project, IBM is actively involved in the development of this blockchain platform.
Cite as

Christian Cachin. Blockchain - From the Anarchy of Cryptocurrencies to the Enterprise (Keynote Abstract). In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cachin:LIPIcs.OPODIS.2016.2,
  author =	{Cachin, Christian},
  title =	{{Blockchain - From the Anarchy of Cryptocurrencies to the Enterprise}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.2},
  URN =		{urn:nbn:de:0030-drops-70719},
  doi =		{10.4230/LIPIcs.OPODIS.2016.2},
  annote =	{Keywords: consensus, cryptographic, distributed protocols}
}
Document
Keynote Abstract
DOI: 10.4230/LIPIcs.OPODIS.2016.3
Really Big Data: Analytics on Graphs with Trillions of Edges (Keynote Abstract)

Authors: Willy Zwaenepoel

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
Big graphs occur naturally in many applications, most obviously in social networks, but also in many other areas such as biology and forensics. Current approaches to processing large graphs use either supercomputers or very large clusters. In both cases the entire graph must reside in memory before it can be processed. We are pursuing an alternative approach, processing graphs from secondary storage. While this comes with a performance penalty, it makes analytics on very large graphs feasible on a small number of commodity machines. We have developed two systems, one for a single machine and one for a cluster of machines. X-Stream, the single machine solution, aims to make all secondary storage access sequential. It uses two techniques to achieve this goal, edge-centric processing and streaming partitions. Chaos, the cluster solution, starts from the observation that there is little benefit to locality when accessing data from secondary storage over a high-speed network. As a result, Chaos spreads graph data uniformly randomly over storage devices, and uses randomized access to achieve I/O balance. Chaos furthermore uses work stealing to achieve computational load balance. By using these techniques, it avoids the need for expensive partitioning during pre-processing, while still achieving good scaling behavior. With Chaos we have been able to process an 8-trillion-edge graph on 32 machines, a new milestone for graph size on a small cluster. I will describe both systems and their performance on a number of benchmarks and in comparison to state-of-the-art alternatives. This is joint work with Laurent Bindschaedler (EPFL), Jasmina Malicevic (EPFL) and Amitabha Roy (Intel Labs).
Cite as

Willy Zwaenepoel. Really Big Data: Analytics on Graphs with Trillions of Edges (Keynote Abstract). In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{zwaenepoel:LIPIcs.OPODIS.2016.3,
  author =	{Zwaenepoel, Willy},
  title =	{{Really Big Data: Analytics on Graphs with Trillions of Edges}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.3},
  URN =		{urn:nbn:de:0030-drops-70724},
  doi =		{10.4230/LIPIcs.OPODIS.2016.3},
  annote =	{Keywords: large graphs}
}
Document
Keynote Abstract
DOI: 10.4230/LIPIcs.OPODIS.2016.4
Participating Sets, Simulations, and the Consensus Hierarchy (Keynote Abstract)

Authors: Faith Ellen

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
The participating set problem can be solved in an asynchronous system using only registers. I will gently explain this problem and its solution, followed by a new extension, called consistent ordered partition. Next, I will present a wait-free simulation by f + 1 processes of any setconsensus algorithm that tolerates f faults. I will also describe how to extend this simulation using consistent ordered partition. Finally, I will discuss how this extension can be used to prove that, within every level m > 1 of the consensus hierarchy, there is an infinite sequence of increasingly more powerful deterministic objects.
Cite as

Faith Ellen. Participating Sets, Simulations, and the Consensus Hierarchy (Keynote Abstract). In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, p. 4:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ellen:LIPIcs.OPODIS.2016.4,
  author =	{Ellen, Faith},
  title =	{{Participating Sets, Simulations, and the Consensus Hierarchy}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{4:1--4:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.4},
  URN =		{urn:nbn:de:0030-drops-70736},
  doi =		{10.4230/LIPIcs.OPODIS.2016.4},
  annote =	{Keywords: Consensus, shared-memory systems}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.5
Bounded Disagreement

Authors: David Yu Cheng Chan, Vassos Hadzilacos, and Sam Toueg

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
A well-known generalization of the consensus problem, namely, set agreement (SA), limits the number of distinct decision values that processes decide. In some settings, it may be more important to limit the number of "disagreers". Thus, we introduce another natural generalization of the consensus problem, namely, bounded disagreement (BD), which limits the number of processes that decide differently from the plurality. More precisely, in a system with n processes, the (n, l)-BD task has the following requirement: there is a value v such that at most l processes (the disagreers) decide a value other than v. Despite their apparent similarities, the results described below show that bounded disagreement, consensus, and set agreement are in fact fundamentally different problems. We investigate the relationship between bounded disagreement, consensus, and set agreement. In particular, we determine the consensus number for every instance of the BD task. We also determine values of n, l, m, and k such that the (n, l)-BD task can solve the (m, k)-SA task (where m processes can decide at most k distinct values). Using our results and a previously known impossibility result for set agreement, we prove that for all n >= 2, there is a BD task (and a corresponding BD object) that has consensus number n but can not be solved using n-consensus and registers. Prior to our paper, the only objects known to have this unusual characteristic for n >= 2 (which shows that the consensus number of an object is not sufficient to fully capture its power) were artificial objects crafted solely for the purpose of exhibiting this behaviour.
Cite as

David Yu Cheng Chan, Vassos Hadzilacos, and Sam Toueg. Bounded Disagreement. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{yuchengchan_et_al:LIPIcs.OPODIS.2016.5,
  author =	{Yu Cheng Chan, David and Hadzilacos, Vassos and Toueg, Sam},
  title =	{{Bounded Disagreement}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.5},
  URN =		{urn:nbn:de:0030-drops-70742},
  doi =		{10.4230/LIPIcs.OPODIS.2016.5},
  annote =	{Keywords: Consensus, Set Agreement, Asynchronous System, Distributed Algorithms, Shared Memory}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.6
Read-Write Memory and k-Set Consensus as an Affine Task

Authors: Eli Gafni, Yuan He, Petr Kuznetsov, and Thibault Rieutord

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
The wait-free read-write memory model has been characterized as an iterated Immediate Snapshot (IS) task. The IS task is affine — it can be defined as a (sub)set of simplices of the standard chromatic subdivision. In this paper, we highlight the phenomenon of a "natural" model that can be captured by an iterated affine task and, thus, by a subset of runs of the iterated immediate snapshot model. We show that the read-write memory model in which, additionally, k-set-consensus objects can be used is "natural" by presenting the corresponding simple affine task captured by a subset of 2-round IS runs. As an "unnatural" example, the model using the abstraction of Weak Symmetry Breaking (WSB) cannot be captured by a set of IS runs and, thus, cannot be represented as an affine task. Our results imply the first combinatorial characterization of models equipped with abstractions other than read-write memory that applies to generic tasks.
Cite as

Eli Gafni, Yuan He, Petr Kuznetsov, and Thibault Rieutord. Read-Write Memory and k-Set Consensus as an Affine Task. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gafni_et_al:LIPIcs.OPODIS.2016.6,
  author =	{Gafni, Eli and He, Yuan and Kuznetsov, Petr and Rieutord, Thibault},
  title =	{{Read-Write Memory and k-Set Consensus as an Affine Task}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.6},
  URN =		{urn:nbn:de:0030-drops-70759},
  doi =		{10.4230/LIPIcs.OPODIS.2016.6},
  annote =	{Keywords: iterated affine tasks, k-set consensus, k-concurrency, simplicial complexes, immediate snapshot}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.7
Set-Consensus Collections are Decidable

Authors: Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Petr Kuznetsov

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
A natural way to measure the power of a distributed-computing model is to characterize the set of tasks that can be solved in it. In general, however, the question of whether a given task can be solved in a given model is undecidable, even if we only consider the wait-free shared-memory model. In this paper, we address this question for restricted classes of models and tasks. We show that the question of whether a collection C of (l, j)-set consensus objects, for various l (the number of processes that can invoke the object) and j (the number of distinct outputs the object returns), can be used by n processes to solve wait-free k-set consensus is decidable. Moreover, we provide a simple O(n^2) decision algorithm, based on a dynamic programming solution to the Knapsack optimization problem. We then present an adaptive wait-free set-consensus algorithm that, for each set of participating processes, achieves the best level of agreement that is possible to achieve using C. Overall, this gives us a complete characterization of a read-write model defined by a collection of set-consensus objects through its set-consensus power.
Cite as

Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Petr Kuznetsov. Set-Consensus Collections are Decidable. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{delportegallet_et_al:LIPIcs.OPODIS.2016.7,
  author =	{Delporte-Gallet, Carole and Fauconnier, Hugues and Gafni, Eli and Kuznetsov, Petr},
  title =	{{Set-Consensus Collections are Decidable}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.7},
  URN =		{urn:nbn:de:0030-drops-70761},
  doi =		{10.4230/LIPIcs.OPODIS.2016.7},
  annote =	{Keywords: Decidability, distributed tasks, set consensus, Knapsack problem}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.8
k-Set Agreement in Communication Networks with Omission Faults

Authors: Emmanuel Godard and Eloi Perdereau

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
We consider an arbitrary communication network G where at most f messages can be lost at each round, and consider the classical k-set agreement problem in this setting. We characterize exactly for which f the k-set agreement problem can be solved on G. The case with k = 1, that is the Consensus problem, has first been introduced by Santoro and Widmayer in 1989, the characterization is already known from [Coulouma/Godard/Peters, TCS, 2015]. As a first contribution, we present a detailed and complete characterization for the 2-set problem. The proof of the impossibility result uses topological methods. We introduce a new subdivision approach for these topological methods that is of independent interest. In the second part, we show how to extend to the general case with k in N. This characterization is the first complete characterization for this kind of synchronous message passing model, a model that is a subclass of the family of oblivious message adversaries.
Cite as

Emmanuel Godard and Eloi Perdereau. k-Set Agreement in Communication Networks with Omission Faults. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{godard_et_al:LIPIcs.OPODIS.2016.8,
  author =	{Godard, Emmanuel and Perdereau, Eloi},
  title =	{{k-Set Agreement in Communication Networks with Omission Faults}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.8},
  URN =		{urn:nbn:de:0030-drops-70775},
  doi =		{10.4230/LIPIcs.OPODIS.2016.8},
  annote =	{Keywords: k-set agreement, message passing, dynamic networks, message adversary, omission faults}
}
  • Refine by Type
  • 41 Document/PDF
  • 3 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 1 2026
  • 2 2025
  • 1 2023
  • 38 2017

  • Refine by Author
  • 4 Pedone, Fernando
  • 2 Cachin, Christian
  • 2 Fatourou, Panagiota
  • 2 Gafni, Eli
  • 2 Jiménez, Ernesto
  • Show More...

  • Refine by Series/Journal
  • 41 LIPIcs

  • Refine by Classification
  • 2 Computer systems organization → Availability
  • 2 Computer systems organization → Redundancy
  • 2 Computer systems organization → Reliability
  • 2 Computing methodologies → Distributed algorithms
  • 1 Computer systems organization → Dependable and fault-tolerant systems and networks
  • Show More...

  • Refine by Keyword
  • 4 Consensus
  • 2 Blockchain
  • 2 Decidability
  • 2 Simulation
  • 2 Verification
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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