Birman Schiper Stephenson Protocol

This algorithm is used to maintain the causal ordering of the messages i.e. the message which is sent first should be received first. If send (M1)–>send(M2) then for all processes which receive the messages M1 and M2 should receive M1 before M2.

Features :

1.Broadcast based messaging.

2.Size of the messages are small.

3.More no. of messages are sent.

4.Limited state information.

Key Points :

1.Each process increases its vector clock by 1 upon sending of messages.

2.Message is delivered to a process if the process has received all the messages preceding to it.

3.Else buffer the message.

4.Update the vector clock for the process.

Schiper-Eggli-Sandoz Protocol

Instead of maintaining a vector clock based on the number of messages sent to each process, the vector clock for this protocol can increment at any rate it would like to and has no additional meaning related to the number of messages currently outstanding.

Sending a message:

1.All messages are timestamped and sent out with a list of all the timestamps of messages sent to other processes.

2.Locally store the timestamp that the message was sent with.

Receiving a message:

1.A message cannot be delivered if there is a message mentioned in the list of timestamps that predates this one.

2.Otherwise, a message can be delivered, performing the following steps:

a)Merge in the list of timestamps from the message:

_______Add knowledge of messages destined for other processes to our list of processes if we didn't know about any other messages destined for one already.

_______If the new list has a timestamp greater than one we already had stored, update our timestamp to match.

b)Update the local logical clock.

c)Check all the local buffered messages to see if they can now be delivered.