2026-07-17T14:13:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7994 2024-03-06T10:41:40Z ddc:004 open_access

Which Broadcast Abstraction Captures k-Set Agreement? Imbs, Damien Mostéfaoui, Achour Perrin, Matthieu Raynal, Michel Agreement problem Antichain Asynchronous system Communication abstraction Consensus Message-passing system Partially ordered set Process crash 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Damien Imbs and Achour Mostéfaoui and Matthieu Perrin and Michel Raynal 2017 Is Part Of LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2017.27 urn:nbn:de:0030-drops-79943 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.27 eng https://creativecommons.org/licenses/by/3.0/legalcode