Search Results

Documents authored by Imbs, Damien

Document
DOI: 10.4230/LIPIcs.OPODIS.2017.9
Progress-Space Tradeoffs in Single-Writer Memory Implementations

Authors: Damien Imbs, Petr Kuznetsov, and Thibault Rieutord

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
Many algorithms designed for shared-memory distributed systems assume the single-writer multi- reader (SWMR) setting where each process is provided with a unique register that can only be written by the process and read by all. In a system where computation is performed by a bounded number n of processes coming from a large (possibly unbounded) set of potential participants, the assumption of an SWMR memory is no longer reasonable. If only a bounded number of multi- writer multi-reader (MWMR) registers are provided, we cannot rely on an a priori assignment of processes to registers. In this setting, implementing an SWMR memory, or equivalently, ensuring stable writes (i.e., every written value persists in the memory), is desirable. In this paper, we propose an SWMR implementation that adapts the number of MWMR registers used to the desired progress condition. For any given k from 1 to n, we present an algorithm that uses n + k − 1 registers to implement a k-lock-free SWMR memory. In the special case of 2-lock-freedom, we also give a matching lower bound of n + 1 registers, which supports our conjecture that the algorithm is space-optimal. Our lower bound holds for the strictly weaker progress condition of 2-obstruction-freedom, which suggests that the space complexity for k-obstruction-free and k-lock-free SWMR implementations might coincide.
Cite as

Damien Imbs, Petr Kuznetsov, and Thibault Rieutord. Progress-Space Tradeoffs in Single-Writer Memory Implementations. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{imbs_et_al:LIPIcs.OPODIS.2017.9,
  author =	{Imbs, Damien and Kuznetsov, Petr and Rieutord, Thibault},
  title =	{{Progress-Space Tradeoffs in Single-Writer Memory Implementations}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.9},
  URN =		{urn:nbn:de:0030-drops-86290},
  doi =		{10.4230/LIPIcs.OPODIS.2017.9},
  annote =	{Keywords: Single-writer memory implementation, comparison-based algorithms, space complexity, progress conditions}
}
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}
}
Document
DOI: 10.4230/DagRep.6.7.31
Topological Methods in Distributed Computing (Dagstuhl Seminar 16282)

Authors: Dmitry Feichtner-Kozlov and Damien Imbs

Published in: Dagstuhl Reports, Volume 6, Issue 7 (2016)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 16282 "Topological Methods in Distributed Computing", which was attended by 22 international researchers, both junior and senior. In the last 10--15 years, there has been an increasing body of work on applications of topology in theoretical distributed computing. This seminar brought together computer scientists working in theoretical distributed computing and mathematicians working in combinatorial topology, leading to interesting new collaborations. This report gathers abstracts of the talks given by the participants and of the group research sessions that happened during the seminar.
Cite as

Dmitry Feichtner-Kozlov and Damien Imbs. Topological Methods in Distributed Computing (Dagstuhl Seminar 16282). In Dagstuhl Reports, Volume 6, Issue 7, pp. 31-41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{feichtnerkozlov_et_al:DagRep.6.7.31,
  author =	{Feichtner-Kozlov, Dmitry and Imbs, Damien},
  title =	{{Topological Methods in Distributed Computing (Dagstuhl Seminar 16282)}},
  pages =	{31--41},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{7},
  editor =	{Feichtner-Kozlov, Dmitry and Imbs, Damien},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.7.31},
  URN =		{urn:nbn:de:0030-drops-67614},
  doi =		{10.4230/DagRep.6.7.31},
  annote =	{Keywords: combinatorial topology, concurrency, distributed protocols, shared-memory communication, solvability}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2015.26
The Synchronization Power of Atomic Bitwise Operations

Authors: Damien Imbs

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
In a distributed system, processes must reach a certain level of synchronization to solve a common problem. The strongest form of synchronization can be reached through consensus: all the processes must agree on a common value that has been proposed by one of them. Consensus is universal in shared memory systems: any type of shared object can be implemented using it. Unfortunately, consensus is impossible to solve using only shared registers when processes can crash. To circumvent this impossibility, one can use stronger objects, for example Test&Set or Compare&Swap. The synchronization power of these objects can be measured using the concept of Consensus Number: the maximum number of processes for which they can solve consensus in a crash-prone system. Bitwise AND, OR and XOR operations are very widely used, but have received little attention in the distributed setting. Because bitwise operations are available in most modern processors, they can constitute a valuable tool for synchronization in distributed systems. It is then natural to consider the level of synchronization that these operations can achieve. This paper introduces shared AND/OR and AND/OR/XOR registers. A shared AND/OR register consists of an array of x bits and offers three atomic operations: AND and OR operations, which take an array of x bits as parameter and change the state of the register by applying the corresponding bitwise operation, and a read operation which returns the content of the array. A shared AND/OR/XOR register additionally offers a XOR operation. We show that shared AND/OR registers of x bits have consensus number lfloor (x+1)/2 rfloor, by presenting an algorithm that solves consensus using these registers, and by proving that consensus cannot be solved for n processes using AND/OR registers that have strictly less than 2n-1 bits. We then show that shared AND/OR/XOR registers of x bits have consensus number x using a similar technique.
Cite as

Damien Imbs. The Synchronization Power of Atomic Bitwise Operations. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{imbs:LIPIcs.OPODIS.2015.26,
  author =	{Imbs, Damien},
  title =	{{The Synchronization Power of Atomic Bitwise Operations}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.26},
  URN =		{urn:nbn:de:0030-drops-66151},
  doi =		{10.4230/LIPIcs.OPODIS.2015.26},
  annote =	{Keywords: Asynchronous systems, Binary operations, Consensus, Consensus number, Read/write shared memory, Shared objects, Synchronization, Wait-freedom}
}
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