Serializability vs Linearizability

In today (well.. already yesterday..)’s tiny group meeting, this question is raised. And I remember I’ve asked the exactly same question to Gustavo before! :)

The question is about the difference between serializability & linearizability. I checked my notes after meeting, it was 01/17/2014, which is more than 1.5 years now. I am really thankful to Gustavo’s mentoring!

Below is from my note, since I may not record everything correctly at that time, if you find anything wrong, please just point it out! Thanks in advance.

Difference

Assume a stack, pop() has 3 instructions inside, and push() has 4 instructions inside. e.g.

pop():   —>          —>             —>
push():        —>          —> —>           —>

It would be best if we could consider them as this: (sequential consistency)

—>—>—> pop()
                          —>—>—>—> push()

or

—>—>—>—> push()
                                 —>—>—> pop()

In this case there is now only 2 possibilities, either first push() then pop() or first pop() then pop(). It’s much easier.

If:

...push(4)       —>—>—>—> push(5)
                                                           —>—>—> pop(4)

Here, pop(4) means pop() with value 4 returned. So the pop(4) should be incorrect, cause apparently it should return value 5.

BUT Serializability says it’s OK to have pop(4). If this is acceptable, the whole execution is actually regarded as push(4), pop(4), push(5), which throws all the information about time!

While Linearizability won’t accept this. Linearizability respects the time information, if push(5) finishes before pop(4) starts, then they cannot be reordered. It has some kind of linearization point, think of it as the exact instruction that changes the state. If in the following case: ( star below is to the left of star above)

—>—>—>*—>
    —>*—>—>

where ‘*’ represents the linearization point, it is then equivalent as:

—>*—>—>
                                                          —>—>—>*—>

since the order of linearization points is still maintained.

One good thing about Linearizability is that it is compositional. If A is linearizable and B is linearizable, then the composition of A and B is also linearizable. But for Serializability this is not the case. This property is very good because it allows modular checking!