Get the latest tech news

When is causal broadcast not enough for causal memory?

, 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.

The paper that Cheriton and Skeen cite as “[1]” there is “Implementing and programming causal distributed shared memory”, published in 1991 by Ahamad, Hutto, and John. A Lamport diagram of the execution in Figure 3 of Ahamad et al., "Implementing and programming causal distributed shared memory"Here, we have three processes, \(P_1\), \(P_2\), and \(P_3\), each of which has carried out a sequence of read and write operations. Perhaps it won’t come as a surprise, then, that in the implementation of causal memory that Ahamad et al. show later in the paper, reads do in fact involve inter-process communication!

Get the Android app