Causal consistency captures the notion that causally-related operations should appear in the same order on all processes—though processes may disagree about the order of causally independent operations.
For example, consider a single object representing a chat between three people, where Attiya asks “shall we have lunch?”, and Barbarella & Cyrus respond with “yes”, and “no”, respectively. Causal consistency allows Attiya to observe “lunch?”, “yes”, “no”; and Barbarella to observe “lunch?”, “no”, “yes”. However, no participant ever observes “yes” or “no” prior to the question “lunch?”.
Convergent causal systems require that the values of objects in the system converge to identical values, once the same operations are visible. In such a system, users could transiently observe “lunch”, “yes”; and “lunch”, “no”—but everyone would eventually agree on (to pick an arbitrary order) “lunch”, “yes”, “no”.
Causal consistency is sticky available: even in the presence of network partitions, every client connected to a non-faulty node can make progress. However, clients must stick to the same server.
A slightly stronger version of causal consistency, Real-Time Causal, is proven to be the strongest consistency model in an always-available, one-way convergent system. Most “causally consistent” systems actually provide these stronger properties, such as RTC or causal+.
When a total order is required, and you’re willing to sacrifice availability (and latency), consider Sequential Consistency. If you need total availability, you’ll have to give up causal (and read-your-writes), but can still obtain Writes Follow Reads, monotonic reads, and monotonic writes.
<aside> 💡 支持 writes follow reads，因为 write 和 read 间存在 causual 关系。
</aside>
Causal memory stems from Lamport’s definition of the happens-before relation, which captures the notion of potential causality by relating an operation to previous operations by the same process, and to operations on other processes whose effects could have been visible thanks to messages exchanged between those processes.
This was formalized into a multiprocessor memory model in a 1993 paper by Ahamad, Neiger, Burns, et al, but a more useful (and non-paywalled) reference might be Mahajan, Alvisi, and Dahlin’s Consistency, Availability, and Convergence, which takes a history (called “an execution”) composed of read and write operations, asks for a directed acyclic happens-before relation over that execution, and requires that happens-before…
Mahajan et al leave conflict resolution (what to do with concurrent writes) up to the implementation, requiring only that all concurrent writes are returned for a read.
A more concise definition, from Viotti and Vukolić, decomposes causal consistency into three properties: