Leader Election in Asymmetric Labeled Unidirectional Rings
Document Type
Conference Proceeding
Publication Date
5-1-2017
Publication Title
2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
First page number:
182
Last page number:
191
Abstract
We study (deterministic) leader election in unidirectional rings of homonym processes that have no a priori knowledge on the number of processes. In this context, we show that there is no algorithm that solves process-terminating leader election for the class of asymmetric labeled rings. In particular, there is no process-terminating leader election algorithm in rings in which at least one label is unique. However, we show that process-terminating leader election is possible for the subclass of asymmetric rings, where multiplicity is bounded. We confirm this positive results by proposing two algorithms, which achieve the classical trade-off between time and space.
Keywords
Leader Election, Homonym Processes, Multiplicity, Unidirectional Rings.
Language
eng
Repository Citation
Altisen, K.,
Datta, A. K.,
Devismes, S.,
Durand, A.,
Larmore, L. L.
(2017).
Leader Election in Asymmetric Labeled Unidirectional Rings.
2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
182-191.
http://dx.doi.org/10.1109/IPDPS.2017.23