24

Can anyone explain me the definitions and differences between sequential consistency and quiescent consistency? In the most dumb form possible :|

I did read this: Example of execution which is sequentially consistent but not quiescently consistent

But I am not able to understand Sequential and quiescent consistency itself :(

Community
  • 1
  • 1
  • 1
    See: http://coldattic.info/shvedsky/pro/blogs/a-foo-walks-into-a-bar/posts/88 – jessehouwing Sep 28 '14 at 21:23
  • 2
    Quiescent consistency means that a data structure is considered consistent after an operation is executed on it and before another is executed on it (i.e. in the "quite" time). Sequential consistency means that the structure remains consistent regardless what order operations are performed on it from different threads. – Peter Ritchie Sep 28 '14 at 23:01

2 Answers2

30

Sequential consistency requires that the operations should appear to take effect in the order they are specified in each program. Basically it enforces program order within each individual process, and allows all processes to assume they are observing the same order of operations. Let's say we have 2 processes enqueuing and dequeuing items on a queue q:

P1 -- q.enq(x) ----------------------------- 
P2 -------------- q.enq(y) ---- q.deq():y --

This is not the expected behaviour from a FIFO queue. We'd expect to dequeue x because P1 enqueues x before P2 enqueues y. However this scenario is allowed in the sequential consistency model because sequential consistency doesn't require that the order seen by all processes is correct (real-time order). There's at least one sequential execution that can explain these results and one is:

P2:q.enq(y) P1:q.enq(x) P2:q.deq():y

In this execution each process executes operations in program order meaning each process executes its operations in the order they're specified in each process.

Quiescent consistency requires non-overlapping operations to appear to take effect in their real-time order, but overlapping operations might be reordered. Therefore, the same scenario is not allowed in the quiescent consistency model because we expect q.enq(x) to appear to take effect before q.enq(y), and q.deq() to return x instead of y. Also quiescent consistency doesn't necessarily preserve program order. If q.enq(x) and q.enq(y) would be concurrent (overlapping) operations, they could be reordered and q.deq():y would be quiescently consistent.

Basically some executions are sequentially consistent but not quiescently consistent, and vice versa.

Selim Ekizoglu
  • 519
  • 5
  • 6
  • Note that nonoverlapping events need not be separated by a period of quiescence. So, the characterization of quiescent consistency is too strong: it should allow nonoverlapping events to be reordered (provided some method call remains pending throughout the interval between them). – mmw Feb 18 '20 at 15:25
  • "Basically it enforces program order within each individual process" It doesn't. It enforces executions that could be fully explained by at least one interleaving of threads running in program order, which is different from what you described (note how that would prevent any kind of compiler optimization). – devoured elysium Jul 25 '21 at 16:20
2

First you should understand what is program order, it is literally how you expect your program runs in the order of the appearance of instructions.

But a program order is only for a single thread program, if you have multithreads, then problem comes as the program order may not hold or even not exist as sometimes you cannot tell which thread's method call happens first.

A quiescent consistency describes a clear program order of all threads' behaviors. that is no overlaps are allowed since it is required a quiescent period between two method calls.

A sequential consistency allows overlaps, but requires one can find a program order in which all the method calls can be put in a place and still returns correct value and behaves correctly.

elexonics
  • 35
  • 7
  • 1
    Well when you say "quiescent consistency describes a clear program order" it means that program method calls separated by quiescent points appear complete to other. As in ------- (quiescent period) ------ -- . The calls made in set 'a' by multiple threads will be completed and will be visible to the calls in method call set 'b' as complete. –  Nov 04 '14 at 22:44
  • 1
    Sequential consistency has more to do with the program order of a thread. Calls within the thread need to be in the program order. The overlapping calls of other threads can be moved around as one wishes. However the movement cannot change the program order of the other thread. i.e Overlapping/non overlapping calls between two threads can be reordered as one wishes keeping the program order of each thread intact. –  Nov 04 '14 at 22:50