* Understanding the Limitations of Causally and Totally Ordered Communication
* Authors: D.R. Cheriton and D. Skeen
* Field: OS/Networking

Causally ordered communication ensures that message delivery follows
the "happens-before" relation.  In particular if there exists a
process P s.t. m1 is sent by or received at P before P sends m2, then
m1 happens-before m2.  Take the transitive closure of this property to
get a relation between messages.

Causal multicast makes sure that message delivery to a process group
is causally ordered; i.e. if m1 happens-before m2, then m1 is
delivered to the process group before m2 is delivered.

Totally ordered multicast ensures that all messages are delivered to
all members of a process group in the same order, even if they are
concurrent with respect to the "happens-before" relation.

Basic argument against CATOCS: violated end-to-end argument.  Tries to
implement ordering of events by imposing an order on the communication
system, when the events of interest have semantics at the application
level.  Four issues pointed out by authors:

1) Can't say "for sure" - because of alternate communication channels,
i.e. database, address space (threads)

2) Can't say the "whole story" - Some semantic constraints are
stronger than happens-before so just happens-before isn't sufficient.

3) Can't say "together" - can't guarantee serializability to events
corresponding to several messages

4) Can say efficiently - Mechanisms used to implement CATOCS can be
efficiently moved to higher levels.  Worse, working at the low
semantic of messages introduced false causality: certain messages
happen to be sent after others but have no causal relationship.
Forcing the delivery to follow causal ordering hurts performance
unnecessarily.