15

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.enter image description here

user23
  • 415
  • 1
  • 8
  • 22

1 Answers1

11

An execution e of operations is sequentially consistent if and only if it can be permutated into a sequence s of these operations such that:

  • the sequence s respects the program order of each process. That is, for any two operations o1 and o2 which are of the same process and if o1 precedes o2 in e, then o1 should be placed before o2 in s;

  • 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 from P3 require that W(x)b come before W(x)a

  • the operations R(x)a, R(x)b from P4 require that W(x)a come before W(x)b

It is impossible to construct such a sequence s.

Anshuman Kumar
  • 464
  • 1
  • 6
  • 20
hengxin
  • 1,867
  • 2
  • 21
  • 42
  • 1
    Second point is a bit misleading. A read operation on the process that wrote the value should return it's written value or anything newer (as soon as it returns newer value, it can't return older values anymore). On any other processes, reads can return older values, as long as it complies with write order (it doesn't traverse time backward). So for example, in case (C), R(x) on P1 can return "a", but if it returns "b", then from that point onward, it can't return "a" anymore. – Majid Azimi Jun 12 '18 at 13:10
  • As more info, please take a look at [here](https://cs.gmu.edu/~setia/cs707/slides/consistency.pdf). Slide number 8 says: "Definition of sequential consistency says nothing about time -- **there is no reference to the most recent write operation**" – Majid Azimi Jun 12 '18 at 13:23
  • This [link](https://www.e-reading.club/chapter.php/143358/218/Tanenbaum_-_Distributed_operating_systems.html), also corroborates my comment. Specially the first figure. – Majid Azimi Jun 12 '18 at 13:31
  • @MajidAzimi Yes, it does not refer to time. However, it does refer to a total order/permutation/sequence of operations based on which the notion of "the most recent" is well-defined. – hengxin Jun 12 '18 at 14:01
  • Why the operations R(x)b, R(x)a from P3 require that W(x)b come before W(x)a? – noobcoder Dec 09 '19 at 01:25