Bully algorithm

, by Engineer's Vision

The bully algorithm is a method in distributed computing for dynamically selecting a coordinator by process ID number.



Assumptions in Bully Algorithm
The system is synchronous and uses timeout for identifying process failure

Message Types in Election Algorithms
  • Election Message : Sent to announce the election
  • Answer Message : Respond to the election message
  • Coordinator message: sent to announce the identity elected process
Comparison of Bully algorithm with ring algorithm
  • Assumes that system is synchronous
  • Uses timeout to detect process failure/crash
  • Each processor knows which processor has the higher identifier number and communicates with that

Explanation
When a process P determines that the current coordinator is down because of message timeouts or failure of the coordinator to initiate a handshake, it performs the following sequence of actions:
  1. P broadcasts an election message (inquiry) to all other processes with higher process IDs.
  2. If P hears from no process with a higher process ID than it, it wins the election and broadcasts victory.
  3. If P hears from a process with a higher ID, P waits a certain amount of time for that process to broadcast itself as the leader. If it does not receive this message in time, it re-broadcasts the election message.
  4. If P gets an election message (inquiry) from another process with a lower ID it sends an "I am alive" message back and starts new elections.
Note that if P receives a victory message from a process with a lower ID number, it immediately initiates a new election. This is how the algorithm gets its name - a process with a higher ID number will bully a lower ID process out of the coordinator position as soon as it comes online.

Ring algorithm : 

The ring algorithm assumes that the processes are arranged in a logical ring and each process is knows the order of the ring of processes.
Processes are able to “skip” faulty systems: instead of sending to process j, send to j + 1.
Faulty systems are those that don’t respond in a fixed amount of time.



When the message returns to p, it sees its own process ID in the list and knows that the circuit is complete.
P circulates a COORDINATOR message with the new high number.
Here, both 2 and 5 elect 6: [5,6,0,1,2,3,4] [2,3,4,5,6,0,1]

C - Programm :

#include<stdio.h>

void bully()
{
int i,p[10],pno,ch,co,new_co;
printf("\n\tHow many processes are in system : ");
scanf("%d",&pno);
for(i=0;i<pno;i++)
{
p[i]=1;
}
do
{
printf("\n\t***** BULLY ALGO *****\n\t1.Crash Process\n\t2.Recover process\n\t3.Go in back menu\n\tEnter choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:printf("\n\tProcess %d is crash*****\n\tEnter co-ordinate to start election : ",pno);
p[pno-1]=0;
new_co=0;
scanf("%d",&co);
l1 :
for(i=co;i<pno;i++)
printf("\n\t Election message to process %d",i+1);
for(i=co;i<pno;i++)
if(p[i]==1)
{
if(i>new_co)
new_co=i;
printf("\n\t Ok message from process %d ",i+1);
}

printf("\n\t****New coordinator is %d *****",new_co+1);
break;
case 2:
p[pno-1]=1;
co=pno-2;
goto l1;
break;
}
}while(ch!=3);
}

void ring()
{
int i,p[10],pno,ch,co,new_co,flag=0;
printf("\n\tHow many processes are in system : ");
scanf("%d",&pno);
for(i=0;i<pno;i++)
{
p[i]=1;
}
do
{
printf("\n\t***** RING ALGO *****\n\t1.Crash Process\n\t2.Recover process\n\t3.Go in back menu\n\tEnter choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:printf("\n\tProcess %d is crash*****\n\tEnter co-ordinate to start election : ",pno);
p[pno-1]=0;
scanf("%d",&co);
l2 :
new_co=co;
for(i=co;i<pno;i++)
if(p[i])
{
printf("\n\t Message to %d ",i+1);
if(i>new_co)
new_co=i;
}
for(i=0;i<co;i++)
if(p[i])
printf("\n\t Message to %d ",i+1);
printf("\n\t****Cycle completed New coordinator is %d *****",new_co+1);
break;
case 2:
p[pno-1]=1;
co=pno-2;
goto l2;
break;
}
}while(ch!=3);
}

int main()
{
int ch;
do
{
printf("\n\t1.Bully \n\t2.Ring\n\t3.Exit\n\tEnter choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
bully();
break;
case 2:
ring();
break;
}
}while(ch!=3);
}

/* OUTPUT
student@mmcoe-desktop:~$ ./a.out 

1.Bully 
2.Ring
3.Exit
Enter choice : 1

How many processes are in system : 9

***** BULLY ALGO *****
1.Crash Process
2.Recover process
3.Go in back menu
Enter choice : 1

Process 9 is crash*****
Enter co-ordinate to start election : 3

 Election message to process 4
 Election message to process 5
 Election message to process 6
 Election message to process 7
 Election message to process 8
 Election message to process 9
Ok message from process 4 
Ok message from process 5 
Ok message from process 6 
Ok message from process 7 
Ok message from process 8 
****New coordinator is 8 *****
***** BULLY ALGO *****
1.Crash Process
2.Recover process
3.Go in back menu
Enter choice : 2

 Election message to process 8
 Election message to process 9
Ok message from process 8 
Ok message from process 9 
****New coordinator is 9 *****
***** BULLY ALGO *****
1.Crash Process
2.Recover process
3.Go in back menu
Enter choice : 3

1.Bully 
2.Ring
3.Exit
Enter choice : 2

How many processes are in system : 6

***** RING ALGO *****
1.Crash Process
2.Recover process
3.Go in back menu
Enter choice : 1

Process 6 is crash*****
Enter co-ordinate to start election : 3

Message to 4 
Message to 5 
Message to 1 
Message to 2 
Message to 3 
****Cycle completed New coordinator is 5 *****
***** RING ALGO *****
1.Crash Process
2.Recover process
3.Go in back menu
Enter choice : 2

Message to 5 
Message to 6 
Message to 1 
Message to 2 
Message to 3 
Message to 4 
****Cycle completed New coordinator is 6 *****
***** RING ALGO *****
1.Crash Process
2.Recover process
3.Go in back menu
Enter choice : 3

1.Bully 
2.Ring
3.Exit
Enter choice : 3
student@mmcoe-desktop:~$ gcc CL_1.c
student@mmcoe-desktop:~$ ./a.out 

1.Bully 
2.Ring
3.Exit
Enter choice : 1

How many processes are in system : 9

***** BULLY ALGO *****
1.Crash Process
2.Recover process
3.Go in back menu
Enter choice : 1

Process 9 is crash*****
Enter co-ordinate to start election : 3

Election message to process 4
Election message to process 5
Election message to process 6
Election message to process 7
Election message to process 8
Election message to process 9
Ok message from process 4 
Ok message from process 5 
Ok message from process 6 
Ok message from process 7 
Ok message from process 8 
****New coordinator is 8 *****
***** BULLY ALGO *****
1.Crash Process
2.Recover process
3.Go in back menu
Enter choice : 2

Election message to process 8
Election message to process 9
Ok message from process 8 
Ok message from process 9 
****New coordinator is 9 *****
***** BULLY ALGO *****
1.Crash Process
2.Recover process
3.Go in back menu
Enter choice : 3

1.Bully 
2.Ring
3.Exit
Enter choice : 2

How many processes are in system : 8

***** RING ALGO *****
1.Crash Process
2.Recover process
3.Go in back menu
Enter choice : 1

Process 8 is crash*****
Enter co-ordinate to start election : 4

Message to 5 
Message to 6 
Message to 7 
Message to 1 
Message to 2 
Message to 3 
Message to 4 
****Cycle completed New coordinator is 7 *****
***** RING ALGO *****
1.Crash Process
2.Recover process
3.Go in back menu
Enter choice : 2

Message to 7 
Message to 8 
Message to 1 
Message to 2 
Message to 3 
Message to 4 
Message to 5 
Message to 6 
****Cycle completed New coordinator is 8 *****
***** RING ALGO *****
1.Crash Process
2.Recover process
3.Go in back menu
Enter choice : 3

1.Bully 
2.Ring
3.Exit
Enter choice : 3
student@mmcoe-desktop:~$ 
*/




Labels:

0 comments:

Post a Comment

Subscribe to: Post Comments (Atom)