Understanding the Limitations of Causally and Totally Ordered Communication
📜 Abstract
Causally and totally ordered communication support (CATOCS) has been proposed as important to provide as part of the basic building blocks for constructing reliable distributed systems. In this paper, we identify four major limitations to CATOCS, investigate the applicability of CATOCS to several classes of distributed applications in light of these limitations, and the potential impact of these facilities on communication scalability and robustness. From this investigation, we find limited merit and several potential problems in using CATOCS. The fundamental difficulty with the CATOCS is that it attempts to solve state problems at the communication level in violation of the well-known “end-to-end” argument.
✨ Summary
The paper argues that causally and totally ordered communication support (CATOCS) provides ordering guarantees at the communication level, whereas distributed applications generally require consistency guarantees over application state. It identifies four principal limitations: CATOCS cannot detect semantic causality arising through hidden channels; it cannot serialize groups of operations or support atomic application-level updates; it cannot express many semantic ordering requirements, such as those involving computed data, linearizability, or serializability; and it introduces substantial overhead without a corresponding efficiency advantage over state-level mechanisms. The authors examine news dissemination, trading systems, global predicate evaluation, transactions, replicated data, large-scale naming, and real-time systems, arguing that versions, timestamps, transactions, locks, snapshots, and application-specific state management are generally more appropriate. They further argue that CATOCS buffering and membership-management costs can scale poorly, potentially approaching quadratic growth with group size. The proposed design principle is to solve state problems at the state level, using durable state metadata and object-oriented abstractions rather than embedding broad consistency semantics in the communication substrate.
The paper also generated a documented contemporaneous debate: Ken Birman published a response defending and clarifying the CATOCS/Isis approach, while Robbert van Renesse published “Why Bother with CATOCS?” in the same Operating Systems Review issue. (researchgate.net) Its arguments have continued to be used as teaching material in distributed-systems courses and reading lists, particularly in discussions of causal ordering, virtual synchrony, replication, and the placement of functionality between communication and state-management layers. (courses.cs.duke.edu)