From an intermittent rotating star to a leader

Abstract : Ce rapport présente un protocole d'élection d'un leader inéluctable dans un système réparti défini par des hypothèses de synchronisme très faible. \\Considering an asynchronous system made up of n processes and where up to t of them can crash, finding the weakest assumptions that such a system has to satisfy for a common leader being eventually elected, is one of the holy grail quests of fault-tolerant asynchronous computing. This paper is a step in such a quest. It has two main contributions. First, it proposes an asynchronous system model, in which an eventual leader can be elected, that is weaker and more general than previous models. This model is captured by the notion of intermittent rotating t-star. An x-star is a set of x+1 processes: a process p(the center of the star) plus a set of x processes (the points of the star). Intuitively, assuming logical times rn (round numbers), the intermittent rotating t-star assumption means that there are a process p, a subset of the round numbers rn, and associated sets Q(rn) such that each set {p} U Q(rn) is a t-star centered at p, and each process of Q(rn) receives from p a message tagged rn in a timely manner or among the first (n-t) messages tagged rn it ever receives. The star is called t-rotating because the set Q(rn) is allowed to change with rn. It is called intermittent because the star can disappear during finite periods. This assumption, not only combines, but generalizes several synchrony and time-free assumptions that have been previously proposed to elect an eventual leader (e.g., eventual t-source, eventual t-moving source, message pattern assumption). Each of these assumptions appears as a particular case of the intermittent rotating t-star} assumption. The second contribution of the paper is an algorithm that eventually elects a common leader in any system that satisfies the intermittent rotating t-star} assumption. That algorithm enjoys several noteworthy properties. From a design point of view, it is simple. From a cost point of view, only the round numbers can increase without bound. This means that, be the execution finite or infinite, be links timely or not (or have the corresponding sender crashed or not), all the other local variables (including the timers) and message fields have a finite domain.
Type de document :
[Research Report] PI 1810, 2006, pp.19
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger
Contributeur : Anne Jaigu <>
Soumis le : vendredi 25 août 2006 - 13:45:36
Dernière modification le : jeudi 11 janvier 2018 - 06:20:08
Document(s) archivé(s) le : lundi 5 avril 2010 - 23:16:04



  • HAL Id : inria-00089975, version 1



Antonio Fernández, Michel Raynal. From an intermittent rotating star to a leader. [Research Report] PI 1810, 2006, pp.19. 〈inria-00089975〉



Consultations de la notice


Téléchargements de fichiers