Leader Election : from higham-przytycka's algorithm to a gracefully degrading algorithm

Abstract : The leader election problem consists in selecting a process (called leader) in a group of processes. Several leader election algorithms have been proposed in the past for ring networks, tree networks, fully connected networks or regular networks (such as tori and hypercubes). As far as ring networks are concerned, it has been shown that the number of messages that processes have to exchange to elect a leader is (n log n). The algorithm proposed by Higham and Przytycka is the best leader algorithm known so far for ring networks in terms of message complexity, which is 1.271 n log n + O(n). This algorithm uses round numbers and assumes that all processes start with the same round number. More precisely, when round numbers are not initially equal, the algorithm has runs that do not terminate. This paper presents an algorithm, based on Higham-Przytycka's technique, which allows processes to start with different round numbers. This extension is motivated by fault-tolerance with respect to initial values. While the algorithm always terminates, its message complexity is optimal, i.e., O(n log n), when the processes start with the same round number and increases up to O(n2) when all processes start with different round number values. We call graceful degradation this additional property that combines fault-tolerance (with respect to initial values) and efficiency.
Type de document :
[Research Report] PI-1980, 2011, pp.9
Liste complète des métadonnées

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

Contributeur : Ist Rennes <>
Soumis le : lundi 4 juillet 2011 - 15:00:23
Dernière modification le : vendredi 16 novembre 2018 - 01:40:21
Document(s) archivé(s) le : lundi 12 novembre 2012 - 10:00:16


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00605799, version 1


Itziar Arrieta, Federico Fariña, José De Mendívil, Michel Raynal. Leader Election : from higham-przytycka's algorithm to a gracefully degrading algorithm. [Research Report] PI-1980, 2011, pp.9. 〈inria-00605799〉



Consultations de la notice


Téléchargements de fichiers