Message passing Systems and Selection Algorithm

What is message passing system ?

It is a system in which process exchange infromation with each other by sending and receiving messages over a network since they dont have a common memory

In message passing system order is important

What are the three types of message ordering ?

• Casual Order

• Total Order

  • Total Casual Order

What is causal order?

If we send message A before B then every process should recive A before B

Messages which are independent can arrive in any order

Ex: If p1 says update file and p2 reply file updated then it should show file updated

What is Total Order?

In this all processes receive all messages in exactly the same order no matter what

• Even if messages are unrelated , every process will see them in same sequence

  • Ex; If p1 sends A and p2 sends B either all of them see A then B or B then A

What is total causal Order?

It is the combination of both causal and total order
- If A → B ( casual ) then A must be delivered before B

- If A and B are independent even they need to go in order

- Causality + consistency across processes

What is selection algorithm?

• It is also known as election algorithm

• It is used in distributed systems to select the coordinator (leader) among multiple processes

• The work of coordinator is to manage resource allocation , syncronization

• If coordinator fails then it will choose a new one

  
  

There are two types of Selection or election algorithm

• Bully Algorithm

• Ring Algorithm

What is Bully Algorithm ?

In this we select the leader which has highest unique ID wins.

When the coordinator fails the election algorithm starts again

What are the step by step process in bully algorithm?

1. In this process P detects that coordinator is dead

2. P sends election messages to all the processes with higher IDs then P

3. If no one replies within time P declare himself as coordiator ( as no higher process is alive )

4. Else if one process reply OK ,, p stops and waits

5. Higher process starts an election and if higher then it will be coordinator

6. If waiting process doesn[‘t recieve COORDINATOR within time then it restarts

What is Ring Algortihm ?

• All the process are arranged in Ring Topology

• To select coordinator , an election message is passed

• Process with highes ID becaused the new coordinator

Process of Ring Algorithm

1. A process notice that current coordinator fails

2. The process P creates an election message conatiningits ID

3. It sends the message to next process

4. Each process add their ID to the message

5. Once the message comes back to the process P then highest ID get choosen ad new coordinator