What is "Linearizability"?

multithreading concurrency parallel-processing thread-safety linearizability
unnknown picture unnknown · Mar 18, 2012 · Viewed 11.3k times · Source

Can anyone out there help me understand what Linearizability is? I need an explanation that is simple and easy to understand. I'm reading The Art of Multiprocessor Programming by Maruice Herilihy and Nir Shavit and am trying to understand Chapter 3 about Concurrent Objects.

I understand that a method is Linearizable if it has a point where it seems to "take effect" instantaneously from the point of view of the other threads. That makes sense, but it is also said that Linearizability is actually a property of the execution history. What does it mean for an execution history to be Linearizable, why do I care, and how does it relate to a method or object being Linearizable?

Thank you!

Answer

Vlad Mihalcea picture Vlad Mihalcea · Jun 2, 2018

As I explained in this article, a picture is worth 1000 words.

enter image description here

The first SELECT statement reads the value of 50, while the second SELECT reads the value of 10 since in between the two read operations a write operation was executed.

Linearizability means that modifications happen instantaneously, and once a registry value is written, any subsequent read operation will find the very same value as long as the registry will not undergo any modification.

What happens if you don't have Linearizability?

enter image description here

This time, we don’t have a single registry or a single source of truth. Our system uses asynchronous database replication, and we have a Primary node that takes both reads and writes and a Follower node used for read operations only.

Because replication happens asynchronously, there’s a lag between the Primary node row modification and the time when the Follower applies the same change.

One database connection changes the account balance from 50 to 10 and commits the transaction. Right after, a second transaction reads from the Follower node, but since replication did not apply the balance modification, the value of 50 is read.

Therefore, this system is not linearizable since changes don’t appear to happen instantaneously. In order to make this system linearizable, we need to use synchronous replication, and the Primary node UPDATE operation will not complete until the Follower node also applies the same modification.

Related questions

How to wait for all threads to finish, using ExecutorService?

I need to execute some amount of tasks 4 at a time, something like this: ExecutorService taskExecutor = Executors.newFixedThreadPool(4); while(...) { taskExecutor.execute(new MyTask()); } //...wait for completion somehow How can I get notified once all of them are complete? For now …

Read More
Concurrency: Atomic and volatile in C++11 memory model

A global variable is shared across 2 concurrently running threads on 2 different cores. The threads writes to and read from the variables. For the atomic variable can one thread read a stale value? Each core might have a value of the …

Read More
How to pause/resume all threads in an ExecutorService in Java?

I submitted bunch of jobs to an executorservice in Java and I somehow want to temporarily pause all these jobs. What's the best way to do this? How can I resume? Or am I doing this completely wrong? Should I …

Read More