Search Results

Documents authored by Perrin, Matthieu

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.2023.35
Atomic Register Abstractions for Byzantine-Prone Distributed Systems

Authors: Vincent Kowalski, Achour Mostéfaoui, and Matthieu Perrin

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

Abstract
The construction of the atomic register abstraction over crash-prone asynchronous message-passing systems has been extensively studied since the founding work of Attiya, Bar-Noy, and Dolev. It has been shown that t < n/2 (where t is the maximal number of processes that may be faulty) is a necessary and sufficient requirement to build an atomic register. However, little attention has been paid to systems where faulty processes may exhibit a Byzantine behavior. This paper studies three definitions of linearizable single-writer multi-reader registers encountered in the state of the art: Read/Write registers whose read perations return the last written value, Read/Write-Increment registers whose read perations return both the last written value and the number of previously written values, and Read/Append registers whose read perations return the sequence of all previously written values. More specifically, it compares their computing power and the necessary and sufficient conditions on the maximum ratio t/n which makes it possible to build reductions from one register to another. Namely, we prove that t < n/3 is necessary and sufficient to implement a Read/Write-Increment register from Read/Write registers whereas this bound is only t < n/2 for a reduction from a Read/Append register to Read/Write-Increment registers. Reduction algorithms meeting these bounds are also provided.
Cite as

Vincent Kowalski, Achour Mostéfaoui, and Matthieu Perrin. Atomic Register Abstractions for Byzantine-Prone Distributed Systems. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kowalski_et_al:LIPIcs.OPODIS.2023.35,
  author =	{Kowalski, Vincent and Most\'{e}faoui, Achour and Perrin, Matthieu},
  title =	{{Atomic Register Abstractions for Byzantine-Prone Distributed Systems}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{35:1--35:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.35},
  URN =		{urn:nbn:de:0030-drops-195257},
  doi =		{10.4230/LIPIcs.OPODIS.2023.35},
  annote =	{Keywords: Byzantine processes, Concurrent Object, Linearizability, Shared Register}
}
Document
DOI: 10.4230/LIPIcs.DISC.2023.16
Send/Receive Patterns Versus Read/Write Patterns in Crash-Prone Asynchronous Distributed Systems

Authors: Mathilde Déprés, Achour Mostéfaoui, Matthieu Perrin, and Michel Raynal

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
This paper is on the power and computability limits of messages patterns in crash-prone asynchronous message-passing systems. It proposes and investigates three basic messages patterns (encountered in all these systems) each involving two processes, and compares them to their Read/Write counterparts. It is first shown that one of these patterns has no Read/Write counterpart. The paper proposes then a new one-to-all broadcast abstraction, denoted Mutual Broadcast (in short MBroadcast), whose implementation relies on two of the previous messages patterns. This abstraction provides each pair of processes with the following property (called mutual ordering): for any pair of processes p and p', if p broadcasts a message m and p' broadcasts a message m', it is not possible for p to deliver first (its message) m and then m' while p' delivers first (its message) m' and then m. It is shown that MBroadcast and atomic Read/Write registers have the same computability power (independently of the number of crashes). Finally, in addition to its theoretical contribution, the practical interest of MBroadcast is illustrated by its (very simple) use to solve basic upper level coordination problems such as mutual exclusion and consensus. Last but not least, looking for simplicity was also a target of this article.
Cite as

Mathilde Déprés, Achour Mostéfaoui, Matthieu Perrin, and Michel Raynal. Send/Receive Patterns Versus Read/Write Patterns in Crash-Prone Asynchronous Distributed Systems. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 16:1-16:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{depres_et_al:LIPIcs.DISC.2023.16,
  author =	{D\'{e}pr\'{e}s, Mathilde and Most\'{e}faoui, Achour and Perrin, Matthieu and Raynal, Michel},
  title =	{{Send/Receive Patterns Versus Read/Write Patterns in Crash-Prone Asynchronous Distributed Systems}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{16:1--16:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.16},
  URN =		{urn:nbn:de:0030-drops-191420},
  doi =		{10.4230/LIPIcs.DISC.2023.16},
  annote =	{Keywords: Asynchrony, Atomicity, Broadcast abstraction, Characterization, Consensus, Crash failure, Distributed Computability, Distributed software engineering, Computability, Lattice agreement, Message-passing, Message pattern, Mutual exclusion, Quorum, Read/write pattern, Read/Write register, Test\&Set, Simplicity, Two-process communication}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.11
Wait-Free CAS-Based Algorithms: The Burden of the Past

Authors: Denis Bédin, François Lépine, Achour Mostéfaoui, Damien Perez, and Matthieu Perrin

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
Herlihy proved that CAS is universal in the classical computing system model composed of an a priori known number of processes. This means that CAS can implement, together with reads and writes, any object with a sequential specification. For this, he proposed the first universal construction capable of emulating any data structure. It has recently been proved that CAS is still universal in the infinite arrival computing model, a model where any number of processes can be created on the fly (e.g. multi-threaded systems). In this paper, we prove that CAS does not allow to implement wait-free and linearizable visible objects in the infinite model with a space complexity bounded by the number of active processes (i.e. ones that have operations in progress on this object). This paper also shows that this lower bound is tight, in the sense that this dependency can be made as low as desired (e.g. logarithmic) by proposing a wait-free and linearizable universal construction, using the compare-and-swap operation, whose space complexity in the number of ever issued operations is defined by a parameter that can be linked to any unbounded function.
Cite as

Denis Bédin, François Lépine, Achour Mostéfaoui, Damien Perez, and Matthieu Perrin. Wait-Free CAS-Based Algorithms: The Burden of the Past. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bedin_et_al:LIPIcs.DISC.2021.11,
  author =	{B\'{e}din, Denis and L\'{e}pine, Fran\c{c}ois and Most\'{e}faoui, Achour and Perez, Damien and Perrin, Matthieu},
  title =	{{Wait-Free CAS-Based Algorithms: The Burden of the Past}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.11},
  URN =		{urn:nbn:de:0030-drops-148131},
  doi =		{10.4230/LIPIcs.DISC.2021.11},
  annote =	{Keywords: Compare-And-Swap, Concurrent Object, Infinite arrival model, Linearizability, Memory complexity, Multi-Threaded Systems, Shared-Memory, Universality, Wait-freedom}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2019.38
Brief Announcement: Wait-Free Universality of Consensus in the Infinite Arrival Model

Authors: Grégoire Bonin, Achour Mostéfaoui, and Matthieu Perrin

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
In classical asynchronous distributed systems composed of a fixed number n of processes where some proportion may fail by crashing, many objects do not have a wait-free linearizable implementation (e.g. stacks, queues, etc.). It has been proved that consensus is universal in such systems, which means that this system augmented with consensus objects allows to implement any object that has a sequential specification. In this paper, we consider a more general system model called infinite arrival model where infinitely many processes may arrive and leave or crash during a run. We prove that consensus is still universal in this more general model. For that, we propose a universal construction based on a weak log that can be implementated using consensus objects.
Cite as

Grégoire Bonin, Achour Mostéfaoui, and Matthieu Perrin. Brief Announcement: Wait-Free Universality of Consensus in the Infinite Arrival Model. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 38:1-38:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bonin_et_al:LIPIcs.DISC.2019.38,
  author =	{Bonin, Gr\'{e}goire and Most\'{e}faoui, Achour and Perrin, Matthieu},
  title =	{{Brief Announcement: Wait-Free Universality of Consensus in the Infinite Arrival Model}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{38:1--38:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.38},
  URN =		{urn:nbn:de:0030-drops-113454},
  doi =		{10.4230/LIPIcs.DISC.2019.38},
  annote =	{Keywords: Concurrent object, Consensus, Infinite arrival model, Linearizability, Universal construction, Wait-freedom}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.27
Which Broadcast Abstraction Captures k-Set Agreement?

Authors: Damien Imbs, Achour Mostéfaoui, Matthieu Perrin, and Michel Raynal

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
It is well-known that consensus (one-set agreement) and total order broadcast are equivalent in asynchronous systems prone to process crash failures. Considering wait-free systems, this article addresses and answers the following question: which is the communication abstraction that "captures" k-set agreement? To this end, it introduces a new broadcast communication abstraction, called k-BO-Broadcast, which restricts the disagreement on the local deliveries of the messages that have been broadcast (1-BO-Broadcast boils down to total order broadcast). Hence, in this context, k=1 is not a special number, but only the first integer in an increasing integer sequence. This establishes a new "correspondence" between distributed agreement problems and communication abstractions, which enriches our understanding of the relations linking fundamental issues of fault-tolerant distributed computing.
Cite as

Damien Imbs, Achour Mostéfaoui, Matthieu Perrin, and Michel Raynal. Which Broadcast Abstraction Captures k-Set Agreement?. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{imbs_et_al:LIPIcs.DISC.2017.27,
  author =	{Imbs, Damien and Most\'{e}faoui, Achour and Perrin, Matthieu and Raynal, Michel},
  title =	{{Which Broadcast Abstraction Captures k-Set Agreement?}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{27:1--27:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.27},
  URN =		{urn:nbn:de:0030-drops-79943},
  doi =		{10.4230/LIPIcs.DISC.2017.27},
  annote =	{Keywords: Agreement problem, Antichain, Asynchronous system, Communication abstraction, Consensus, Message-passing system, Partially ordered set, Process crash}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact