2026-07-21T14:09:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22557 2025-10-02T11:06:14Z ddc:004 open_access

No Symmetric Broadcast Abstraction Characterizes k-Set-Agreement in Message-Passing Systems Gay, Sylvain Mostéfaoui, Achour Perrin, Matthieu 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 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sylvain Gay and Achour Mostéfaoui and Matthieu Perrin 2025 Is Part Of LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2024.21 urn:nbn:de:0030-drops-225573 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.21 eng https://creativecommons.org/licenses/by/4.0/legalcode