Jump to content

Bully algorithm

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Person54 (talk | contribs) at 14:17, 18 May 2017 (→Algorithm). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In distributed computing, the bully algorithm is a method for dynamically electing a coordinator or leader by process ID number. The process with the highest process ID number is selected as the coordinator.

Assumptions

The algorithm assumes that:[1]

  • the system is synchronous and timeouts identify process failure.
  • processes may crash during execution of the algorithm.
  • message delivery between processes is reliable.
  • process ids are known.

Algorithm

The algorithm uses the following message types:

  • Election Message: Sent to announce faster election
  • Answer (Alive) Message: Respond to the election message
  • Coordinator (Victory) Message: Sent to announce the identity of the elected process

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:

  1. P broadcasts an Election message (inquiry) to all other processes with higher process IDs.
  2. If P receives no Answer from a process with a higher process ID, then it broadcasts a Victory and becomes the

Coordinator.

  1. If P receives an Answer from a process with a higher ID, P waits a certain amount of time for another process with a higher ID to broadcast a Victory message. If it does not receive a Victory message in time, it re-broadcasts the Election message.
  2. If P gets an Election message (inquiry) from another process with a lower ID it sends an Answer message back and starts a new election.

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

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–Wesley, 2003.
  • Witchel, Emmett (2005). "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–59
  • L. Lamport, R. Shostak, and M. Pease, "The Byzantine Generals Problem" ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, July 1982.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Bully_algorithm&oldid=781005268"