Content deleted Content added
Fix broken coordinator link |
→Algorithm: lx |
||
Line 12:
==Algorithm==
The [[algorithm]] uses the following message types:
* Election Message: Sent to announce election.
* Answer (Alive) Message: Responds to the Election message.
* Coordinator (Victory) Message: Sent by winner of the election to announce victory.
When a [[computing process|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.
Line 32:
====Liveness====
[[Liveness]] is also guaranteed in the [[synchronous]], crash-recovery model. Consider the would-be leader failing after sending an Answer (Alive) message but before sending a Coordinator (victory) message. If it does not recover before the set timeout on lower ID processes, one of them will become leader eventually (even if some of the other processes crash). If the failed process recovers in time, it simply sends a Coordinator (victory) message to all of the group.
====Network bandwidth utilization====
{{see also|network bandwidth}}
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−1) Election messages, the next higher ID sends (N−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>.
| |||