2
$\begingroup$

How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs

... the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program. A multiprocessor satisfying this condition will be called sequentially consistent.

Spanner docs:

Strong Consistency All accesses are seen by all parallel processes (or nodes, processors, etc.) in the same order (sequentially)5 In some definitions, a replication protocol exhibits "strong consistency" if the replicated objects are linearizable.

The 5 in that doc is a link to the wikipedia page, which apparently hasn't ever cited any sources. I can't seem to find any original source for it. The "some definitions" mentioned seem to be nowhere to find online.

What's the difference between strong and sequential consistency?

$\endgroup$
2

3 Answers 3

1
$\begingroup$

Let me describe sequential and then strong consistency to highlight the difference.

Sequential consistency implies that there is some order without any timing guaranties. For example, let's say we have a system where nodes have some state machines and these machines process some events.

In a sequentially consistent system, all these events have the same processing order - A,B,C,D - hence state machines execute exactly same sequence. But if you ask a specific node about its state - you can get any of those, as there is no timing guarantee. From a readers point of view - different nodes return different results.

But if a reader reads from one singe node, in a sequential system, the reader will see states in the same correct order: A,B,C,D - again - there is no timing guarantee when it will happen, but if it will, the order is set.

Imagine a counter in a sequentially consistent system - let's say the counter counts visitors on a website. Clearly the counter is always increasing. If a reader will keep reading the counter from the same node, they will see increasing counter - the counter never moves in an opposite direction. But reads from different nodes may give any results.

Keeping in mind a visitor counter example; what will make that system strongly consistent? This should be true:

  • after a counter increment happened
  • all next reads will see the new value

It's the same as - there is a point in time, when all reads will see the new value.

There are some details about reads being executed before the write ended (writes and read happening at the same time), I'll leave that for another post.

Edit: I woke up with a though to clarify sequential consistency

Sequential consistency has SOME order - this order will be respected on each node. So if I send three signals to a sequentially consistent system: A, B and C; there will be SOME order for these events to be processed - ABC, BCA, CBA... But whatever order will happen, the order will be the SAME everywhere.

In a sequential system order of events may not match real life order of events. In strongly consistent system the order will be predictable - sending events one by one A,B,C will create a processing order of A, B, C

$\endgroup$
1
$\begingroup$

In the case of the Spanner doc: it appears to be more strict than linearizability due to transactions. The difference between linearizability and sequential consistency is that latter doesn't need to preserve the real time ordering of requests.

https://jepsen.io/consistency/models/linearizable

The combination of linearizability and transactions is called strict serializability:

https://jepsen.io/consistency/models/strict-serializable

I'm not sure if spanner is supporting strict serializability.

$\endgroup$
1
$\begingroup$

This is sequential consistency:

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.