Show that, if the basic multicast that we use in the algorithm of Figure 15.13is 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?
What will be an ideal response?
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. See Florin
& Toinard [1992].
[Florin & Toinard 1992] Florin, G. and Toinard, C. (1992). A new way to design causally and totally ordered
multicast protocols. Operating Systems Review, ACM, Oct. 1992.
You might also like to view...
What fraction of state legislators around the country would be required to ratify a Constitutional amendment in order for it to pass?
What will be an ideal response?
Basic data manipulations include _____ that involves eliminating rows in a relational database according to certain criteria.
a. selecting b. joining c. projecting d. linking
An interface standard can consist of four parts, or components: the electrical component, the mechanical component, the ____ component, and the procedural component.?
A. ?functional B. ?automatic C. ?administrative D. ?organizational
In the accompanying figure, item 3 points to the ____.
A. layer boundary B. edit bars C. rectangle frame D. none of the above