Election in Unidirectional Rings with Homonyms

Document Type

Article

Publication Date

8-19-2020

Publication Title

Journal of Parallel and Distributed Computing

Volume

146

First page number:

79

Last page number:

95

Abstract

We study leader election in unidirectional rings of homonyms that have no a priori knowledge of the number of processes. In this context, we show that there exists no algorithm that solves the process-terminating leader election problem for the class of asymmetrically labeled unidirectional rings. More precisely, we prove that there is no process-terminating leader election algorithm even for the subclass of unidirectional rings where at least one label is unique. Message-terminating leader election is also impossible for the class of unidirectional rings where only a bound on multiplicity is known. However, we show that the process-terminating leader election is possible for two particular subclasses of asymmetrically labeled unidirectional rings where the multiplicity is bounded. We propose three efficient algorithms and analyze their complexities. We also give some non-trivial lower bounds.

Keywords

Leader election; Homonyms; Multiplicity; Unidirectional rings

Language

English

UNLV article access

Find in your library

Share

COinS