Show that, if the basic multicast that we use in the algorithm is also FIFO-ordered, then the resultant totally-ordered multicast is also causally ordered. Is it the case that any multicast that is both FIFO-ordered and totally ordered is thereby causally ordered?

Question

What will be an ideal response?

Answer 1

We show that causal ordering is achieved for the simplest possible cases of the happened-before relation; the general case follows trivially.

First, suppose p TO-multicasts a message m1 which q receives; q then TO-multicasts message m2. The sequencer must order m2 after m1, so every process will deliver m1 and m2 in that order.

Second, suppose p TO-multicasts a message m1 then TO-multicasts message m2. Since the basic multicast is FIFO-ordered, the sequencer will receive m1 and m2 in that order; so every group member will receive them in that order.

It is clear that the result is generally true, as long as the implementation of total ordering guarantees that the sequence number of any message sent is greater than that of any received by the sending process.