K-set agreement bounds in round-based models through combinatorial topology - Assistance à la Certification d’Applications DIstribuées et Embarquées Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

K-set agreement bounds in round-based models through combinatorial topology

Résumé

Round-based models are the main message-passing models; combinatorial topology applied to distributed computing provide sweeping results like general lower bounds. We combine both to study the computability of k set-agreement. Among all the possible round-based models, we consider oblivious ones, where the constraints are given only round per round by a set of allowed graphs. And among oblivious models, we focus on closed-above ones, that is models where the set of possible graphs is a union of above-closure of graphs. These capture intuitively the underlying structure required by some communication model, like containing a ring. We then derive lower bounds and upper bounds in one round for k set-agreement, such that these bounds are proved using combinatorial topology but stated only in terms of graph properties. These bounds extend to multiple rounds when limiting our algorithms to oblivious ones, that is ones that recall only pairs of process and initial value.
Fichier principal
Vignette du fichier
shimi_26404.pdf (380.83 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02950742 , version 1 (28-09-2020)

Identifiants

  • HAL Id : hal-02950742 , version 1
  • OATAO : 26404

Citer

Adam Shimi, Armando Castañeda. K-set agreement bounds in round-based models through combinatorial topology. 39th ACM Symposium on Principles of Distributed Computing (PODC 2020), Aug 2020, Salerno, Italy. pp.395-404. ⟨hal-02950742⟩
80 Consultations
67 Téléchargements

Partager

Gmail Facebook X LinkedIn More