[<<][compsci][>>][..]
Sat Oct 24 10:28:13 CEST 2009

Linearizability

From [1]

  Linearizability provides the illusion that each operation applied by
  concurrent processes takes effect instantaneously at some point
  between its invocation and its response, implying that the meaning
  of a concurrent object's operations can be give by pre- and
  post-conditions.

Maybe better is The art of multiprocessor programming[2], chapter 3
about Concurrent objects.

Quiescent Consistency: any time an object becomes quiescent, then
execution so far is equivalent to some sequential execution of the
completed calls.

I.e.

  A---
   B----
    C--
         D--
..      .   ..

This can mean all possible permutations of A,B,C followed by D,
because there is no quiescent time among the invocations of A,B,C but
all of them are separated from D.

QC doesn't necessarily respect program order (= single thread's
sequential order)

Sequential Consistency: In any concurrent execution, there is a way to
order the method calls sequentially such that they (1) are consistent
with program order and (2) meet the object's sequential specification.

SC is _not_ composable.  QC and SC conditions are incomparable.

Linearizability: each method call should appear to take effect
instantaneously at some moment between its invocation and response.

L => SC.







[1] http://www.cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf
[2] isbn://0123705916



[Reply][About]
[<<][compsci][>>][..]