Similar questions

Discuss the need of a coordinator. Also give one algorithm for coordinator selection.

Marks: 10 M

Year: Dec 12, May 13

• Distributed algorithms require one process to act as a coordinator or initiator. To decide which process becomes the coordinator algorithms are used.
• Election algorithms are meant for electing a coordinator process from among the currently running processes in such a manner that at any instance of time there is a single coordinator for all processes in the system.
• The goal of an election algorithm is to ensure that when an election starts it concludes with all the processes agreeing on who the coordinator should be.
• Therefore, whenever initiated, an election algorithm basically finds out which of the currently active processes has the highest priority number and then informs this to all other active processes.

i.Bully Algorithm

• This algorithm was proposed by Garcia-Molina.
• When the process notices that the coordinator is no longer responding to requests, it initiates an election. A 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 the coordinator.
3. If one of the higher-ups answers, it takes over. P’s job is done.
   • A process can get an ELECTION message at any time 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 he is alive and will take over. The receiver then holds an election, unless it is already holding one.
   • All processes give up except one that 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 the highest numbered process currently running, it will win the election and take over the coordinator’s job. Thus the biggest guy in town always wins, hence the name “bully algorithm”.
   • Example:

• In fig(a) a group of eight processes taken is numbered from 0 to 7. Assume that previously process 7 was the coordinator, but it has just crashed. Process 4 notices if first and sends ELECTION messages to all the processes higher than it that is 5, 6 and 7.
• In fig (b) processes 5 and 6 both respond with OK. Upon getting the first of these responses, process4job is over. It knows that one of these will become the coordinator. It just sits back and waits for the winner.
• In fig(c), both 5 and 6 hold elections by each sending messages to those processes higher than itself.
• In fig(d), process 6 tells 5 that it will take over with an OK message. At this point 6knows that 7 is dead and that (6) it is the winner. It there is state information to be collected from disk or elsewhere to pick up where the old coordinator left off, 6 must now do what is needed. When it is ready to take over, 6 announce this by sending a COORDINATOR message to all running processes. When 4 gets this message, it can now continue with the operation it was trying to do when it discovered that 7 was dead, but using 6 as the coordinator this time. In this way the failure of is handled and the work can continue.
• If process 7 is ever restarted, it will just send all the others a COORDINATOR message and bully them into submission.

ii.Ring Algorithm

• This algorithm uses a ring for its election but does not use any token. In this algorithm it is assumed that the processes are physically or logically ordered so each processor knows its successor.
• When any process notices that a coordinator is not functioning, it builds an ELECTION message containing its own process number and sends the message to its successor. If the successor is down the sender skips over the successor and goes to the next member along the ring until a process is located.
• At each step the sender adds its own process number to the list in the message making itself a candidate to elected as coordinator
• The message gets back to the process that started it and recognizes this event as the message consists its own process number.
• At that point the message type is changed to COORDINATOR and circulated once again to inform everyone who the coordinator is and who are the new members. The coordinator is selected with the process having highest number.
• When this message is circulated once it is removed and normal work is preceded.