Résolution efficace du consensus généralisé dans les systèmes répartis par passage de messages

Pierre Sutra 1, 2 Marc Shapiro 1, 2
1 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Résumé : La construction d'un objet partagé entre plusieurs processus nécessite la résolution du consensus. De ce fait, la résolution du consensus est un sujet central et récurrent dans le domaine des systèmes répartis. Dans un article récent, L. Lamport suggère de prendre en compte la commutativité des accès concurrents à un objet partagé afin d'améliorer la vitesse de résolution du consensus. Cet article introduit notamment Generalized Paxos, un algorithme qui résout le consensus dans les systèmes répartis par passage de messages en deux étapes de communication si les accès concurrents sont commutatifs ou spontanément ordonnés par le réseau. Toutefois, si une collision se produit, c'est à dire que deux accès concurrents et non-commutatifs ont lieu, Generalized Paxos exécute quatre étapes de communication supplémentaires. L'algorithme devient alors moins performant que les solutions classiques. Dans cet article nous décrivons une nouvelle solution au consensus généralisé: FGGC. FGGC est optimal au regard des fautes et de la vitesse d'exécution car: (i) pour tolérer f pannes franches, FGGC utilise 2f+1 processus, (ii) si toutes les commandes sont commutatives, ou spontanément ordonnées par le réseau, FGGC résout le consensus en deux étapes de communication, (iii) les collisions sont résolues en une seule étape de communication, et (iv) FGGC utilise seulement f+1 processus pour progresser.
Type de document :
Communication dans un congrès
Ducourthial, Bertrand and Felber, Pascal. ALGOTEL 2011 - 13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications, May 2011, Cap Estérel, France. 2011
Liste complète des métadonnées

https://hal.inria.fr/inria-00586591
Contributeur : Pierre Sutra <>
Soumis le : vendredi 22 avril 2011 - 21:05:24
Dernière modification le : vendredi 25 mai 2018 - 12:02:03
Document(s) archivé(s) le : jeudi 30 mars 2017 - 09:48:32

Fichier

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

Identifiants

  • HAL Id : inria-00586591, version 2

Collections

Citation

Pierre Sutra, Marc Shapiro. Résolution efficace du consensus généralisé dans les systèmes répartis par passage de messages. Ducourthial, Bertrand and Felber, Pascal. ALGOTEL 2011 - 13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications, May 2011, Cap Estérel, France. 2011. 〈inria-00586591v2〉

Partager

Métriques

Consultations de la notice

398

Téléchargements de fichiers

157