Solving k-Set Agreement Using Failure Detectors in Unknown Dynamic Networks

Abstract : The failure detector abstraction has been used to solve agreement problems in asynchronous systems prone to crash failures, but so far it has mostly been used in static and complete networks. This paper aims to adapt existing failure detectors in order to solve agreement problems in unknown, dynamic systems. We are specifically interested in the k-set agreement problem. The problem of k-set agreement is a generalization of consensus where processes can decide up to k different values. Although some solutions to this problem have been proposed in dynamic networks, they rely on communication synchrony or make strong assumptions on the number of process failures. In this paper we consider unknown dynamic systems modeled using the formalism of Time-Varying Graphs, and extend the definition of the existing ΠΣx,y failure detector to obtain the ΠΣ ⊥,x,y failure detector, which is sufficient to solve k-set agreement in our model. We then provide an implementation of this new failure detector using connectivity and message pattern assumptions. Finally, we present an algorithm using ΠΣ ⊥,x,y to solve k-set agreement.
Type de document :
Article dans une revue
IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 2016
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01354864
Contributeur : Pierre Sens <>
Soumis le : vendredi 19 août 2016 - 17:45:27
Dernière modification le : vendredi 25 mai 2018 - 12:02:04
Document(s) archivé(s) le : dimanche 20 novembre 2016 - 10:47:08

Fichier

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

Identifiants

  • HAL Id : hal-01354864, version 1

Collections

Citation

Denis Jeanneau, Thibault Rieutord, Luciana Arantes, Pierre Sens. Solving k-Set Agreement Using Failure Detectors in Unknown Dynamic Networks. IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 2016. 〈hal-01354864〉

Partager

Métriques

Consultations de la notice

299

Téléchargements de fichiers

106