Difference Between Bully and Ring Algorithm

Keywords: compare bully and ring algorithm, ring and bully, ring election algorithm

Compare bully and ring election algorithm

Choose or design an algorithms in distributed system is a big challenging issue since past until now. The big challenge is calls for a suitable, efficient and no error election algorithm. Nodes communicate with each other using shared memory and through or via message passing. Coordinator will be the key requirement for nodes to execute or run any distributed task effectively and smoothly. There will be no central controlling node exists in a pure distributed system, every node has to communicate other nodes in the network to make an important decision. During the decision process all nodes will not often make the same decision. All involve the decision-making process and communication between nodes time-consuming. When consistency is needed, among all the nodes Coordination among nodes becomes harder.

The main purpose of the leader election is to choose a node as a coordinator. It will act as a leader and coordinate activities of the whole system. A leader in any leader election algorithm is usually chosen based on the node which has the largest identifier. The nodes will reach a state called as terminated state once the leader is selected. There are 2 states which are elected states and non-elected states in the leader election algorithms. When a node enters either state, it always remains in that state. The leader election algorithm has to satisfy liveness condition and safety for an execution. The safety condition requires that only one single node can enter the elected state and it will become the leader of the distributed system. The liveness condition states that every node will eventually enter an elected state or a non-elected state.

There are many election algorithms been proposed over the years such as Bully algorithm, Ring algorithm, Chang and Roberts’ algorithm, Le Lann’s algorithm, and Franklin’s algorithm. All these algorithms require nodes to be directly involved in leader election. Nodes will transmit the messages to one another for exchange information until an agreement is reached. Once a node is been selected as leader, all the nodes will acknowledge the role as that node as leader.

Bully algorithm

The algorithm was devised by Garcia-Molina in 1982. While one of the process notices that the coordinator is not active, crashed, or responding to requests, it will start an election. Process Q, holds an election as follows:

-Q sends a message to all the processes with higher numbers to start the election.

-Q wins the election and becomes coordinator if and only if no higher numbers responds.

-If there is one of the higher-ups number answers, it takes over. Q’s job is finish or done.

A process can receive an Election message from any one of its lower-numbered nodes at any moment. The receiver sends a confirmation message back to tell the sender that it is active and will take over when an Election message received. If other processes do not respond, and there is only one then it will become the new coordinator. After that, it will send all processes a message to announce its victory and starting immediately it will be the new coordinator.

If a process that was down before but come back up, it will hold an election. If it happens to be the highest-numbered process among other currently running processes, it will win the election then will become leader and take over the coordinator’s job.

Process 4 holds an election

Process 5 and 6 respond, telling 4 to stop

Now 5 and 6 each hold an election

Process 6 tells 5 to stop

Process 6 wins and tells everyone

Modified Bully Algorithm

In Bully algorithm, the number of message be exchanged between processes is very high. Thus, this Modified Bully Algorithm been devised to reduce the heavy traffic in network. Besides to reduce the heavy traffic flow in network, the number of stages is decreased from at most five stages to at most four stages.

The algorithm has following steps:

1st step

When process Q notices coordinator had crashed, it will start an election.

2nd step

Q will send Election message to all other processes with higher priority numbers when Q find out that the coordinator was crashed.

3rd step

All the processes that receives message which with higher priority process than Q will send OK message back to process Q with its unique priority number.

4th step

If no processes responses to process Q, Q will broadcast one Coordinator message to all processes to declare itself as a coordinator. In vice versa, process Q will select the process Q with the highest priority number as coordinator and then send to it the GRANT message.

5th step

Coordinator process will broadcast message to all the processes and informs them that itself as a coordinator at this stage.

6th step

After the process with higher number compare to coordinator is up, modified Bully algorithm is run immediately. It does not have the drawback of Bully algorithm which has high number of message passing.

If a higher priority number process crashes after sending it priority number to Q, Process Q will send GRANT message to it meaning that itself is the highest process and Q waits for broadcasting coordinator message else it will continue run the modified Bully algorithm. After a certain time or period, process Q does not receives any Coordinator message, it will repeat the algorithm again.

Thus, this algorithm is efficient and safe to use for select the coordinator.

Figure 2

The modified Bully election algorithm

Process 2 holds an election.

Processes 3, 4, 5 and 6 respond, telling its unique priority number.

Now 3 comparing the priority number and select the highest process (process 6) and send a message to its (GRANT).

Process 6 tell to everyone that “it is coordinator”.

Token Ring algorithm

Token ring algorithm is totally different with Bully algorithm. It achieves mutual exclusion by creating a bus network of processes in distributed system. It does not have a real ring in the network but a logical ring is constructed with all processes and all processes are assigned a position in the ring. All the processes know who is before them and next after them in the line.

Token Ring algorithm works:

1st step: Process 6 is down.

2nd step: Process 3 notices that Process 6 does not respond. So it starts an election, sending a message containing its id to the next node in the ring.

3rdstep: Process 5 passes the message on, adding its own id to the message.

4th step: Process 0 passes the message on, adding its own id to the message.

5th step: Process 1 passes the message on, adding its own id to the message.

6th step: Process 4 passes the message on, adding its own id to the message.

7th step: When Process 3 receives the message back, it knows the message has gone around the ring, as its own id is in the list. Picking the highest id in the list, it starts the coordinator message “5 is the leader” around the ring.

8th step: Process 5 passes on the coordinator message.

9th step: Process 0 passes on the coordinator message.

10th step: Process 1 passes on the coordinator message.

11th step: Process 4 passes on the coordinator message. Process 3 receives the coordinator message, and stops it.

Modified Token Ring algorithm

This algorithm is modified from Token Ring algorithm. It is modified to reduce the number of message passing and additional message being sent to the elected leader.

When the leader has crashed and been noticed by a node, it will send its ID number to the node next to it in the ring. It is not necessary for all nodes to send their IDs into the ring. The receiving node compares the received ID with its own, and forwards whichever is the greatest at this moment. But this comparison is done by all the nodes such that only the greatest ID remains in the ring. After that, the greatest ID will return to the initial node. It declares itself as the leader by sending a coordinate message into the ring if the received ID equals that of the initial sender.

This method will dramatically reduce the overhead involved in message passing. Besides that, if there is many nodes notice the leader crashed or absence at the same time, only the message of greatest ID node circulates in the ring and it will prevent the smaller IDs from being sent message in the ring.

Modified Token Ring algorithm works:

Nodes 2 and 4 notice that the coordinator has crashed simultaneously

They send their IDs into the ring

The greatest ID always remain in the ring

The greatest ID keep passing in the ring

5 is declared as the leader

Advantages and limitation algorithms

Bully algorithm and Modified Bully algorithm

Both of these algorithms have almost the same advantages. They can always check the liveness of the leader by the assumption of message delivery. The process is chosen as the non-crashed process at the end of the run with the largest process number if no process is replaced. It is impossible for two processes to decide which coordinator among them is, since the process with the lower number will discover that the other exits and defer to it.

However, Modified Bully algorithm has another advantage that Bully algorithm does not have. That is the lower traffic passing. It reduce the traffic in the message communicate passing compare to Bully algorithm. It does not let the lower numbered process involve in the election but just higher numbered process. It also will send a GRANT message to the process which wins in the election. Then the process which wins will announce the message that declares itself as leader to all the nodes. It is more less traffic flow in the process and it is much better than Bully algorithm.

The Bully algorithm also suffers from many shortcomings. This algorithm is not guaranteed to meet the safety condition if processes that had crashed and replaced by processes with the same number. A process that replaces the crashed process Q may decide which has the highest number just as another process has decided that it has the highest number. Both of them will announce themselves as the coordinator in a same time. But unfortunately, there are no guarantees on message passing order, and the recipients of these messages may give out different conclusion on which is the coordinator process. The condition may be broken if the assumed timeout values turn out to be accurate. That means if the processes’ failure detector is unreliable.

Token Ring algorithm and Modified Token Ring algorithm

Token Ring and Modified Token Ring algorithm are having very special routing. It is totally different with the Bully algorithm. They know the process next to them and just passing the message to the process which next to them. It is much more simple compare to other algorithm. They just need to take the information from beside, add the value and pass to another side. The message passing traffic is very much lower than other algorithms. This is because they just pass the information to the next process after that no more communicate with other processes. This reason make the algorithm become much easier to carry out. Compare with the bully algorithm which need keep communicate with all the process, Token Ring just need the message passing around the ring and know all the information about which one process having the higher numbered process. After that, the process can decide after compare and get the highest numbered process. Then, it just needs passing a decision message around the ring to announce or declare the leader in the ring.

Meanwhile, the token ring and modified token ring also have their different. Token ring needs add up the information when the leader is crashed or down. Then the message or information will keep pass and to next process and the process will add its own ID into the message and passed to the process next to it. It will keep on going until the message reaches the process which starts the election process. Hence, the process will compare the information then announce the new leader by passing the coordinator message to the next process and keep on passing it in the ring.

But the modified token ring will have slightly different. When the process notice the leader is crashed and start the election, the information message passing will start. When the message passing in the ring, it will compare the results collect from the processes. In the comparison, the highest numbered process’s ID only will remain stay in the information message. Those smaller numbered processes’ ID will be deleted or will not be put inside the information message. When the information message finish a round, it will straight away start announce or pass the coordinator message to all the process for the new leader been selected. It is much easier and simple for the information message. All the comparison will be done when the new ID want to add into the information message. It not just save the time and no need wait until the end just compares the information that get from all processes. It also make the information message smaller and the message passing consumed less time to pass to the next process.

The limitations for Token Ring and Modified Token Ring algorithm are they both also consumed a lot of time in message passing. It needs to pass and get the information message. It will take a round to get all the information. For those smaller processes, they also need to involve in the passing message process even they also would not been selected as a leader. It will take much more time compare with other algorithms. After the leader had been selected, the coordinator message also needs to pass around all the processes in the ring. The coordinator message will not pass to all the processes at once but it will pass from one to another one. All these processes really consumed and waste a lot of time compare with other algorithms.

Besides above limitation, the message passing around the ring sometimes also will miss. When the information or coordinator message passing around the ring, it will possible loss or miss out. After that, it need take time to been noticed and regenerate the information message passing. Hence, the message needs to restart pass among the processes. This make the process for the election for leader consumed longer than other algorithms.

Algorithms analysis

In modified Bully Algorithm, if a single node detects the coordinator is crashed, N (i) with an order of O (n) is obtained as follows:

The order of message passing increase to O(n2) with fault tolerance as follows:

Where i’ is the selected leader ID number.

The bully algorithm against the Modified Bully algorithm has been plots for the case when one node notices that the coordinator has crashed.

From the graph, the traffic for the Bully algorithm from the beginning is much higher than modified Bully algorithm. Hence it keeps decrease when the process ID noticed increased. Meanwhile, the modified Bully algorithm is having a nearly constant for number of message passing. This shows that the traffic in the modified Bully algorithm is much less than Bully algorithm. That means modified Bully algorithm is better than Bully algorithm and has lower traffic flow when election happens.

In Token Ring algorithm, the number of message passed with an order of O (n2) is:

For the modified Token Ring algorithm is:

The number of messages passed reduced and the complexity is much lower.

From the graph above, the number of message passing in the ring for the Token Ring algorithm keep increase when the number of processes notices that the coordinator has crashed. But for the modified Token Ring algorithm, the number of message passing in the ring has not much different compare to non-modified. This shows that the traffic flow in the ring for modified ring is much lower than non modified.

Conclusion

Leader election algorithms play an important role in distributed system. The modified Bully algorithm and Modified Token Ring algorithm are efficient and easier to implement in all cases if compare to the existing one. But, still need a lot of improvement have to be done so that the algorithms can be more safety and efficient in the electing the coordinator in distributed system.