A Failure Detector for k-Set Agreement in 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 or made strong failure pattern assumptions. Exploiting the formalism of the Time-Varying Graph model, this paper proposes a new quorum-based failure detector for solving k-set agreement in dynamic networks with asynchronous communications. We present two algorithms that implement this new failure detector using graph connectivity and message pattern assumptions. We also provide an algorithm for solving k-set agreement using our new failure detector.
Type de document :
Communication dans un congrès
NCA 2015 - 14th IEEE International Symposium on Network Computing and Applications, Sep 2015, Cambridge, United States. IEEE, pp.176-183, 〈10.1109/NCA.2015.45〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01250233
Contributeur : Pierre Sens <>
Soumis le : lundi 4 janvier 2016 - 14:54:18
Dernière modification le : samedi 24 novembre 2018 - 01:27:16

Identifiants

Citation

Denis Jeanneau, Thibault Rieutord, Luciana Arantes, Pierre Sens. A Failure Detector for k-Set Agreement in Dynamic Systems. NCA 2015 - 14th IEEE International Symposium on Network Computing and Applications, Sep 2015, Cambridge, United States. IEEE, pp.176-183, 〈10.1109/NCA.2015.45〉. 〈hal-01250233〉

Partager

Métriques

Consultations de la notice

143