Causal Order of Messages

Causal Order of Messages

presented by Dave Sisson

The information contained here can be found in the book used for this class, Advanced Concepts in Operating Systems by Singhal and Shivaratri on pages 106-108.

Explanation of Causal Ordering of Messages:

The purpose of causal ordering of messages is to insure that the same causal relationship for the "message send" events correspond with "message receive" events. (i.e. All the messages are processed in order that they were created.)

Birman-Schiper-Stephenson Protocol

There are three basic principles to this algorithm:

  1. All messages are time stamped by the sending process.

[Note: This time is separate from the global time talked about in the previous sections. Instead each element of the vector corresponds to the number of messages sent (including this one) to other processes.]

  1. A message can not be delivered until:
    • All the messages before this one have been delivered locally.
    • All the other messages that have been sent out from the original processs has been accounted as delivered at the receiving process.
  2. When a message is delivered, the clock is updated.

This protocol requires that the processes communicate through broadcast messages since this would ensure that only one message could be received at any one time (thus concurrently timestamped messages can be ordered).

[Note: There may be other reasons that broadcast messages are required.]

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:

  • A message cannot be delivered if there is a message mentioned in the list of timestamps that predates this one.
  • Otherwise, a message can be delivered, performing the following steps:
    1. 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.
    2. Update the local logical clock.
    3. Check all the local buffered messages to see if they can now be delivered.