multithreading - Linearizability vs. Serializability -

from this, understand that

• linearizability , sequential consistency single operation on single object
• serializability , strict serializability multiple operations on multiple objects.

does single operation on single object mean following?

sequence 1:

t1: read(x) write(x)

t2: write(x) read(x)

whereas multiple operations , multiple objects mean:

sequence 2:

t1: read(y) write(x) read(y)

t2: write(y) read(x) write(y)

does mean that:

1. sequence 2 can reason execution of functions (or methods in java)?
2. sequence 1 can reason subset of operations on same object within function?

first of all, note consistent histories---according given consistency model, such linearizability or serializability---are defined satisfy sequential specifications of objects respect points of operation (or method) invocations [1, 2].

more specifically:

sequential specification object set of sequential histories object

where history defined as:

a finite sequence of method invocation , response events

where pair of invocation , response events form method call, i.e.:

a method call in history h pair consisting of invocation , next matching response in h

thus, indeed, linearizability defined single operations on single objects, definition can covers histories on multiple objects [1, 2]. on other hand, serializability covers histories multiple operations on multiple objects inherently, since (usually) defined in context of transactional processing, each transaction can involve multiple operations on multiple objects.

the two, namely single operations on single objects , multiple operations on multiple objects, can made equivalent through defining methods on objects (that potentially unify multiple objects) define appropriate sequential specification in whole transactions viewed methods on objects (e.g. simple example queue enqueue/dequeue [1]). this, in turn, defines sequential specification of such objects, , valid histories according given consistency models.

now, if t1 , t2 interpreted threads, indeed, sequence 1 invokes operations on single object, while sequence 2 invokes multiple operations , multiple objects. note in both cases, histories can checked respect both linearizability , serializability, while read , write operations might grouped "semantically" atomic methods discussed previously.

as per relationship between linearizability , serializability, serializability strictly weaker consistency model in valid histories might equivalent executions of methods in arbitrary sequences, while linearizability can viewed equivalent strict serializability (if view transactions methods of single object). note authors started using linearizability in context of transactions [3].

---

[1] the art of multiprocessor programming. nir shavit , m p. herlihy

[2] linearizability: correctness condition concurrent objects. m p. herlihy , j m. wing. acm transactions on programming languages , systems, vol. 12, no. 3, july 1990.

[3] software transactional memory. nir shavit , dan touitou. distrib. comput. (1997) 10: 99-116.