Randomized leader election

Get BibTex-formatted data

Author

Murali Krishna Ramanathan, Ronaldo A. Ferreira, Suresh Jagannathan, Ananth Grama, Wojciech Szpankowski

Entry type

article

Abstract

We present an efficient randomized algorithm for leader election in large-scale distributed systems. The proposed algorithm is optimal in message complexity (O(n) for a set of n total processes), has round complexity logarithmic in the number of processes in the system, and provides high probabilistic guarantees on the election of a unique leader. The algorithm relies on a balls and bins abstraction and works in two phases. The main novelty of the work is in the first phase where the number of contending processes is reduced in a controlled manner. Probabilistic quorums are used to determine a winner in the second phase. We discuss, in detail, the synchronous version of the algorithm, provide extensions to an asynchronous version and examine the impact of failures.

Date

2007 – 04

URL

http://scholar.google.com/scho ... 008&start=40&sa=N

Journal

Distributed Computing

Key alpha

Grama

Pages

403-418

Publisher

Springer Berlin / Heidelberg

Affiliation

Purdue University

Publication Date

2007-04-00

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Article{ Grama,
	title = "Randomized leader election",
	author = "Murali Krishna Ramanathan, Ronaldo A. Ferreira, Suresh Jagannathan, Ananth Grama, Wojciech Szpankowski",
	year = "2007",
	month = "04",
	journal = "Distributed Computing",
	pages = "403-418",
	publisher = "Springer Berlin / Heidelberg",
	abstract = "We present an efficient randomized algorithm for leader election in large-scale distributed systems. The proposed algorithm is optimal in message complexity (O(n) for a set of n total processes), has round complexity logarithmic in the number of processes in the system, and provides high probabilistic guarantees on the election of a unique leader. The algorithm relies on a balls and bins abstraction and works in two phases. The main novelty of the work is in the first phase where the number of contending processes is reduced in a controlled manner. Probabilistic quorums are used to determine a winner in the second phase. We discuss, in detail, the synchronous version of the algorithm, provide extensions to an asynchronous version and examine the impact of failures.",
	affiliation = "Purdue University",
	url = "http://scholar.google.com/scholar?q=Purdue+University+author:Grama&hl=en&lr=&as_ylo=1999&as_yhi=2008&start=40&sa=N",
}