Eventual Leader Election with Weak Assumptions on Initial Knowledge, Communication Reliability, and Synchrony

Antonio Fernández (1) , Ernesto Jiménez (2) , Michel Raynal (3)

1 LADyR - Laboratorio de Algoritmia Distribuida y Redes
2 EUI - Escuela Universidaria de Informática
3 IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires

This report considers the eventual leader election problem in asynchronous message-passing systems where an arbitrary number $t$ of processes can crash ($t < n$, where $n$ is the total number of processes). It considers weak assumptions both on the initial knowledge of the processes and on the network behavior. More precisely, initially, a process knows only its identity and the fact that the process identities are different and totally ordered (it knows neither $n$ nor $t$). Two eventual leader election protocols and a lower bound are presented. The first protocol assumes that a process also knows the lower bound $\alpha$ on the number of processes that do not crash. This protocol requires the following behavioral properties from the underlying network: the graph made up of the correct processes and fair lossy links is strongly connected, and there is a correct process connected to $t-f$ other correct processes (where $f$ is the actual number of crashes in the considered run) through eventually timely paths (paths made up of correct processes and eventually timely links). This protocol is not communication-efficient in the sense that each correct process has to send messages forever. The second protocol is communication-efficient: after some time, only the final common leader has to send messages forever. This protocol does not require the processes to know $\alpha$, but requires stronger properties from the underlying network: each pair of correct processes has to be connected by fair lossy links (one in each direction), and there is a correct process whose output links to the rest of correct processes have to be eventually timely. The lower bound result shows that this a necessary requirement. This protocol enjoys also the property that each messsage is made up of several fields, each of which taking values from a finite domain. \\ Ce rapport présente deux protocoles qui élisent un leader inéluctable dans un système réparti défini par des hypothèses faibles sur connaissance initiale des processus, le synchronisme et la fiabilité des communcations. Un théorème d'impossibilité est également présenté.

Mots clés: Asynchronous message-passing system; Eventually timely link; Fair lossy link; Eventual leader election; Failure detector; Message loss; Network behavior; Omega leader oracle; Process crash; Process initial knowledge \\ Systèmes répartis asynchrones; Tolérance aux fautes; Crash de processus; Oracle oméga; canal équitable; Perte de message; Détection de fautes; Leader inéluctable

Domaines: Réseaux et télécommunications [cs.NI]

Antonio Fernández, Ernesto Jiménez, Michel Raynal. Eventual Leader Election with Weak Assumptions on Initial Knowledge, Communication Reliability, and Synchrony. [Research Report] PI 1770, 2005, pp.19. ⟨inria-00000913⟩