Linearizability

Distributed/networked systems employ data replication to achieve availability and scalability. Consistency is concerned with the question of what should happen if a client modifies some data items and concurrently another client reads or modifies the same items possibly at a different replica.

Linearizability is a strong form of consistency. (That is why it is also called as strong-consistency.) For a system to satisfy linearizability, 

• each operation must appear (from client perspective) to occur at an instantaneous point between its start time (when the client submits it) and finish time (when the client receives the response), and 
• execution at these instantaneous points should form a valid sequential execution (i.e., it should be as if operations are executed one at a time ---without concurrency, like they are being executed by a single node) 

Let's simplify things further. In practice, consistency is often defined for systems that have two very specific operations: read and write. If the write operations are destructive, rather than cumulative write/update, defining linearizability becomes even are more straightforward.  

Linearizability (i.e., strong consistency) ensures that a read operation returns the value that was last written for a given object. 

But we don't know when the write (or read) actually takes effect (that is hidden from us). We only know that it has to take effect atomically between invocation and response of the corresponding operation. And that still makes things interesting/nontrivial for linearizability checking.

Examples

I will use the same color to match request response pairs. 

PUT-req(k1,a), PUTresp(k1,a)

Let's start with a basic example. This is a client view of the system. The PUT execution should take "effect" in between the invocation PUT-req(k1,a) (which requests the system to PUT the value a to the key k1) and the response received from the system PUTresp(k1,a) (which acknowledges that the PUT request has been completed for value a on key k1).

PUTreq(k1,a), PUTresp(k1,a), PUTreq(k1,b), GETreq(k1), GETresp(k1,a)

Is this linearizable?

Yes, because PUTreq(k1,b) has not been responded yet, and it is possible that it might not have taken effect when GET is actually executed (when GET takes effect on the system side).

PUTreq(k1,a), PUTresp(k1,a), PUTreq(k1,b), GETreq(k1), GETresp(k1,b)

Is this linearizable?

Yes, because it is possible that the PUTreq(k1,b) might have taken effect before GET is executed.

Notice that for the same prefix of visible operations, both GETresp(a) and GETresp(b) were valid responses in a linearizable system. 

PUTreq(k1,a), PUTresp(k1,a), PUTreq(k1,b), GETreq(k1), GETresp(k1,NULL)

Is this linearizable?

No, because we know PUT(k1,a) has definitely taken effect. We have seen the response. So, GET cannot return NULL (no value). There has not been a delete in between either.

PUTreq(k1,a), PUTresp(k1,a), PUTreq(k1,b), GETreq(k1), GETresp(k1,b), GETreq(k1), GETresp(k1,a)

Is this linearizable?

No. The first GET response has established that the system had seen the effects of PUT(k1,b), and we cannot revert back on that in a linearizable system.

PUTreq(k1,a), GETreq(k1), GETresp(k1,a), PUTreq(k1,b), PUTresp(k1,b), PUTresp(k1,a),  GETreq(k1), GETresp(k1,?)

What should be the value returned in the last GETresp(k1,?) in a linearizable system? The last PUT response returned (from client perspective) is PUTresp(k1,a). But we don't evaluate linearizability based on what is the last PUT response seen. We need to evaluate it in terms of which put has "taken effect" most recently. Is it possible for PUT(a) to happen (take effect) after PUT(b)? No, that is ruled out by the GETresp(k1,a) that the client has seen (similar to the previous example). So the latest PUT to take effect in a sequential execution would be PUT(b), and the linearizable system should return GETresp(k1,b).

What if that first GET was not there? Without that observation point, which pinned down a result, would there be a constraint in the final GET? What would be acceptable results a linearizable system could return in that case? 

PUTreq(k1,a), PUTreq(k1,b), PUTresp(k1,b), PUTresp(k1,a),  GETreq(k1), GETresp(k1,?)

Returning a would be acceptable, because it is possible that PUT of a might have taken effect after PUT of b. Returning b would also be acceptable, because it is possible that on the system side PUT of b might have taken effect after PUT of a. Returning NULL would not be possible because we have a value (even though we don't know whether it is a or b that is the latest) that has been PUT for the key.