Understanding the Limitations of Causally and Totally Ordered Communication
D.R. Cheriton and D. Skeen

Paper's Contribution:

Essentially a counter-example to previous publications that have
proposed "causally and totally ordered communication support" (CATOCS)
as an essential tool for distributed application development.

Paper's Critical Ideas:

The key argument revealed is CATOCS is not a strong enough mechanism
to ensure totally and properly ordered relationships in most (if not
all) real distributed systems, and thus developers must still rely on
application specific mechanisms (not communication channel mechanisms)
to ensure proper behavior.  Given that, CATOCS becomes unnecessary.

The paper lays out 4 major limitations to CATOCS.  One, unrecognized
causality, or relationships at the semantic level that can't be
enforced at the communications channel.  Two, lack of serialization,
or the lack of ability to group messages together so they remain
consistent.  Three, unexpressed semantic ordering, or constraints that
aren't captured in the "happens-before" relationship.  And four, lack
of efficiency and failure to scale well as communication networks
grow.

One interesting thing about the article is how they've taken many
well-known issues from parallel processing papers and applied them to
distributed computing, making a connection that doesn't always seem
obvious from many of the other papers we've read.

Paper's Flaws:

There's not a whole lot to criticize about this paper.  Their
arguments are well stated and logically ordered.  The counter-
examples used are well presented and understandable.  The authors
appear to have knowledge of distributed systems theory and actual
industry experience developing distributed applications, and they
speak authoritatively on the subject.  I guess you could fault the
paper for arriving at a not-so-appealing conclusion that each
distributed application is going to have to develop its own proper
application mechanisms at the "state-level" for ensuring correct event
ordering.

Relevance to modern systems:

Any current distributed application development will need to design
mechanisms for ensuring that events and communications occur in proper
order.  If this could be completely achieved at the communication
channel layer, then application development would be orders of
magnitude simpler.  However, as the paper demonstrates, CATOCS isn't
enough to guarantee complete system ordering for most distributed
applications.  Distributed architects undertaking new projects should
certainly be aware of these arguments before they rely on a CATOCS
toolkit as their only source intended for system- wide ordering.