A Response to Cheriton and Skeen’s Criticism of Causal and Totally Ordered Communication
📜 Abstract
In a paper to be presented at the 1993 ACM Symposium on Operating Systems Principles, Cheriton and Skeen offer their understanding of causal and total ordering as a communication property. I find their paper highly critical of Isis, and unfairly so, for a number of reasons. In this paper I present some responses to their criticism, and also explain why I find their discussion of causal and total communication ordering to be distorted and incomplete.
✨ Summary
Summary
Ken Birman’s paper responds to David Cheriton and Dale Skeen’s criticism of causally and totally ordered communication, particularly their critique of the Isis system. Birman argues that their analysis is incomplete because it treats causal and total ordering primarily as isolated communication properties rather than as components of a broader execution model incorporating process groups, reliable multicast, and virtual synchrony.
The paper defends the use of causal ordering as a practical mechanism for simplifying distributed-system development. Birman’s central claim is that system-provided ordering can reduce application complexity, debugging effort, and the likelihood of inconsistent outcomes after failures. He emphasizes that causal ordering is not intended to express every application-specific dependency or to solve every consistency problem; instead, it provides a useful baseline guarantee that can be combined with stronger, application-specific mechanisms when needed.
Birman challenges several objections raised by Cheriton and Skeen. He argues that the performance cost of causal ordering is often less significant than delays caused by flow control, resource management, and congestion. He also contends that examples involving external communication paths or application-specific ordering do not invalidate system-provided causal guarantees. Comparisons with pipes, streams, caches, and network-news systems are used to illustrate why preserving communication order can be valuable even when not every individual ordering relationship is semantically essential.
A recurring theme is that ordering guarantees should be evaluated together with failure semantics. Birman argues that Isis and virtual synchrony prevent problematic gaps in the causal past that could otherwise arise when failures interact with atomic multicast. Thus, the contribution defended in the paper is not merely CATOCS ordering in isolation, but the combination of ordering, failure handling, membership management, and a programming model intended to support highly available and consistent distributed applications.
Influence and subsequent use
The paper became part of the documented CATOCS controversy and was published alongside related responses and comments in Operating Systems Review. It continues to be cited in historical accounts of fault-tolerance research and appears in distributed-systems reading lists and research-paper collections, where it is taught alongside work on causal consistency, distributed transactions, replication, and large-scale storage systems. (dblp.org)
The available evidence supports a continuing historical and pedagogical influence, but does not establish that a particular industry system was directly based on this response. The paper’s broader position—that strong communication and failure guarantees can simplify reliable distributed programming—forms part of the intellectual background for later discussions of replication, consistency, and the trade-offs surrounding the CATOCS debate. (sigops.org)