## 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**- denotes that_{i}(x)a**P**writes value_{i}**a**to data item**x**.**R**represents the fact that process Pi reads x and is returned the value b._{i}(x)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**on x._{1}(x)a - Later (in absolute time), process P2 also performs a write operation
**W**, by setting the value of x to b._{2}(x)b - However, both processes P3 and P4 first read value b, and later value a.
- In other words, the write operation
**W**of process P2 appears to have taken place before_{2}(x)b**W**of P1._{1}(x)a

- Process P1 first performs
- 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:

**P1:**W(x) 1

**P2:**R(x) 0; R(x) 1**P1**: W(x) 1

**P2**: R(x) 1; R(x) 0**P1**: W(x) 1

**P2**: W(x) 2

**P3**: R(x) 1; R(x) 2**P1**: W(x) 1

**P2**: W(x) 2

**P3**: R(x) 2; R(x) 1**P1**: W(x) 1

**P2**: W(x) 2

**P3**: R(x) 2; R(x) 1

**P4**: R(x) 1; R(x) 2**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**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:

**Solution:**They are sequentially consistent. They can be executed as follows:

**P2**: R(x) 0;

**P1**: W(x) 1;

**P2**: R(x) 1**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.**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