92 Search Results for "Bramas, Quentin"

Volume

LIPIcs, Volume 217

25th International Conference on Principles of Distributed Systems (OPODIS 2021)

OPODIS 2021, December 13-15, 2021, Strasbourg, France

Editors: Quentin Bramas, Vincent Gramoli, and Alessia Milani

Volume

OASIcs, Volume 82

2nd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2020)

Tokenomics 2020, October 26-27, 2020, Toulouse, France

Editors: Emmanuelle Anceaume, Christophe Bisière, Matthieu Bouvard, Quentin Bramas, and Catherine Casamatta

Volume

LIPIcs, Volume 184

24th International Conference on Principles of Distributed Systems (OPODIS 2020)

OPODIS 2020, December 14-16, 2020, Strasbourg, France (Virtual Conference)

Editors: Quentin Bramas, Rotem Oshman, and Paolo Romano

Document
DOI: 10.4230/LIPIcs.OPODIS.2024.9
Crash-Tolerant Exploration of Trees by Energy-Sharing Mobile Agents

Authors: Quentin Bramas, Toshimitsu Masuzawa, and Sébastien Tixeuil

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

Abstract
We consider the problem of graph exploration by energy sharing mobile agents that are subject to crash faults. More precisely, we consider a team of two agents where at most one of them may fail unpredictably, and the considered topology is that of connected acyclic graphs (i.e. trees). We consider both the asynchronous and the synchronous settings, and we provide necessary and sufficient conditions about the energy.
Cite as

Quentin Bramas, Toshimitsu Masuzawa, and Sébastien Tixeuil. Crash-Tolerant Exploration of Trees by Energy-Sharing Mobile Agents. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bramas_et_al:LIPIcs.OPODIS.2024.9,
  author =	{Bramas, Quentin and Masuzawa, Toshimitsu and Tixeuil, S\'{e}bastien},
  title =	{{Crash-Tolerant Exploration of Trees by Energy-Sharing Mobile Agents}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{9:1--9:16},
  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.9},
  URN =		{urn:nbn:de:0030-drops-225452},
  doi =		{10.4230/LIPIcs.OPODIS.2024.9},
  annote =	{Keywords: Mobile Agents, Distributed Algorithms, Energy sharing}
}
Document
DOI: 10.4230/LIPIcs.SAND.2024.7
Online Space-Time Travel Planning in Dynamic Graphs

Authors: Quentin Bramas, Jean-Romain Luttringer, and Sébastien Tixeuil

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract
We study the problem of traveling in an unknown dynamic graph, to reach a destination with minimum latency. At each step of the execution, an agent can decide to move to a neighboring node if an edge exists at this time instant, wait at the current node in the hope that other links will appear in the future, or move backward in time using an expensive time travel device. A travel that makes use of backward time travel is called a space-time travel. Our aim is to arrive at the destination with zero delay, which always requires the use of backward time travel if no path exists to the destination during the first time instant. Finding an optimal space-time travel is polynomial when the agent knows the entire dynamic graph (including the future edges), even with additional constraints. However, we consider in this paper that the agent discovers the dynamic graph while it is exploring it, in an online manner. In this paper, we propose two models that define how an agent learns new knowledge about the dynamic graph during the execution of its protocol: the T-online model, where the agent reaching time t learns about the entire past of the network until t (even nodes not yet visited), and the S-online model, where the agent learns about the past and future about the current node he is located at. We present an algorithm with an optimal competitive ratio of 2 for the T-online model. In the S-online model, we prove a lower bound of 2/3n-7/4 and an upper bound of 2n-3 on the optimal competitive ratio when the cost function is linear.
Cite as

Quentin Bramas, Jean-Romain Luttringer, and Sébastien Tixeuil. Online Space-Time Travel Planning in Dynamic Graphs. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bramas_et_al:LIPIcs.SAND.2024.7,
  author =	{Bramas, Quentin and Luttringer, Jean-Romain and Tixeuil, S\'{e}bastien},
  title =	{{Online Space-Time Travel Planning in Dynamic Graphs}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.7},
  URN =		{urn:nbn:de:0030-drops-198854},
  doi =		{10.4230/LIPIcs.SAND.2024.7},
  annote =	{Keywords: Dynamic graphs, online algorithm, space-time travel, treasure hunt}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2024.25
Brief Announcement: Crash-Tolerant Exploration of Trees by Energy Sharing Mobile Agents

Authors: Quentin Bramas, Toshimitsu Masuzawa, and Sébastien Tixeuil

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract
We consider the problem of graph exploration by energy sharing mobile agents that are subject to crash faults. More precisely, we consider a team of two agents where at most one of them may fail unpredictably, and the considered topology is that of acyclic graphs (i.e. trees). We consider both the asynchronous and the synchronous settings, and we provide necessary and sufficient conditions about the energy in two settings: line-shaped graphs, and general trees.
Cite as

Quentin Bramas, Toshimitsu Masuzawa, and Sébastien Tixeuil. Brief Announcement: Crash-Tolerant Exploration of Trees by Energy Sharing Mobile Agents. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 25:1-25:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bramas_et_al:LIPIcs.SAND.2024.25,
  author =	{Bramas, Quentin and Masuzawa, Toshimitsu and Tixeuil, S\'{e}bastien},
  title =	{{Brief Announcement: Crash-Tolerant Exploration of Trees by Energy Sharing Mobile Agents}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{25:1--25:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.25},
  URN =		{urn:nbn:de:0030-drops-199031},
  doi =		{10.4230/LIPIcs.SAND.2024.25},
  annote =	{Keywords: Mobile Agents, Distributed Algorithms, Energy sharing}
}
Document
DOI: 10.4230/LIPIcs.FUN.2022.7
Beedroids: How Luminous Autonomous Swarms of UAVs Can Save the World?

Authors: Quentin Bramas, Stéphane Devismes, Anaïs Durand, Pascal Lafourcade, and Anissa Lamani

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract
Bee extinction is a great risk for humanity. To circumvent this ineluctable disaster, we propose to develop beedroids, i.e., small UAVs mimicking the behaviors of real bees. Those beedroids are endowed with very weak capabilities (short-range visibility sensors, no GPS, light with a few colors, ...). Like real bees, they have to self-organize together into swarms. Beedroid swarms will be deployed in cuboid-shaped greenhouse. Each beedroid swarm will have to indefinitely search for flowers to pollinate in its greenhouse. We model this problem as a perpetual exploration of a 3D grid by a swarm of beedroids. In this paper, we propose two optimal solutions to solve this problem and so to save humanity.
Cite as

Quentin Bramas, Stéphane Devismes, Anaïs Durand, Pascal Lafourcade, and Anissa Lamani. Beedroids: How Luminous Autonomous Swarms of UAVs Can Save the World?. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bramas_et_al:LIPIcs.FUN.2022.7,
  author =	{Bramas, Quentin and Devismes, St\'{e}phane and Durand, Ana\"{i}s and Lafourcade, Pascal and Lamani, Anissa},
  title =	{{Beedroids: How Luminous Autonomous Swarms of UAVs Can Save the World?}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.7},
  URN =		{urn:nbn:de:0030-drops-159771},
  doi =		{10.4230/LIPIcs.FUN.2022.7},
  annote =	{Keywords: Bee extinction, luminous swarms of beedroids, perpetual flower pollination problem, greenhouse}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.OPODIS.2021
LIPIcs, Volume 217, OPODIS 2021, Complete Volume

Authors: Quentin Bramas, Vincent Gramoli, and Alessia Milani

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
LIPIcs, Volume 217, OPODIS 2021, Complete Volume
Cite as

25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 1-580, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Proceedings{bramas_et_al:LIPIcs.OPODIS.2021,
  title =	{{LIPIcs, Volume 217, OPODIS 2021, Complete Volume}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{1--580},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021},
  URN =		{urn:nbn:de:0030-drops-157746},
  doi =		{10.4230/LIPIcs.OPODIS.2021},
  annote =	{Keywords: LIPIcs, Volume 217, OPODIS 2021, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.OPODIS.2021.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Quentin Bramas, Vincent Gramoli, and Alessia Milani

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bramas_et_al:LIPIcs.OPODIS.2021.0,
  author =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.0},
  URN =		{urn:nbn:de:0030-drops-157752},
  doi =		{10.4230/LIPIcs.OPODIS.2021.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.OPODIS.2021.1
Distributed Algorithms: A Challenging Playground for Model Checking (Invited Talk)

Authors: Nathalie Bertrand

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
Distributed computing is increasingly spreading, in advanced technological applications as well as in our daily life. Failures in distributed algorithms can have important human and financial consequences, so that is is crucial to develop rigorous techniques to verify their correctness. Model checking is a model-based approach to formal verification, dating back the 80’s. It has been successfully applied first to hardware, and later to software verification. Distributed computing raises new challenges for the model checking community, and calls for the development of new verification techniques and tools. In particular, the parameterized verification paradigm is nowadays blooming to help proving automatically the correctness of distributed algorithms. In this invited talk, we present recent parameterized verification developments to automatically prove properties of some classical distributed algorithms.
Cite as

Nathalie Bertrand. Distributed Algorithms: A Challenging Playground for Model Checking (Invited Talk). In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bertrand:LIPIcs.OPODIS.2021.1,
  author =	{Bertrand, Nathalie},
  title =	{{Distributed Algorithms: A Challenging Playground for Model Checking}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.1},
  URN =		{urn:nbn:de:0030-drops-157767},
  doi =		{10.4230/LIPIcs.OPODIS.2021.1},
  annote =	{Keywords: Verification, Distributed algorithms}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.OPODIS.2021.2
Accountable Distributed Computing (Invited Talk)

Authors: Petr Kuznetsov

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
There are two major ways to deal with failures in distributed computing: fault-tolerance and accountability. Fault-tolerance intends to anticipate failures by investing into replication and synchronization, so that the system’s correctness is not affected by faulty components. In contrast, accountability enables detecting failures a posteriori and raising undeniable evidences against faulty components. In this talk, we discuss how accountability can be achieved, both in generic and application-specific ways. We begin with an overview of fault detection mechanisms used in benign, crash-prone system, with a focus on the weakest failure detector question. We then consider the fault detection problem in systems with general, Byzantine failures and explore which classes of misbehavior can be detected and which - cannot. We then study the mechanism of application-specific accountability that, intuitively, only accounts for instances of misbehavior that affect particular correctness criteria. Finally, we discuss how fault detection can be combined with reconfiguration, opening an avenue of "self-healing" systems that seamlessly replace faulty system components with correct ones.
Cite as

Petr Kuznetsov. Accountable Distributed Computing (Invited Talk). In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kuznetsov:LIPIcs.OPODIS.2021.2,
  author =	{Kuznetsov, Petr},
  title =	{{Accountable Distributed Computing}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.2},
  URN =		{urn:nbn:de:0030-drops-157775},
  doi =		{10.4230/LIPIcs.OPODIS.2021.2},
  annote =	{Keywords: Fault-tolerance, fault detection, accountability, application-specific}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.OPODIS.2021.3
A Fresh Look at the Design and Implementation of Communication Paradigms (Invited Talk)

Authors: Robbert van Renesse

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
Datacenter applications consist of many communicating components and evolve organically as requirements develop over time. In this talk I will present two projects that try to support such organic growth. The first project, Escher, recognizes that components of a distributed systems may themselves be distributed systems. Escher introduces a communication abstraction that hides the internals of a distributed component, and in particular how to communicate with it, from other components. Using Escher, a replicated server can invoke another replicated server without either server having to even know that the servers are replicated. The second project, Scalog, presents a datacenter scale totally ordered logging service. Logs are increasingly a central component in many datacenter applications, but log configurations can lead to significant hiccups in the performance of those applications. Scalog has seamless reconfiguration operations that allow it to scale up and down without any downtime.
Cite as

Robbert van Renesse. A Fresh Look at the Design and Implementation of Communication Paradigms (Invited Talk). In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{vanrenesse:LIPIcs.OPODIS.2021.3,
  author =	{van Renesse, Robbert},
  title =	{{A Fresh Look at the Design and Implementation of Communication Paradigms}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.3},
  URN =		{urn:nbn:de:0030-drops-157780},
  doi =		{10.4230/LIPIcs.OPODIS.2021.3},
  annote =	{Keywords: Distributed systems}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.4
Arbitrarily Accurate Aggregation Scheme for Byzantine SGD

Authors: Alexandre Maurer

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
A very common optimization technique in Machine Learning is Stochastic Gradient Descent (SGD). SGD can easily be distributed: several workers try to estimate the gradient of a loss function, and a central parameter server gathers these estimates. When all workers behave correctly, the more workers we have, the more accurate the gradient estimate is. We call this the Arbitrary Aggregation Accuracy (AAA) property. However, in practice, some workers may be Byzantine (i.e., have an arbitrary behavior). Interestingly, when a fixed fraction of workers is assumed to be Byzantine (e.g. 20%), no existing aggregation scheme has the AAA property. In this paper, we propose the first aggregation scheme that has this property despite a fixed fraction of Byzantine workers (less than 50%). We theoretically prove this property, and then illustrate it with simulations.
Cite as

Alexandre Maurer. Arbitrarily Accurate Aggregation Scheme for Byzantine SGD. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{maurer:LIPIcs.OPODIS.2021.4,
  author =	{Maurer, Alexandre},
  title =	{{Arbitrarily Accurate Aggregation Scheme for Byzantine SGD}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.4},
  URN =		{urn:nbn:de:0030-drops-157793},
  doi =		{10.4230/LIPIcs.OPODIS.2021.4},
  annote =	{Keywords: distributed machine learning, Byzantine failures, stochastic gradient descent}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.5
Good-Case and Bad-Case Latency of Unauthenticated Byzantine Broadcast: A Complete Categorization

Authors: Ittai Abraham, Ling Ren, and Zhuolun Xiang

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
This paper studies the good-case latency of unauthenticated Byzantine fault-tolerant broadcast, which measures the time it takes for all non-faulty parties to commit given a non-faulty broadcaster. For both asynchrony and synchrony, we show that n ≥ 4f is the tight resilience threshold that separates good-case 2 rounds and 3 rounds. For asynchronous Byzantine reliable broadcast (BRB), we also investigate the bad-case latency for all non-faulty parties to commit when the broadcaster is faulty but some non-faulty party commits. We provide matching upper and lower bounds on the resilience threshold of bad-case latency for BRB protocols with optimal good-case latency of 2 rounds. In particular, we show 2 impossibility results and propose 4 asynchronous BRB protocols.
Cite as

Ittai Abraham, Ling Ren, and Zhuolun Xiang. Good-Case and Bad-Case Latency of Unauthenticated Byzantine Broadcast: A Complete Categorization. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.OPODIS.2021.5,
  author =	{Abraham, Ittai and Ren, Ling and Xiang, Zhuolun},
  title =	{{Good-Case and Bad-Case Latency of Unauthenticated Byzantine Broadcast: A Complete Categorization}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.5},
  URN =		{urn:nbn:de:0030-drops-157806},
  doi =		{10.4230/LIPIcs.OPODIS.2021.5},
  annote =	{Keywords: Byzantine broadcast, asynchrony, synchrony, latency, good-case, optimal}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.6
On Finality in Blockchains

Authors: Emmanuelle Anceaume, Antonella Del Pozzo, Thibault Rieutord, and Sara Tucci-Piergiovanni

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
This paper focuses on blockchain finality, which refers to the time when it becomes impossible to remove a block that has previously been appended to the blockchain. Blockchain finality can be deterministic or probabilistic, immediate or eventual. To favor availability against consistency in the face of partitions, most blockchains only offer probabilistic eventual finality: blocks may be revoked after being appended to the blockchain, yet with decreasing probability as they sink deeper into the chain. Other blockchains favor consistency by leveraging the immediate finality of Consensus - a block appended is never revoked - at the cost of additional synchronization. The quest for "good" deterministic finality properties for blockchains is still in its infancy, though. Our motivation is to provide a thorough study of several possible deterministic finality properties and explore their solvability. This is achieved by introducing the notion of bounded revocation, which informally says that the number of blocks that can be revoked from the current blockchain is bounded. Based on the requirements we impose on this revocation number, we provide reductions between different forms of eventual finality, Consensus and Eventual Consensus. From these reductions, we show some related impossibility results in presence of Byzantine processes, and provide non-trivial results. In particular, we provide an algorithm that solves a weak form of eventual finality in an asynchronous system in presence of an unbounded number of Byzantine processes. We also provide an algorithm that solves eventual finality with a bounded revocation number in an eventually synchronous environment in presence of less than half of Byzantine processes. The simplicity of the arguments should better guide blockchain designs and link them to clear formal properties of finality.
Cite as

Emmanuelle Anceaume, Antonella Del Pozzo, Thibault Rieutord, and Sara Tucci-Piergiovanni. On Finality in Blockchains. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{anceaume_et_al:LIPIcs.OPODIS.2021.6,
  author =	{Anceaume, Emmanuelle and Del Pozzo, Antonella and Rieutord, Thibault and Tucci-Piergiovanni, Sara},
  title =	{{On Finality in Blockchains}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.6},
  URN =		{urn:nbn:de:0030-drops-157810},
  doi =		{10.4230/LIPIcs.OPODIS.2021.6},
  annote =	{Keywords: Blockchain, consistency properties, Byzantine tolerant implementations}
}
  • Refine by Author
  • 12 Bramas, Quentin
  • 5 Tixeuil, Sébastien
  • 5 Tucci-Piergiovanni, Sara
  • 4 Abraham, Ittai
  • 4 Kuhn, Fabian
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 9 Blockchain
  • 5 Consensus
  • 4 Distributed Computing
  • 4 distributed graph algorithms
  • 3 Blockchains
  • Show More...

  • Refine by Type
  • 89 document
  • 3 volume

  • Refine by Publication Year
  • 52 2021
  • 35 2022
  • 2 2020
  • 2 2024
  • 1 2025

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 About DROPS Imprint Privacy Contact