Bully algorithm: Difference between revisions

Revision as of 17:29, 5 December 2015

Revision as of 05:15, 19 March 2016

Line 7:

The '''bully algorithm''' is a programming mechanism that applies a hierarchy to nodes on a system, making a process coordinator or slave.

This is used as a method in [[distributed computing]] for dynamically electing a [[Distributed Computingcomputing#Coordinator Electionelection|coordinator]] by process ID number. The process with the highest process ID number is selected as the [[Distributed Computingcomputing#Coordinator Election|coordinator]].

==Assumptions==

Line 22:

==Component calls==

These are the Bullybully-algorithm components:

* Election Message: Sent to announce faster election

Line 31:

* Assumes that system is synchronous

* Uses timeout to detect process failure/crash

* Each processor knows which processor has the higher identifier number and communicates with that<ref>Jean Dollimore, Tim Kindberg, George F. Coulouris, "Distributed systems : concepts and design (Third Edition)," in ''Distributed systems : concepts and design (Third Edition)''. Addison-WesleyAddison–Wesley, 2003.</ref>

==Bully algorithm structure==

Line 41:

# If P hears from a process with a higher ID, P waits a certain amount of time for any process with a higher ID to broadcast itself as the leader. If it does not receive this message in time, it re-broadcasts the election message.

# 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 ==

*[[Distributed Computingcomputing#Coordinator election]]

*[[Chang and Roberts algorithm]]

Line 50:

{{reflist}}

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

* Hector Garcia-Molina, Elections in a Distributed Computing System, IEEE Transactions on Computers, Vol. C-31, No. 1, January (1982) 48-5948–59

* L. Lamport, R. Shostak, and M. Pease, [http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf "The Byzantine Generals Problem"] ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, July 1982.

[[Category:Distributed algorithms]]