Sat Oct 24 10:28:13 CEST 2009
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
Maybe better is The art of multiprocessor programming, 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
.. . ..
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 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.