Mumbai University > Computer Science > Sem 8 > Parallel And Distributed System

Assumptions.

• Each process knows the id and address of every other process. communication is reliable.

• A process initiates an election if just recovered from failure or it notices that the coordinator has failed.

• Three types of messages: Election, o/n co-coordinator.

• Several processes can initiate an election simultaneously.

• Need consistent result.

Bully Algorithm Details.

• Any process P can initiate an check.

• P sends election message to all process with higher IDS and awaits OK messages.

• If no OK messages, P becomes coordinator and sends coordinator messages to all processes.

• If it receives an OK, it drops out and waits for an coordinator.

• If a process receive an election message.

• Immediately sends coordinator message if it is the process with highest ID.

• Otherwise returns an OK and start election.

• If a process receives a coordinator message, it treats sender as a co-coordinator.

Bully Algorithm : Assume p10 = 7 is co-coordinator.

p4 p7 has failed and hence start election for all process higher then p4.

$\because$ ps & p6 assume they bully p1 by sending OK.

Now i5 & p6 start election.

Now p6 bully.

$\because$ no one can bully p6

$\because$ p6 becomes co-coordinator R informs everyone.