Linearizability and Serializability in context of Software Transactional Memory

Question

I've been trying to grasp serializability and linearizability in the context of software transactional memory. However, I think both notions can be applied to transactional memory in general.

At this point, the following is my understanding of both subjects.

Serializability

Serializability is a global property. It is a correctness property of transactions. Given k processes that each execute a transaction Tkconcurrently, serializability ensures that there is a sequence of transactions that can be executed in sequence (i.e., one after the other) such that the end result is the same as the transactions being executed concurrently. So there is a permutation of the list (T1, T2,..,Tk) that defines a list of transactions that can be executed sequentially.

This property makes perfect sense to me and I think my definition is correct. I based this definition on the text in "The Art of Multiprocessor programming" by Herlihy and Shavit.

Linearizability

Linearizability is a local property of concurrent objects (e.g., an instance of a class that is shared amongst threads). Linearizability ensures that when two processes each execute a series op method calls (e.g., queue or dequeue on a Queue instance) on that shared object there is a sequential ordering of these method calls that does not necessarily preserve program order (the order in which the programmer wrote them down), but each method call does seem to happen instantly (i.e., invocation and response follow each other directly), whilst maintaining the result of each method call individually and consequently the object its state.

Question

According to a paper "On the correctness of TM" by Guerraoui and Kapalka this is the definition of linearizability in context of TM:

.. a safety property devised to describe shared objects, is sometimes used as a correctnes criterian for TM. In the TM terminology linearizability means that intuitively, every transaction should appear as if it took place at some single unique point in time during its lifespan.

This definition just seems to resemble serializability to me. But the paper further on defines serializability as follows:

.. is one of the most commonly required properties of a database transaction. Roughly speaking, a history H of transactions (i.e., the sequence of all operations performed by all transactions in a given execution) is serializable if all committed transactions in H issue the same operations and receive the same responses as in some sequential history S that consists of only the committed transactions in H. (A sequential history is one without concurrency between the transactions).

This definition however seems to imply that one can reorder statements from transactions in such a way that they are interleaved. (I.e. reorder the statements such that not all the statements of a transaction T appear in sequence in H).

---

I am under the assumption that my personal above definitions are correct. My actual question is how linearizability is defined in the context of transactional memory. It makes no sense to reason about each method call (i.e., read/write operation) in a transaction individually as this would break the semantic of transactional memory. Nor would it make sense to having to reason about two concurrent transactions their interleavings, as this would obviously break serializability. Does linearizability mean that one can reorder individual operations inside a transaction? If linearizability is a stronger form of serializability, it should not matter in which order the operations are executed inside a single transaction.

In short: First of all, is my understanding of serializability and linearizability correct? I am confused after reading a plethora of definitions in different works. And second, what does it mean for a set of transaction to be linearizable?

I have also read the question that was linked inside of the comments. But it did not explain to me my specific question.

Sources

• SO question on the topic (not about STM explicitly) https://stackoverflow.com/questions/4179587/difference-between-linearizability-and-serializability

• An informal explanation about the two http://www.bailis.org/blog/linearizability-versus-serializability/

• Original paper on serializability http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.2690&rep=rep1&type=pdf

• [1] Original paper on linearizability http://www.cs.toronto.edu/~christoff/files/Linearizability-ACorrectnessConditionForConcurrentObjects.pdf

Answer 1

About your definitions:

The basic idea of Serializability ($\textsf{SR}$) is correct. However, it does not have to constrain itself on the your assumption that each (process) executes a transaction: Every process can issue as many transactions as they want.

Your understanding of Linearizability ($\textsf{LR}$) is quite wrong. First, for both $\textsf{SR}$ and $\textsf{LR}$, program order between transactions issued by a single process must be preserved. Furthermore, you cannot reorder any operations within a transaction.

Explaination of $\textsf{SR}$ and $\textsf{LR}$:

Both $\textsf{SR}$ and $\textsf{LR}$ require all the transactions to behave as if they were executed in some sequential order $H$, meaning that in such a sequential order, all reads operations return the same values and the end states of the database is the same as those when the transactions are being executed concurrently.

As mentioned before, for both $\textsf{SR}$ and $\textsf{LR}$, program order between transactions issued by a single process must be preserved.

The above gives the difinition of $\textsf{SR}$. However, $\textsf{LR}$ further requires the sequential order $H$ to obey the so-called real-time (partial) order between transactions: If a transaction $T_1$ ends before another transaction $T_2$ starts, then $T_1$ must be ordered before $T_2$ in $H$.

Notice that $\textsf{SR}$ does not enforce the real-time order. That is to say, $\textsf{LR}$ is stronger than $\textsf{SR}$.

About global property and local property:

I don't know whether $\textsf{SR}$ is called a global property (please give me some reference if you are sure about this). However, the term "local property" has its special meaning.

A property $P$ of a concurrent system is said to be local if the system as a whole satisfies $P$ whenever each individual object satisfies $P$.

It is known that $\textsf{LR}$ is local [1] while $\textsf{SR}$ is not.

ADDED: About LR and Strict Serializability (SSR)

As mentioned by @Wandering Logic, LR is originally defined for objects, not for transactions. Quoted from [1]；

Linearizability can be viewed as a special case of strict serializability where transactions are restricted to consist of a single operation applied to a single object.

However, nowadays, many authors have used $\textsf{LR}$ for transactions. For instance, in their seminal paper [2], Shavit and Touitou used the term $\textsf{LR}$ for transactions. When used for transactions, $\textsf{LR}$ is the same as $\textsf{SSR}$.

Thanks @Wandering Logic for the discussions.

---

[1] Linearizability: A Correctness Condition for Concurrent Objects. By M P. Herlihy and J M. Wing. ACM Transactions on Programming Languages and Systems, Vol. 12, No. 3, July 1990.

[2] Software Transactional Memory. By Nir Shavit and Dan Touitou. Distrib. Comput. (1997) 10: 99-116.

Answer 2

Your definition of serializability is correct, and equivalent to the definition of Guerraoui and Kapalka that you quote. Guerraoui and Kapalka's definition, like yours, requires all the instructions inside transaction $T_k$ to appear to execute and to execute in order. That is: the end result is as if you had executed the transactions atomically and in some sequential order. (The implementation may be optimized with some crazy concurrent, parallel, out-of-order execution scheme, but the result has to look as if you ran all the transactions in some sequential order and with no interleaving.)

Serializability talks about the behavior of transactions without taking into consideration the processes or threads that issued those transactions. (In your definition you have exactly as many processes as transactions, and each process issues exactly one transaction.)

Linearizability takes into account the fact that each thread will issue multiple transactions, and we expect those transactions to execute and complete in the order we asked them to issue.

A transactional memory system is strictly serializable if the end result of any execution is the same as if the transactions of all the processes were executed atomically in some sequential order, and the transactions issued by each individual process appear in this sequence in the order specified by the program of that process.

(This is the definition of sequential consistency from Lamport, "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs", IEEE T Comp 28(9):690-691, 1979, but modified to talk about transactions instead of memory operations. Herlihy and Wing call this property strict serializability.)

The original paper by Herlihy and Wing that defines linearizability was about operations on objects, not transactions. But, the following connects the two concepts:

Linearizability can be viewed as a special case of strict serializability where transactions are restricted to consist of a single operation applied to a single object.

(Herlihy, Maurice; Wing, Jeanette: Linearizability: A Correctness Condition for Concurrent Objects. ACM T. Prog. Lang. and Sys. 12(3):463-492, 1990.)