A Distributed Computing Tutorial by Steven Choy
Question 1: Basic Questions
- (a) Ordering is an important issue that needs to be addressed in the design of multicast group communication. Briefly describe the four possible orderings of group communication.
- (b) State the six important issues that need to be addressed in the design of group communication within a distributed system.
- (c) Briefly describe two applications of mulitcast communications.
- (d) Give an example application that total order multicast communication is required.
Question 2: Multicast Ordering
Consider the following example of multicast communication. A multicast group G has three member processes, A, B and c. Process A multicasts messages a1 then a2 to group G. Process B multicast message b1 and then b2 to group G. It is also known that multicast message a1 happened before multicast message b1, and that multicast message b2 happened before multicast message a2.
- (a) Consider that group G implements FIFO ordering. Write all possible sequences of messages as delivered by process C.
- (b) Draw two diagrams to show two scenarios that the mulitcast communication is not FIFO.
- (c) Draw a diagram to show a scenario that the mulitcast communication is FIFO ordering but not causal ordering.
- (d) Draw a diagram to show a scenario that the mulitcast communication is causal ordering.
- (e) Does causal ordering imply FIFO ordering?
- (f) Suppose we use the following algorithm to implement the Casual Ordering Multicast Protocol. Draw two diagrams, one without the causality problem and another with the causality problem, to show how messages are accepted buffered, and how vector timestamps are updated.
Description: Each host sends a copy of its vector with each message and compare the sender's vector with its own on receive:
If any entry in the sender's vector, that was sent as a "timestamp" with the multicast message is greater than the corresponding entry in the receiver's local copy fo the vector, the receiver buffers the message. This is because the sender has received a message, whcih is potentially causally related to the message it subsequently sent, that the reciever has not yet received. If the incoming message were passed up to the application, a causality violation might result.
If the sender's entry in the message's timestamp is more than one greater than the sender's entry in the local time vector, the message is also buffered. This ensures that the protocol ensures FIFO ordering.
If the sender's entry in the messages timestamp is less than the sender's entry in the local timestamp, the message is rejected -- it is a duplicate.
If none of the above are true, the message is accepted. Accepting a message offers the opportunity to dequeue previously enqueued messages, if they can now be accepted.
Example:
