License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2017.27
URN: urn:nbn:de:0030-drops-79943
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7994/
Go to the corresponding LIPIcs Volume Portal

Imbs, Damien ; Mostéfaoui, Achour ; Perrin, Matthieu ; Raynal, Michel

Which Broadcast Abstraction Captures k-Set Agreement?

pdf-format:
LIPIcs-DISC-2017-27.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{imbs_et_al:LIPIcs:2017:7994,
  author =	{Damien Imbs and Achour Most{\'e}faoui and Matthieu Perrin and Michel Raynal},
  title =	{{Which Broadcast Abstraction Captures k-Set Agreementl}},
  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 =	{Andr{\'e}a W. Richa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7994},
  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}
}

Keywords: Agreement problem, Antichain, Asynchronous system, Communication abstraction, Consensus, Message-passing system, Partially ordered set, Process crash
Collection: 31st International Symposium on Distributed Computing (DISC 2017)
Issue Date: 2017
Date of publication: 12.10.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI