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:
- 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.]
- 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.
- 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:
- All messages are timestamped and sent out with a list of all the
timestamps of messages sent to other processes.
- 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:
- 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.
- Update the local logical clock.
- Check all the local buffered messages to see if they can now
be delivered.
Go Back to the Operating Systems page.
Last updated: 21 Feb 1995 / cs5204@ie.cs.vt.edu