Understanding the Limitations of Causally and Totally Ordered Communication
David R. Cheriton and Dale Skeen,
Proceedings of the 14th ACM Symposium on Operating Systems Principles,
December 5-8, 1993
Summary
Main idea:
Causally and totally ordered communication support (CATOCS) has been proposed as an important building block for constructing reliable distributed systems.
This paper argues that for a significant class of real distributed applications using CATOCS protocols is of little merit. The requirements satisfied by CATOCS can be satisfied using alternative, state-level general-purpose mechanisms.
The basic problem with CATOCS is explained using the end-to-end argument: CATOCS is at the communication level and is therefor limited to ensuring communication level semantics. Consistency requirements are usually connected to the applications state. This leads to the conclusion that the ideal framework for state consistency should be a state-level framework rather than a communication level one. Distributed systems that support object oriented technology are presented as such a framework.
Paper outline:
- Definitions, assumptions and explanations related to COTACS
- Causally ordered communication: CBCAST
- Totally ordered communication: ABCAST
- CATOCS Limitations and cost
- CATOCS limitations:
- Unrecognized causality (cant say "for sure")
- Lack of serializability (cant say "together")
- Unexpressed semantic ordering constraints (cant say the "whole story")
- Lack of efficiency gain over state-level techniques (cant say efficient)
- Cost:
- For each of the above limitations CATOCS solutions are shown to have higher cost than state-level solutions
- The overall limitation
Is explained by the end-to-end argument: a lower level facility cannot ensure higher level semantics. At best it can be used as an optimization for higher levels.
CATOCS as a communication level facility cannot recognize & enforce application level end-to-end semantics. It is also shown in the examples that not only does using CATOCS not provide any optimizations, but it also tends to add extra overhead.
- CATOCS applicability
- Applicability to a number of classes of distributed applications, including examples from literature that explains the use of CATOCS protocols is examined
- classes of distributed applications examined
- data dissemination applications (e.g. Usenet)
- global predicate evaluation
- transactional applications
- replicated data
- distributed real time applications
- The limitations shown before are demonstrated as obstacles in using CATOCS for these classes of applications
- For each such class alternative state-level solutions using established techniques are shown to exist
- Scaling cost is presented as an additional problem of using CATOCS protocols
- Expected message buffering is quadratically proportional, in the worst case, to the number of participating processes
- Conclusions
- There is no need for CATOCS at the communication level
- Logical clocks based on communication activity should be applied at the state level. This is done in the object oriented view of distributed systems