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.
https://hal.inria.fr/hal-01100776
Contributor : Carole Delporte-Gallet <>
Submitted on : Wednesday, January 7, 2015 - 9:47:07 AM Last modification on : Tuesday, December 8, 2020 - 9:44:10 AM