Leader Election in Distributed Systems with Crash Failures
Abstract:
Leader election is an important problem in distributed computing.
Garcia-Molina's Bully Algorithm is a classic solution to leader election
in synchronous systems with crash failures. This paper shows that the
Bully Algorithm can be easily adapted for use in asynchronous systems.
First, we re-write the Bully Algorithm to use a failure detector,
instead of explicit time-outs; this yields a modular solution to leader
election in synchronous systems. Second, we show that minor
modifications to that algorithm yield a simple and efficient solution to
leader election in asynchronous systems with crash failures. We point
out a flaw in Garcia-Molina's specification of leader election in
asynchronous systems, propose a revised specification, and show that the
modified Bully Algorithm satisfies this specification.
BibTeX
PDF
Scott Stoller's Home Page