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 transactionTk
concurrently, 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
ordequeue
on aQueue
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