Title

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

UNLV article access

Share

COinS