Name
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1109/IPDPS.2017.23 | 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS) |
Keywords | Field | DocType |
Leader Election,Homonym Processes,Multiplicity,Unidirectional Rings | Leader election,Algorithm design,Voting,Upper and lower bounds,Computer science,A priori and a posteriori,Distributed algorithm,Time complexity,Bounded function,Distributed computing | Conference |
ISSN | ISBN | Citations |
1530-2075 | 978-1-5386-3915-3 | 1 |
PageRank | References | Authors |
0.35 | 4 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Karine Altisen | 1 | 165 | 15.03 |
| Ajoy K. Datta | 2 | 369 | 35.83 |
| Stéphane Devismes | 3 | 192 | 25.74 |
| Anaïs Durand | 4 | 10 | 4.29 |
| Lawrence L. Larmore | 5 | 859 | 109.15 |