I am learning Sequential Consistency in Distributed Systems but just could not understand the terms explained. I would appreciate if someone can shed some light in layman's term on why (a) and (c) below are sequentially consistent and (b) is not.
Thanks.
Sequential Consistency in Distributed Systems
6.9k views Asked by user23 At
1
An execution
e
of operations is sequentially consistent if and only if it can be permutated into a sequences
of these operations such that:the sequence
s
respects the program order of each process. That is, for any two operationso1
ando2
which are of the same process and ifo1
precedeso2
ine
, theno1
should be placed beforeo2
ins
;in the sequence
s
, each read operation returns the value of the last preceding write operation over the same variable.For (a),
s
can be:W(x)b [P2], R(x)b [P3], R(x)b [P4], W(x)a [P1], R(x)a [P3], R(x)a [P4]
For (c),
s
can be:W(x)a [P1], R(x)a [P2], R(x)a [P3], R(x)a [P4], W(x)b [P3], R(x)b [P1], R(x)b [P2], R(x)b [P4]
However, for (b):
the operations
R(x)b, R(x)a
fromP3
require thatW(x)b
come beforeW(x)a
the operations
R(x)a, R(x)b
fromP4
require thatW(x)a
come beforeW(x)b
It is impossible to construct such a sequence
s
.