Hajussüsteemid 2020/21 kevad

Seminar 9: Sequential Consistency

Goal:

• To look at Sequential Consistency, one of the consistency Models.
• To Check for Sequential Consistency in a set of execution steps

---

Definitions:

• A consistency model is essentially a contract between processes and the data store.
• It says that if processes agree to obey certain rules, the data store promises to work correctly.
• Normally, a process that performs a read operation on a data item, expects the operation to return a value that shows the results of the last write operation on that data.
• Sequential consistency is an important data-centric consistency model, which was first defined by Lamport in the context of shared memory for multiprocessor systems.
• A data store is said to be sequentially consistent when it satisfies the following condition:
  • The result of any execution is the same as if the (read and write) operations by all processes on the data store were executed in some sequential order and the operations of each individual process appear in this sequence in the order specified by its program.
• Sequential Consistency uses a special notation in which we draw the operations of a process along a time axis.
• The time axis is always drawn horizontally, with time increasing from left to right.
• Notation:
  • W_i(x)a - denotes that P_i writes value a to data item x.
  • R_i(x)b represents the fact that process Pi reads x and is returned the value b.
• Assumption: Each data item has initial value NIL.
• When there is no confusion concerning which process is accessing data, we omit the index from the symbols W and R.

From the Figure:

• Time does not play a role in Sequential consistency.
• In Figure (a):
  • Process P1 first performs W₁(x)a on x.
  • Later (in absolute time), process P2 also performs a write operation W₂(x)b, by setting the value of x to b.
  • However, both processes P3 and P4 first read value b, and later value a.
  • In other words, the write operation W₂(x)b of process P2 appears to have taken place before W₁(x)a of P1.
• In Figure (b):
  • There is a violation of sequential consistency because not all processes see the same interleaving of write operations.
  • To process P3, it appears as if the data item has first been changed to b, and later to a.
  • On the other hand, P4 will conclude that the final value is b.

---

EXERCISE

• Assuming that all variables are initially set to 0:

1. P1: W(x) 1
   P2: R(x) 0; R(x) 1
2. P1: W(x) 1
   P2: R(x) 1; R(x) 0
3. P1: W(x) 1
   P2: W(x) 2
   P3: R(x) 1; R(x) 2
4. P1: W(x) 1
   P2: W(x) 2
   P3: R(x) 2; R(x) 1
5. P1: W(x) 1
   P2: W(x) 2
   P3: R(x) 2; R(x) 1
   P4: R(x) 1; R(x) 2
6. P1: W(x) 1; R(x) 1; R(y) 0
   P2: W(y) 1; R(y) 1; R(x) 1
   P3: R(x) 1; R(y) 0
   P4: R(y) 0; R(x) 0
7. P1: W(x) 1; R(x) 1; R(y) 1
   P2: W(y) 1; R(y) 1; R(x) 1
   P3: R(y) 1; R(x) 0

For the above executions:

• Please indicate if they are sequentially consistent.
• If an execution is not sequentially consistent, then show the right execution that makes it sequentially consistent (explain how you achieved that)

---

---

The first three have been done for you:

1. Solution: They are sequentially consistent. They can be executed as follows:
   P2: R(x) 0;
   P1: W(x) 1;
   P2: R(x) 1
2. Solution: Not sequentially consistent, as we cannot read x as 0 after we write 1, and if we don’t write 1 to x we cannot read 1 from x.
   Right Execution: Make P2: R(x) 0; R(x) 1; instead of P2: R(x) 1; R(x) 0; thus we can have same solution as 1.
3. Solution: Sequentially consistent.
   Can be executed as follows:
   P1: W(x) 1;
   P3: R(x) 1;
   P2: W(x) 2;
   P3: R(x) 2;

---

Deliverables of practical session: A PDF file containing the answers to above exercise

---

Referrences:

• Distributed Systems, Third edition, Version 3.02 (2018) by Maarten van Steen and Andrew S. Tanenbaum

---