Paper reading: Causal consistency | causal memory

May 20, 2021

1. Traditional memory consistency? 
2. causal memory, an abstraction that ensures that processes in a system agree on the relative ordering of operations that are causally related
3. Because causal memory is weakly consistent, it admits more executions, and hence more concurrency, than either atomic or sequentially consistent memories
4. 
   

Causal Memory: 

Definitions, Implementation and Programming 

Mustaque Ahamad 

Gil Neiger 

James E. Burnsy 

Prince Kohli 

Georgia Institute of Technology 

Phillip W. Huttox 

GIT{CC{93/55 

September 17, 1993 

Revised: July 22, 1994 

Abstract 

The abstraction of a shared memory is of growing importance in distributed computing systems. Traditional memory consistency ensures that all processes agree on a common order of all operations on memory. Unfortunately, providing these guarantees entails access latencies that prevent scaling to large systems. This paper weakens such guarantees by defining causal memory, an abstraction that ensures that processes in a system agree on the relative ordering of operations that are causally related. Because causal memory is weakly consistent, it admits more executions, and hence more concurrency, than either atomic or sequentially consistent memories. This paper provides a formal definition of causal memory and gives an implementation for message-passing systems. In addition, it describes a practical class of programs that, if developed for a strongly consistent memory, run correctly with causal memory. 

1 Introduction 

The abstraction of a shared memory is of growing importance in distributed computing systems. It allows users to program these systems without concerning themselves with the details of the underlying message-passing system. Traditionally, distributed shared memories ensure that all processes in the system agree on a common order of all operations on memory. Such guarantees are provided by sequentially consistent memory [27] and by atomic memory [28] (also called linearizable memory [20]). Unfortunately, providing these consistency guarantees entails access latencies that prevent scaling to large systems. A simple argument [10,29] can be used to show that no memory can provide strong consistency and retain low latency in systems with high message-passing delays. This tradeoff represents a significant effciency problem since it forces applications to pay the costs of consistency even if they are highly parallel and involve little synchronization. A number of techniques [11,24] have been suggested to improve the effciency of shared memory implementations, but all provide only partial remedies to the fundamental problem of latency and scale for strongly consistent memories. 

Recent research [1,6,9,16{18,21,29] suggests that a systematic weakening of memory consistency can reduce the costs of providing consistency while maintaining a viable target" model for programmers. Weakly consistent memories admit more executions, and hence more concurrency, than either sequentially consistent or atomic memories. This paper defines causal memory, an abstraction that ensures that processes in a system agree on the relative ordering of operations that are causally related. (Causal memory has been mentioned earlier [6,21]; however, these papers do not present careful definitions as is done here.) This paper provides a formal definition of causal memory and gives an implementation for message-passing systems. We give two classes of programs that can be developed assuming a sequentially consistent memory and that run correctly with causal memory.

Causal memory is based on Lamport's concept of potential causality [26]. Potential causality provides a natural ordering on events in a distributed system where processes communicate via message passing. We introduce a similar notion of causality based on reads and writes in a shared memory environment. Causal memory requires that reads return values consistent with causally related reads and writes, and we say that "reads respect the order of causally related writes." Since causality orders events only partially, reading processes may disagree on the relative ordering of concurrent writes. This provides independence between concurrent writers which reduces consistency maintenance (synchronization) costs. The idea is that the synchronization required by a program is often specified explicitly and it is not necessary for the memory to provide additional synchronization guarantees.

Causal memory is related to the ISIS causal broadcast and, thereby, to the notion of causally ordered messages [13]. Our implementation of causal memory is based on the use of vector timestamps [14,30], as is the ISIS implementation of causal broadcast. Both implementations are "non-blocking": a process may complete an operation (e.g., a write or a send) without waiting for communication with other processes. Nevertheless, causal memory is more than a collection of "locations" updated by causal broadcasts. Memory has overwrite semantics and messages have queuing semantics. A message recipient can be assured that it will eventually receive all messages that have been sent to it, but repeated reads cannot guarantee that all values written will be read. "Hidden writes", values overwritten before they are read, are always possible. Since a process may read memory locations in any order it chooses, it may read a value v1 from location x much later than a value v2 from location y, even when the write operation that stores v1 in x is causally before the write of v2 to y. In a message-passing system, such behavior would violate the required causal ordering.

We give precise characterizations of two classes of programs that run correctly with causal memory. Any execution a program in either of these classes with causal memory is actually sequentially consistent. If the program is proven correct with sequential consistent memory, then it is still correct with causal memory. One of these classes includes data-race free programs [1,2] that make use of explicit synchronization to prevent problems that may stem from concurrent access to shared memory. 

It is far from clear that there is a "best" kind of shared memory model for use with distributed systems. Strongly consistent memories are easier to program than weak memories, but they require costly blocking implementations. Very weak memories may be implemented cheaply, but they might not be practical to program. We believe that causal memory provides a happy medium: it allows non-blocking implementations and is a useful model for a class of practical programs.