Bully algorithm: Difference between revisions

Revision as of 08:51, 11 November 2011

Revision as of 13:08, 24 November 2011

Line 1:

The '''bully algorithm''' is a method in [[distributed computing]] for dynamically selecting a coordinator by process ID number.

Assumptions

* The system is synchronous and uses timeout for identifing process failure

Message types - Election Message : Sent to announce the election

* Answer Message : Respond to the election message

* Cordinator message: sent to announce the identity elected process

Compare with Ring algorithm

* Assumes that system is synchorinous

* Uses time-out to detect process failure/crash

* Each processor knows which processor has the higher identifier number and communicates with that [1]

When a process P determines that the current coordinator is down because of message timeouts or failure of the coordinator to initiate a handshake, it performs the following sequence of actions:

Line 8 ⟶ 19:

# If P gets an election message (inquiry) from another process with a lower ID it sends an "I am alive" message back and starts new elections.

Note that if P receives a victory message from a process with a lower ID number, it immediately initiates a new election. This is how the algorithm gets its name - a process with a higher ID number will bully a lower ID process out of the coordinator position as soon as it comes online.

== See also ==

*[[Leader election]]

Line 14 ⟶ 27:

==References==

[1] Jean Dollimore, Tim Kindberg George F. Coulouris, "Distributed systems : concepts and design (Third Edition)," in Distributed systems : concepts and design (Third Edition).: Addison-wesly , 2003.

* Witchel, Emmett (2005). [http://www.cs.utexas.edu/users/witchel/372/lectures/25.DistributedCoordination.ppt "Distributed Coordination"]. Retrieved May 4, 2005.