Hajussüsteemid 2021/22 kevad

Seminar 9: Sequential Consistency

Goal: To study and practice Sequential Consistency conceptually in distributed system

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

• 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.
  • execution order of program in the same processor (or thread) is the same as the program order, while execution order of program between processors (or threads) is undefined.
• 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 - denotes that process P_i reads data item x returning the value b.
  • Assumption: Each data item has initial value NIL.

From the Figure:

• Time does not play a role in Sequential consistency.
• In Figure (a) -- Sequentially consistent data store:
  • If 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.
    • Contradiction -- data item x is now b
  • In other words, the write operation W₂(x)b of process P2 appears to have taken place before W₁(x)a of P1.
  • One sequential order: W₂(x)b -> R₃(x)b -> R₄(x)b -> W₁(x)a -> R₃(x)a -> R₄(x)a
• In Figure (b) -- Data store not sequentially consistent:
  • There is a violation of sequential consistency because not all processes see the same interleaving of write operations.
  • If Process P1 first performs W₁(x)a on x.
  • Then process P4 performs a read operation R₄(x)a
  • Next process P2 performs a write operation W₂(x)b, by setting the value of x to b.
  • After P3 performs a read operation R₃(x)b, then value a
    • Contradiction -- data item x is now b

Task Assuming that all variables are initially set to 0, for the below executions:

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

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; R(x) 2
   P2: R(x) 1; R(x) 2
   P3: R(x) 1; W(x) 2
   P4: R(x) 1; R(x) 2
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(x) 0; R(y) 1

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. They can be executed as follows:
   P1: W(x) 1;
   P3: R(x) 1;
   P2: W(x) 2;
   P3: R(x) 2;

Deliverables: A PDF file containing the answers to above exercise

Link:

• https://en.wikipedia.org/wiki/Sequential_consistency

NOTE: Please watch the video or ask us through Slack if something is not clear for you. We usually don't change the points after the deadline.