10 Search Results for "Perrin, Matthieu"

Document
DOI: 10.4230/LIPIcs.DISC.2025.15
Asynchronous Latency and Fast Atomic Snapshot

Authors: João Paulo Bezerra, Luciano Freitas, Petr Kuznetsov, and Matthieu Rambaud

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
This paper introduces a novel, fast atomic-snapshot protocol for asynchronous message-passing systems. In the process of defining what "fast" means exactly, we spot a few interesting issues that arise when conventional time metrics are applied to long-lived asynchronous algorithms. We reveal some gaps in latency claims made in earlier work on snapshot algorithms, which hamper their comparative time-complexity analysis. We then come up with a new unifying time-complexity metric that captures the latency of an operation in an asynchronous, long-lived implementation. This allows us to formally grasp latency improvements of our atomic-snapshot algorithm with respect to the state-of-the-art protocols: optimal latency in fault-free runs without contention, short constant latency in fault-free runs with contention, the worst-case latency proportional to the number of active concurrent failures, and constant amortized latency.
Cite as

João Paulo Bezerra, Luciano Freitas, Petr Kuznetsov, and Matthieu Rambaud. Asynchronous Latency and Fast Atomic Snapshot. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bezerra_et_al:LIPIcs.DISC.2025.15,
  author =	{Bezerra, Jo\~{a}o Paulo and Freitas, Luciano and Kuznetsov, Petr and Rambaud, Matthieu},
  title =	{{Asynchronous Latency and Fast Atomic Snapshot}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{15:1--15:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.15},
  URN =		{urn:nbn:de:0030-drops-248326},
  doi =		{10.4230/LIPIcs.DISC.2025.15},
  annote =	{Keywords: Asynchronous systems, time complexity, atomic snapshot, crash faults}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.8
Auditable Shared Objects: From Registers to Synchronization Primitives

Authors: Hagit Attiya, Antonio Fernández Anta, Alessia Milani, Alexandre Rapetti, and Corentin Travers

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Auditability allows to track operations performed on a shared object, recording who accessed which information. This gives data owners more control on their data. Initially studied in the context of single-writer registers, this work extends the notion of auditability to other shared objects, and studies their properties. We start by moving from single-writer to multi-writer registers, and provide an implementation of an auditable n-writer m-reader read / write register, with O(n+m) step complexity. This implementation uses (m+n)-sliding registers, which have consensus number m+n. We show that this consensus number is necessary. The implementation extends naturally to support an auditable load-linked / store-conditional (LL/SC) shared object. LL/SC is a primitive that supports efficient implementation of many shared objects. Finally, we relate auditable registers to other access control objects, by implementing an anti-flickering deny list from auditable registers.
Cite as

Hagit Attiya, Antonio Fernández Anta, Alessia Milani, Alexandre Rapetti, and Corentin Travers. Auditable Shared Objects: From Registers to Synchronization Primitives. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.DISC.2025.8,
  author =	{Attiya, Hagit and Anta, Antonio Fern\'{a}ndez and Milani, Alessia and Rapetti, Alexandre and Travers, Corentin},
  title =	{{Auditable Shared Objects: From Registers to Synchronization Primitives}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{8:1--8:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.8},
  URN =		{urn:nbn:de:0030-drops-248253},
  doi =		{10.4230/LIPIcs.DISC.2025.8},
  annote =	{Keywords: Auditability, Wait-free implementation, Synchronization power, Distributed objects, Shared memory, LL/SC, Deny List}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.4
AMECOS: A Modular Event-Based Framework for Concurrent Object Specification

Authors: Timothé Albouy, Antonio Fernández Anta, Chryssis Georgiou, Mathieu Gestin, Nicolas Nicolaou, and Junlang Wang

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

Abstract
In this work, we introduce a modular framework for specifying distributed systems that we call AMECOS. Specifically, our framework departs from the traditional use of sequential specification, which presents limitations both on the specification expressiveness and implementation efficiency of inherently concurrent objects, as documented by Castañeda, Rajsbaum and Raynal in CACM 2023. Our framework focuses on the interactions between the various system components, specified as concurrent objects. Interactions are described with sequences of object events. This provides a modular way of specifying distributed systems and separates legality (object semantics) from other issues, such as consistency. We demonstrate the usability of our framework by (i) specifying various well-known concurrent objects, such as registers, shared memory, message-passing, reliable broadcast, and consensus, (ii) providing hierarchies of ordering semantics (namely, consistency hierarchy, memory hierarchy, and reliable broadcast hierarchy), and (iii) presenting a novel axiomatic proof of the impossibility of the well-known Consensus problem.
Cite as

Timothé Albouy, Antonio Fernández Anta, Chryssis Georgiou, Mathieu Gestin, Nicolas Nicolaou, and Junlang Wang. AMECOS: A Modular Event-Based Framework for Concurrent Object Specification. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 4:1-4:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{albouy_et_al:LIPIcs.OPODIS.2024.4,
  author =	{Albouy, Timoth\'{e} and Fern\'{a}ndez Anta, Antonio and Georgiou, Chryssis and Gestin, Mathieu and Nicolaou, Nicolas and Wang, Junlang},
  title =	{{AMECOS: A Modular Event-Based Framework for Concurrent Object Specification}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{4:1--4:29},
  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.4},
  URN =		{urn:nbn:de:0030-drops-225409},
  doi =		{10.4230/LIPIcs.OPODIS.2024.4},
  annote =	{Keywords: Concurrency, Object specification, Consistency conditions, Consensus impossibility}
}
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
Vision
DOI: 10.4230/TGDK.1.1.9
Trust, Accountability, and Autonomy in Knowledge Graph-Based AI for Self-Determination

Authors: Luis-Daniel Ibáñez, John Domingue, Sabrina Kirrane, Oshani Seneviratne, Aisling Third, and Maria-Esther Vidal

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract
Knowledge Graphs (KGs) have emerged as fundamental platforms for powering intelligent decision-making and a wide range of Artificial Intelligence (AI) services across major corporations such as Google, Walmart, and AirBnb. KGs complement Machine Learning (ML) algorithms by providing data context and semantics, thereby enabling further inference and question-answering capabilities. The integration of KGs with neuronal learning (e.g., Large Language Models (LLMs)) is currently a topic of active research, commonly named neuro-symbolic AI. Despite the numerous benefits that can be accomplished with KG-based AI, its growing ubiquity within online services may result in the loss of self-determination for citizens as a fundamental societal issue. The more we rely on these technologies, which are often centralised, the less citizens will be able to determine their own destinies. To counter this threat, AI regulation, such as the European Union (EU) AI Act, is being proposed in certain regions. The regulation sets what technologists need to do, leading to questions concerning How the output of AI systems can be trusted? What is needed to ensure that the data fuelling and the inner workings of these artefacts are transparent? How can AI be made accountable for its decision-making? This paper conceptualises the foundational topics and research pillars to support KG-based AI for self-determination. Drawing upon this conceptual framework, challenges and opportunities for citizen self-determination are illustrated and analysed in a real-world scenario. As a result, we propose a research agenda aimed at accomplishing the recommended objectives.
Cite as

Luis-Daniel Ibáñez, John Domingue, Sabrina Kirrane, Oshani Seneviratne, Aisling Third, and Maria-Esther Vidal. Trust, Accountability, and Autonomy in Knowledge Graph-Based AI for Self-Determination. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 9:1-9:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{ibanez_et_al:TGDK.1.1.9,
  author =	{Ib\'{a}\~{n}ez, Luis-Daniel and Domingue, John and Kirrane, Sabrina and Seneviratne, Oshani and Third, Aisling and Vidal, Maria-Esther},
  title =	{{Trust, Accountability, and Autonomy in Knowledge Graph-Based AI for Self-Determination}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{9:1--9:32},
  ISSN =	{2942-7517},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.9},
  URN =		{urn:nbn:de:0030-drops-194839},
  doi =		{10.4230/TGDK.1.1.9},
  annote =	{Keywords: Trust, Accountability, Autonomy, AI, Knowledge Graphs}
}
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}
}
  • Refine by Type
  • 10 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 4 2025
  • 1 2024
  • 2 2023
  • 1 2021
  • 1 2019
  • Show More...

  • Refine by Author
  • 6 Mostéfaoui, Achour
  • 6 Perrin, Matthieu
  • 2 Raynal, Michel
  • 1 Albouy, Timothé
  • 1 Anta, Antonio Fernández
  • Show More...

  • Refine by Series/Journal
  • 9 LIPIcs
  • 1 TGDK

  • Refine by Classification
  • 5 Theory of computation → Distributed computing models
  • 3 Computer systems organization → Dependable and fault-tolerant systems and networks
  • 3 Theory of computation → Distributed algorithms
  • 2 Software and its engineering → Process synchronization
  • 1 Computer systems organization → Fault-tolerant network topologies
  • Show More...

  • Refine by Keyword
  • 3 Consensus
  • 3 Linearizability
  • 2 Agreement problem
  • 2 Asynchronous system
  • 2 Broadcast abstraction
  • 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