What are the differences between sequential consistency and quiescent consistency?

sequential consistency
user4089193 picture user4089193 · Sep 28, 2014 · Viewed 7.3k times · Source

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 :(

Answer

Selim Ekizoglu picture Selim Ekizoglu · Aug 11, 2016

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.

Related questions

Resolve promises one after another (i.e. in sequence)?

Consider the following code that reads an array of files in a serial/sequential manner. readFiles returns a promise, which is resolved only once all files have been read in sequence. var readFile = function(file) { ... // Returns a promise. }; var readFiles = …

Read More
How do I call a function twice or more times consecutively?

Is there a short way to call a function twice or more consecutively in Python? For example: do() do() do() maybe like: 3*do()

Read More
Notepad++ incrementally replace

Lets say I want to have a 10 rows of data but I want a value to increment for each row or piece of data. How do I increment that value? For example....If I have these rows, is there a …

Read More