CODEWITHSUNDEEP
concurrencyconsistency
sunil
sunil

Reputation: 701

What are the differences between Linearizability and quiescent consistency?

I am reading a book "The Art of Multiprocessor Programming by Maruice Herilihy and Nir Shavit and am trying to understand Chapter 3 about Concurrent Objects"

Linearizability : "The basic idea behind linearizability is that every concurrent history is equiv- alent, in the following sense, to some sequential history. The basic rule is that if one method call precedes another, then the earlier call must have taken effect before the later call. By contrast, if two method calls overlap, then their order is ambiguous, and we are free to order them in any convenient way."

Now,I was reading about quiescent consistency,

Method calls should appear to happen in a one-at-a-time, sequential order.

Method calls separated by a period of quiescence should appear to take effect in their real-time order.

I feel like both are same. I read this What are the differences between sequential consistency and quiescent consistency?.

from above link

Quiescent consistency : "requires non-overlapping operations to appear to take effect in their real-time order, but overlapping operations might be reordered"

can anybody explain how both are different ?

Thanks.

Upvotes: 3

Views: 929

Answers (1)

user5704060
user5704060

Reputation:

Quiescent consistency is a weaker constrain than linearizability. For example there are 3 concurrent method calls.

<---A---> <---B--->
  <------C------>

For linearizability, you can map the concurrent execution to sequential ones such as ABC, ACB, CAB etc. But you CAN NOT put B before A because the precedence order must be preserved.

This is not the case in quiescent consistency, you can reorder A and B since there is no quiescent point in between A and B (because C is pending). In another word, you can reorder the method calls in any manner you like as long as there is no quiescent points separating them.

Upvotes: 4

Related Questions