Linearizability and Serializability in context of Software Transactional Memory

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

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.

StackExchange Computer Science Q#41698, answer score: 6