Election in unidirectional rings with homonyms - Archive ouverte HAL Access content directly
Journal Articles Journal of Parallel and Distributed Computing Year : 2020

Election in unidirectional rings with homonyms

(1) , (2) , (1) , (1, 3) , (2)
Karine Altisen
  • Function : Author
  • PersonId : 1055858
Ajoy K Datta
  • Function : Author
  • PersonId : 923792
Stéphane Devismes


We study leader election in unidirectional rings of homonyms that have no a priori knowledge of the number of processes. In this context, we show that there exists no algorithm that solves the process-terminating leader election problem for the class of asymmetrically labeled unidirectional rings. More precisely, we prove that there is no process-terminating leader election algorithm even for the subclass of unidirectional rings where at least one label is unique. Message-terminating leader election is also impossible for the class of unidirectional rings where only a bound on multiplicity is known. However, we show that the processterminating leader election is possible for two particular subclasses of asymmetrically labeled unidirectional rings where the multiplicity is bounded. We propose three efficient algorithms and analyze their complexities. We also give some non-trivial lower bounds.
Fichier principal
Vignette du fichier
JPDC20.pdf (634.76 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03452675 , version 1 (27-11-2021)


Attribution - NonCommercial - NoDerivatives - CC BY 4.0



Karine Altisen, Ajoy K Datta, Stéphane Devismes, Anaïs Durand, Lawrence L Larmore. Election in unidirectional rings with homonyms. Journal of Parallel and Distributed Computing, 2020, 146, pp.79-95. ⟨10.1016/j.jpdc.2020.08.004⟩. ⟨hal-03452675⟩
25 View
32 Download



Gmail Facebook Twitter LinkedIn More