No Broadcast Abstraction Characterizes k-Set-Agreement in Message-Passing Systems (Extended Version)
Résumé
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 introduction of two new symmetry properties: compositionality and content-neutrality, inspired by the principle of network neutrality. Such clarity in definition is essential for this paper's scope, as it aims not to characterize the computing power of a specific broadcast abstraction, but rather to demonstrate the nonexistence of a broadcast abstraction with certain characteristics. Hence, delineating the realm of ``meaningful'' broadcast abstractions becomes essential. 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
Origine : Fichiers produits par l'(les) auteur(s)
Matthieu Perrin : Connectez-vous pour contacter le contributeur
https://hal.science/hal-04571653
Soumis le : mercredi 8 mai 2024-12:53:23
Dernière modification le : dimanche 12 mai 2024-03:15:49
Dates et versions
Identifiants
- HAL Id : hal-04571653 , version 1
Citer
Sylvain Gay, Achour Mostefaoui, Matthieu Perrin. No Broadcast Abstraction Characterizes k-Set-Agreement in Message-Passing Systems (Extended Version). 2024. ⟨hal-04571653⟩
Collections
0
Consultations
0
Téléchargements