Leader Election in Distributed Systems with Crash Failures
Scott D. Stoller · 1999
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. Keywords: leader election, synchronous, asynchronous, crash failures, failure detector 1 Introduction In a classic paper, Garcia-Molina specifies the leader election problem for synch...