Bully algorithm: Difference between revisions

Revision as of 13:06, 9 December 2019

Revision as of 23:54, 24 December 2019

Line 17:

* Coordinator (Victory) Message: Sent by winner of the election to announce victory.

When a process {{var|P}} recovers from failure, or the failure detector indicates that the current coordinator has failed, {{var|P}} performs the following actions:

# If {{var|P}} has the highest process ID, it sends a Victory message to all other processes and becomes the new Coordinator. Otherwise, {{var|P}} broadcasts an Election message to all other processes with higher process IDs than itself.

# If {{var|P}} receives no Answer after sending an Election message, then it broadcasts a Victory message to all other processes and becomes the Coordinator.

# If {{var|P}} receives an Answer from a process with a higher ID, it sends no further messages for this election and waits for a Victory message. (If there is no Victory message after a period of time, it restarts the process at the beginning.)

# If {{var|P}} receives an Election message from another process with a lower ID it sends an Answer message back and starts the election process at the beginning, by sending an Election message to higher-numbered processes.

# If {{var|P}} receives a Coordinator message, it treats the sender as the coordinator.

===Analysis===

====Safety====

The safety property expected of leader election protocols is that every non-faulty process either elects a process {{var|Q}}, or elects none at all. Note that all processes that elect a leader must decide on the same process {{var|Q}} as the leader. The Bully algorithm satisfies this property (under the system model specified), and at no point in time is it possible for two processes in the group to have

a conflicting view of who the leader is, except during an election. This is true because if it weren't, there are two processes {{var|X}} and {{var|Y}} such that both sent the Coordinator (victory) message to the group. This means {{var|X}} and {{var|Y}} must also have sent each other victory messages. But this cannot happen, since before sending the victory message, Election messages would have been exchanged between the two, and the process with a lower process ID among the two would never send out victory messages. We have a contradiction, and hence our initial assumption that there are two leaders in the system at any given time is false, and that shows that the bully algorithm is safe.

====Liveness====

Line 35:

====Network bandwidth utilization====

Assuming that the bully algorithm messages are of a fixed (known, invariant) sizes, the most number of messages are exchanged in the group when the process with the lowest ID initiates an election. This process sends (N-1N−1) Election messages, the next higher ID sends (N-2N−2) messages, and so on, resulting in <math>\Theta\left(N^2\right)</math> election messages. There are also the <math>\Theta\left(N^2\right)</math> Alive messages, and <math>\Theta\left(N\right)</math> co-ordinator messages, thus making the overall number messages exchanged in the worst case be <math>\Theta\left(N^2\right)</math>.

== See also ==