When is causal broadcast not enough for causal memory?
While getting ready to teach my grad distributed systems course this fall, I found myself once again flipping through Cheriton and Skeen’s rather scathing 1993 article “Understanding the limitations of causally and totally ordered communication”.1 One of Cheriton and Skeen’s complaints about causally ordered communication is that it does not enforce the ordering constraints that they care about. They write:
[T]he correct behavior of an application requires ordering constraints over operations on its state, and these constraints are typically stronger than or distinct from the ordering constraints imposed by the happens-before relationship. Such ordering constraints, referred to as “semantic” ordering constraints, run the gamut from weak to strong, and they may or may not require grouping as well. Example constraints include causal memory [1], linearizability [12], and, of course, serializability. Even the weakest of these semantic ordering constraints, causal memory, can not be enforced through the use of causal multicast [1].
While it’s a good point that there are many important application-level ordering relationships that are not captured by the happens-before order, the last sentence above caught my attention because it seemed counterintuitive. Of course we can’t expect the causal order to give us linearizability or serializability. But causal memory is a distributed shared memory abstraction in which “reads respect the order of causally related writes”, and it certainly seems like it ought to be the kind of thing you can implement using good old causal-order-enforcing communication primitives. So, why can’t you? Let’s dig in!
