The Bully Algorithm was devised by Garcia-Molina in 1982. When a process notices that the coordinator is no longer responding to requests, it initiates an election. Process P, holds an election as follows:

1) P sends an ELECTION message to all processes with higher numbers.

2) If no one responds, P wins the election and becomes coordinator.

3) If one of the higher-ups answers, it takes over. P's job is done.

At any moment, a process can get an ELECTION message from one of its lower-numbered colleagues. When such a message arrives, the receiver sends an OK message back to the sender to indicate that it is alive and will take over. The receiver then holds an election, unless it is already holding one. Eventually, all processes give up but one, and that one is the new coordinator. It announces its victory by sending all processes a message telling them that starting immediately it is the new coordinator.

If a process that was previously down comes back up, it holds an election. If it happens to be the highest-numbered process currently running, it will win the election and will take over the coordinator's job. Thus the biggest guy in town always wins, hence the name "Bully Algorithm".

The workbench displays four processes. There are two queues associated with each process: a queue of requests received from other processes and a queue of requests waiting for an acknowledgement from other processes. Processes are color-coded as follows: red stands for an alive non-coordinator process, purple indicates a coordinator, and gray represents a process that is down. Every non-coordinator process sends requests (circles) to the coordinator and waits for an acknowledgement before sending the next request. Acknowledgement messages are indicated by circles within rectangles. If the acknowledgement does not arrive in a given timeout, the process starts an election by sending ELECTION messages (bars).

The simulation can be controlled on a step-by-step basis by pushing the buttons that correspond to each process. These buttons can cause the individual processes to send requests, fail, or recover. The simulation can also be run in the animation mode in which processes operate concurrently and go up and down randomly. The speed of the animation can be controlled by the "Slow Ratio" slide at the top of the demonstration. Moving the slide to the right will slow down the animiation.

Workbench