A Failure Detector for k-Set Agreement in Asynchronous Dynamic Systems

Abstract : The k-set agreement problem is a generalization of the consensus problem where processes can decide up to k different values. Very few papers have tackled this problem in dynamic networks, and to the best of our knowledge, every algorithm proposed so far for k-set agreement in dynamic networks assumed synchronous communications. Exploiting the formalism of the Time-Varying Graph model, this paper proposes a new failure detector Sigma-bottom-k, based on Sigma-k and Sigma-bottom, for solving k-set agreement in asynchronous dynamic networks. We present two algorithms that implement this new failure detector, making assumptions on the number of process failures and graph connectivity. We also provide an algorithm for solving k-set agreement using Sigma-bottom-z , under an assumption on the relative values of k and z.
Type de document :
Rapport
[Research Report] RR-8727, UPMC Sorbonne Universités/CNRS/Inria - EPI REGAL; INRIA. 2015
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01151739
Contributeur : Pierre Sens <>
Soumis le : jeudi 2 juillet 2015 - 15:39:55
Dernière modification le : jeudi 11 janvier 2018 - 06:20:06
Document(s) archivé(s) le : mardi 25 avril 2017 - 22:24:43

Fichier

Main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01151739, version 2

Citation

Denis Jeanneau, Thibault Rieutord, Luciana Arantes, Pierre Sens. A Failure Detector for k-Set Agreement in Asynchronous Dynamic Systems. [Research Report] RR-8727, UPMC Sorbonne Universités/CNRS/Inria - EPI REGAL; INRIA. 2015. 〈hal-01151739v2〉

Partager

Métriques

Consultations de la notice

365

Téléchargements de fichiers

127