Leader Election in Rings with Homonyms.

Carole Delporte-Gallet 1, 2 Hugues Fauconnier 1, 2 Hung Tran-The 1, 2
2 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Abstract : Considering the case of homonyms processes (some processes may share the same identifier) on a ring, we give here a necessary and sufficient condition on the number of identifiers to enable leader election. We prove that if l is the number of identifiers then message-terminating election is possible if and only if l is greater than the greatest proper divisor of the ring size even if the processes do not know the ring size. If the ring size is known, we propose a process-terminating algorithm exchanging O(n log(n)) messages that is optimal.
keyword : Leader
Type de document :
Communication dans un congrès
NETYS, May 2014, Marrackech, Morocco. Springer, NETYS, pp.9-24, 〈10.1007/978-3-319-09581-3 2〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01100776
Contributeur : Carole Delporte-Gallet <>
Soumis le : mercredi 7 janvier 2015 - 09:47:07
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Identifiants

Collections

Citation

Carole Delporte-Gallet, Hugues Fauconnier, Hung Tran-The. Leader Election in Rings with Homonyms.. NETYS, May 2014, Marrackech, Morocco. Springer, NETYS, pp.9-24, 〈10.1007/978-3-319-09581-3 2〉. 〈hal-01100776〉

Partager

Métriques

Consultations de la notice

198