The University of Sydney Page 1
COMP3221: Distributed
Systems
Consistency
Unit Coordinator
Dr Nguyen Tran
School of Computer Science
The University of Sydney Page 2
Motivation
– Entities are distributed so they may act concurrently to update
some data
– Data may also be distributed (i.e., replicated) and not all
replicas can be accessed simultaneously
– What does it mean to be consistent?
The University of Sydney Page 3
Outline
– Definitions
– Sequential consistency
– Causal consistency
– Replication
– Multiple-access operations
The University of Sydney Page 4
Definitions
Consistency
The University of Sydney Page 5
Definitions
– Data is distributed (replicated) to
– Improve the reliability of a system
– Scale in numbers: preserve performance while multiplying entities
– Scale in geographical area: preserve performance while increasing space
– Drawback: cost of keeping the replicas consistent
– All replicas must have to maintain information
– Intuitively, a client update must be propagated to all replicas
– but a client can obtain an “up-to-date” information from any replica
– Not so simple!
– Propagation takes time and one replica may be up-to-date while another is
not
– Inconsistencies: two clients may observe a different data depending on the
replica they contact
Problem of inconsistency
The University of Sydney Page 6
Definitions
– Two (groups of) operations are concurrent in the traditional sense:
– Each of the two (groups of) operations starts before the other ends
– An update operation is an operation that modifies the data
– E.g., a write operation
– A conflict is a relation between two (groups of) operations:
– that are concurrent,
– access the same data, and
– (at least) one of which is an update
Conflict
The University of Sydney Page 7
Definitions
– A data store is a distributed collection of storages
– From the standpoint of a given process, only one storage copy
represents its local copy
Data store
The University of Sydney Page 8
Definitions
– A consistency model is a contract between the processes and the
data store such that if processes obey certain rules, the store
promises to work correctly
– Data-centric vs. client-centric consistency
– Data-centric consistency: consistency in the general sense (e.g., causal
consistency, sequential consistency)
– Client-centric consistency: consistency for a single client (independently
from other clients), assuming that a single client does not trigger multiple
concurrent updates (e.g., eventual consistency)
Consistency
The University of Sydney Page 9
Sequential consistency
Consistency
The University of Sydney Page 10
Sequential consistency
– Program order: The order in which events appear to be executed locally
(in the program)
– Execution: A sequence of reads (R) and writes (W) on some data items
x… executed by distributed processes p0…
– Serial execution: An execution where each process executes (all its
operations) one after another
– Equivalent executions: Two executions are equivalent if they contain
exactly the same reads and writes:
– executed from the same process,
– all writes have the same input values and
– all reads have the same output values
Distributed execution
The University of Sydney Page 11
Sequential consistency
– Notation:
– Wi(x)1 is a write operation by process pi on data item x with value 1
(index i omitted when clear from context)
– Ri(x)2 is a read operation by process pi on data item x that returns
value 2 (index i omitted when clear from context)
– Example 1: the execution W1(x)2;R2(x)2;W0(x)1;R3(x)1 is serial in that
each process executes one after another in the order p1; p2; p0; p3
W(x)1p0
time
W(x)2p1
R(x)2p2
R(x)1p3
The University of Sydney Page 12
Sequential consistency
– Sequential consistency. The result of each execution is
– the same as if the (read and write) operations by all processes on the same
data store were executed in some sequential order and the operations of
each individual process appear in this sequence in its program order
– Example 1(bis): is this execution sequentially consistent as well?
– All processes should see the same interleaving of operations
Sequentially consistent executions
W(x)1p0
time
W(x)2p1
R(x)2p2
R(x)1p3
The University of Sydney Page 13
Sequential consistency
– Sequential consistency. The result of each execution is
– the same as if the (read and write) operations by all processes on the same data store
were executed in some sequential order and the operations of each individual process
appear in this sequence in its program order
– Example 1(bis): the result of this serial execution is sequentially consistent as well
If an execution is serial, then its result is always sequentially consistent
Sequentially consistent executions
W(x)1p0
time
W(x)2p1
R(x)2p2
R(x)1p3
The University of Sydney Page 14
Sequential consistency
– Sequential consistency. The result of each execution is
– the same as if the (read and write) operations by all processes on the same data store
were executed in some sequential order and the operations of each individual process
appear in this sequence in its program order
– Example 2: is this execution sequentially consistent?
A sequentially consistent execution
W(x)1p0
time
W(x)2p1
R(x)2p2
R(x)2p3 R(x)1
R(x)1
The University of Sydney Page 15
Sequential consistency
– Sequential consistency. The result of each execution is
– the same as if the (read and write) operations by all processes on the same data store were executed in
some sequential order and the operations of each individual process appear in this sequence in its
program order
– Example 2: the result of this execution is sequentially consistent
– The result of the execution is W0(x)1; W1(x)2; R2(x)2; R3(x)2; R2(x)1; R3(x)1
– An equivalent sequential order with the same result is W1(x)2; R2(x)2; R3(x)2; W0(x)1;
R2(x)1; R3(x)1
– The program order of each process is satisfied by this sequence:
• R3(x)2 before R3(x)1 and
• R2(x)2 before R2(x)1
A sequentially consistent execution
W(x)1p0
time
W(x)2p1
R(x)2p2
R(x)2p3 R(x)1
R(x)1
The University of Sydney Page 16
Sequential consistency
– Sequential consistency. The result of each execution is
– the same as if the (read and write) operations by all processes on the same data store were
executed in some sequential order and the operations of each individual process appear in
this sequence in its program order
– Example 3: is this execution sequentially consistent?
A non-sequentially consistent execution
W(x)1p0
time
W(x)2p1
R(x)2p2
R(x)1p3 R(x)2
R(x)1
The University of Sydney Page 17
Sequential consistency
– Sequential consistency. The result of each execution is
– the same as if the (read and write) operations by all processes on the same data store were executed in
some sequential order and the operations of each individual process appear in this sequence in its
program order
– Example 3: the result of this execution is not sequentially consistent
– The result of the execution is W0(x)1; W1(x)2; R2(x)2; R3(x)1; R2(x)1; R3(x)2
– There is no sequential execution in which:
• By program order of p3, R3(x)1 is before R3(x)2 (implying that W0(x)1 would be before
W1(x)2 and
• By program order of p2, R2(x)2 before R2(x)1 (implying that W1(x)2 would be before
W0(x)1)
⇒ contradiction
A non-sequentially consistent execution
W(x)1p0
time
W(x)2p1
R(x)2p2
R(x)1p3 R(x)2
R(x)1
The University of Sydney Page 18
Sequential consistency
– How can a coherent execution may not be sequentially consistent
– Example 4: What are the possible outputs of this concurrent program?
Application to shared memory multiprocessors
Process 0
A = 1;
flag = 1;
Process 1
while (!flag); // spin
Print A;
/* Initially, A = flag = 0 */
Program
order
p0
p1 R(flag)0
W(A)1
time
W(flag)1
The University of Sydney Page 19
Sequential consistency
– How can a coherent execution may not be sequentially consistent
– Example 4: What are the possible outputs of this concurrent program?
Application to shared memory multiprocessors
Process 0
A = 1;
flag = 1;
Process 1
while (!flag); // spin
Print A;
/* Initially, A = flag = 0 */
Program
order
W(flag)1p0
R(A)?p1 R(flag)0 R(flag)1
W(A)1
time
spin
The University of Sydney Page 20
Sequential consistency
– How can a coherent execution may not be sequentially consistent
– Example 4: output “0” is not (sequentially) consistent as we cannot find a
sequential order that respects program order and prints 0.
Application to shared memory multiprocessors
Process 0
A = 1;
flag = 1;
Process 1
while (!flag); // spin
Print A;
/* Initially, A = flag = 0 */
Program
order
W(flag)1p0
R(A)0p1 R(flag)0 R(flag)1
W(A)1
time
spin
The University of Sydney Page 21
Causal consistency
Consistency
The University of Sydney Page 22
Causal consistency
– Causal consistency. Writes that are causally related (i.e., one happens before the other)
must be seen by all processes in the same order. Concurrent writes may be seen in a
different order on different machines
– Example 2(bis): is this execution causally consistent?
Causally consistent executions
W(x)1p0
p1
p2
R(x)2p3 R(x)1
R(x)1
time
W(x)2
R(x)2
The University of Sydney Page 23
Causal consistency
– Causal consistency. Writes that are causally related (i.e., one happens before the other) must be
seen by all processes in the same order. Concurrent writes may be seen in a different order on
different machines
– Example 2(bis): is this execution causally consistent?
– Write to the same data items are (concurrent) not necessarily causally
related
– A read returning the value written are causally related
Causally consistent executions (con’t)
W(x)1p0
W(x)2p1
R(x)2p2
R(x)2p3 R(x)1
R(x)1
time
The University of Sydney Page 24
Causal consistency
– Causal consistency. Writes that are causally related (i.e., one happens before the other) must be seen by
all processes in the same order. Concurrent writes may be seen in a different order on different
machines
– Example 2(bis): the result of this serial execution is causally consistent
If the result of an execution is sequentially consistent, then it is also causally consistent
Causally consistent executions (con’t)
W(x)1p0
W(x)2p1
R(x)2p2
R(x)2p3 R(x)1
R(x)1
time
The University of Sydney Page 25
Causal consistency
– Causal consistency. Writes that are causally related (i.e., one happens before the other) must
be seen by all processes in the same order. Concurrent writes may be seen in a different
order on different machines
– Example 5: is the result of this execution is causally consistent?
Causally consistent executions (con’t)
W(x)1p0
time
R(x)1p1
R(x)1p2
R(x)3p3 R(x)1
W(x)2
W(x)3
R(x)3
R(x)2
R(x)2
The University of Sydney Page 26
Causal consistency
– Causal consistency. Writes that are causally related (i.e., one happens before the other)
must be seen by all processes in the same order. Concurrent writes may be seen in a
different order on different machines
– Example 5: the result of this execution is causally consistent
– W0(x)1 and W0(x)3 that are causally related are seen in the same order by
p0, p1, p2 and p3
– W1(x)2 and W0(x)3 are concurrent as none happen before the other
Causally consistent executions (con’t)
W(x)1p0
time
R(x)1p1
R(x)1p2
R(x)3p3 R(x)1
W(x)2
W(x)3
R(x)3
R(x)2
R(x)2
The University of Sydney Page 27
Causal consistency
– Causal consistency. Writes that are causally related (i.e., one happens before the other) must
be seen by all processes in the same order. Concurrent writes may be seen in a different
order on different machines
– Example 5: but is this sequentially consistent?
Causally consistent executions (con’t)
W(x)1p0
time
R(x)1p1
R(x)1p2
R(x)3p3 R(x)1
W(x)2
W(x)3
R(x)3
R(x)2
R(x)2
The University of Sydney Page 28
Causal consistency
– Causal consistency. Writes that are causally related (i.e., one happens before the other) must
be seen by all processes in the same order. Concurrent writes may be seen in a different
order on different machines
– Example 5: the result of this execution is not sequentially consistent
Causally consistent executions (con’t)
W(x)1p0
time
R(x)1p1
R(x)1p2
R(x)3p3 R(x)1
W(x)2
W(x)3
R(x)3
R(x)2
R(x)2
The University of Sydney Page 29
Replication
Consistency
The University of Sydney Page 30
Replication
– Writes operations can be carried out to several sites (like in the database
example)
– Updates must be executed in the same order at each replicated site
– The use of totally-ordered broadcast (cf., previous lecture) can solve this
– However, our previous Lamport’s clock solution does not scale well
Updating a replicated system
The University of Sydney Page 31
Replication
– Assumption: no concurrent updates
– The only type of conflict occur between a reading operation and an
updating operation (read-write conflict)
– Never between two updating operations (no write-write conflicts)
– Example:
– A web server is the only one to update the webpage content
– Clients typically access the webpage in read mode only (without
modifying it)
– If no updates take place for a long time, all replicas will
gradually become consistent
Eventual consistency: eventually all replicas are consistent
The University of Sydney Page 32
Replication
Eventual consistency (con’t)
– A mobile user accesses a database by connecting to one of its replicas in a transparent way (the user’s application is
unaware of which replica)
– The user executes several update requests and disconnects
– The user then reconnects from a different location or through a different device.
– If the changes have not been propagated by the system to all replicas, the user may observe a client-centric
inconsistency
The University of Sydney Page 33
Replication
– Active replication
– Forward all messages to a central coordinator (leader)
– The coordinator is a sequencer that chooses a unique sequence number for
each message
– It sends this sequence number along with the message to all replicas
– Operations are carried out in the order of their sequence number
Coordinator
The University of Sydney Page 34
Replication
– Primary-backup protocol [Budhiuraja et al., 1993]
– All write operations on x are
forwarded to a primary server for x
– The primary does the update and
forwards the request to backup
servers
– Each backup executes the updates
and acknowledges the primary
– The primary sends a response to
the client
– Read operations can be carried out
locally
– Pro: guarantees sequential consistency
– Cons: delayed answer to client
Primary-backup
The University of Sydney Page 35
Serializability
Consistency
The University of Sydney Page 36
Serializability
– Serializability: the result of an execution (of multi-access
operations) is serializable if there exists an equivalent sequential
execution.
Serializability [Papadimitriou, JACM 1979]
p0
time
p1
Operation 1
Operation 2
p2
Operation 3
R(x)0 R(y)2
W(x)1
R(x)1 W(y)2
The University of Sydney Page 37
Serializability
– Serializability: the result of an execution (of multi-access
operations) is serializable if there exists an equivalent sequential
execution.
p0
time
p1
Operation 1
Operation 2
p2
Operation 3
R(x)0 R(y)2
W(x)1
R(x)1 W(y)2
Can only occur before, in an equivalent sequential execution
There is a cycle op1- ->op2- ->op3- ->op1 in the precedence graph ⇒ non-serializable
The University of Sydney Page 38
Serializability
– Serializability: the result of an execution (of multi-access
operations) is serializable if there exists an equivalent sequential
execution.
p0
time
p1
Operation 1
Operation 2
p2
Operation 3
R(x)0 R(y)0
W(x)1
R(x)1 W(y)2
Can only occur before in an equivalent sequential execution
No cycle op1- ->op2- ->op3 in the precedence graph ⇒ serializable
The University of Sydney Page 39
Linearizability
– Real-time precedence: if an operation o1 returns before another
operation o2 is invoked (at a potentially different process) then o1
precedes o2 with respect (w.r.t) to real-time.
– Linearizability. The result of each execution is
– equivalent to a sequential execution that respects the real-time precedence (i.e.,
in which an operation returning before another is invoked is always ordered
before)
– is the same as if the (read and write) operations by all processes on the same
data store were executed in some sequential order and the operations of each
individual process appear in this sequence in its program order
Linearizability (of reads and writes) [Herlihy and Wing, TOPLAS 1990]
p0
time
p1
R(x)0
W(x)1
inv. resp. inv. resp.
R0(x)0 precedes W1(x)1 w.r.t real time
The University of Sydney Page 40
– Linearizability. The result of each execution is
– equivalent to a sequential execution that respects the real-time precedence (i.e.,
in which an operation returning before another is invoked is always ordered before)
– is the same as if the (read and write) operations by all processes on the same data store
were executed in some sequential order and the operations of each individual process
appear in this sequence in its program order
– Example 5: is this a linearizable execution? (initially x=0)
Linearizability
Linearizability (of reads and writes)
p0
time
p1
R(x)0 R(x)0
W(x)1
The University of Sydney Page 41
Linearizability
– Linearizability. The result of each execution is
– equivalent to a sequential execution that respects the real-time precedence (i.e.,
in which an operation returning before another is invoked is always ordered
before)
– is the same as if the (read and write) operations by all processes on the same
data store were executed in some sequential order and the operations of each
individual process appear in this sequence in its program order
– Example 5: this is not a linearizable execution (initially x=0)
– W1(x)1 precedes R0(x)0 w.r.t real-time, thus R0(x)0 cannot return the
initial value of x.
Linearizability (of reads and writes)
p0
time
p1
R(x)0 R(x)0
W(x)1
The University of Sydney Page 42
Linearizability
– Linearizability. The result of each execution is
– equivalent to a sequential execution that respects the real-time precedence (i.e.,
in which an operation returning before another is invoked is always ordered before)
– is the same as if the (read and write) operations by all processes on the same data store
were executed in some sequential order and the operations of each individual process
appear in this sequence in its program order
– Example 6: is this a linearizable execution? (initially x=0)
Linearizability (of reads and writes)
p0
time
p1
R(x)0 R(x)1
W(x)1
The University of Sydney Page 43
Linearizability
– Linearizability. The result of each execution is
– equivalent to a sequential execution that respects the real-time precedence (i.e.,
in which an operation returning before another is invoked is always ordered before)
– is the same as if the (read and write) operations by all processes on the same data store
were executed in some sequential order and the operations of each individual process
appear in this sequence in its program order
– Example 6: this is a linearizable execution (initially x=0)
Linearizability (of reads and writes)
p0
time
p1
R(x)0 R(x)1
W(x)1
The University of Sydney Page 44
– Linearizability. The result of each execution is
– equivalent to a sequential execution that respects the real-time precedence (i.e.,
in which an operation returning before another is invoked is always ordered before)
– is the same as if the (read and write) operations by all processes on the same data store
were executed in some sequential order and the operations of each individual process
appear in this sequence in its program order
– Example 7: is this a linearizable execution? (initially x=0)
Linearizability
Linearizability (of reads and writes)
p0
time
p1
R(x)1 R(x)1
W(x)1
The University of Sydney Page 45
Linearizability
– Linearizability. The result of each execution is
– equivalent to a sequential execution that respects the real-time precedence (i.e.,
in which an operation returning before another is invoked is always ordered before)
– is the same as if the (read and write) operations by all processes on the same data store were
executed in some sequential order and the operations of each individual process appear in this
sequence in its program order
– Example 7: this is a linearizable execution (initially x=0)
– R0(x)1 is concurrent with W1(x)1 (none precedes the other w.r.t real-time), hence R0(x)
can return 1 (or 0) without violating linearizability
Linearizability (of reads and writes)
p0
time
p1
R(x)1 R(x)1
W(x)1
The University of Sydney Page 46
– Linearizability can also apply to other kind of operations.
Consider an integer set object that exports (as opposed to the previous register exporting read/write):
– insert(int a)boolean b that adds an element to the set if not already present and return true, returns false if
already present
– remove(int a)boolean b that removes an integer from the set if it is currently present and returns true, false if
not present
– contains(int a)boolean b that checks whether an integer is present in the set
– Example 8: is this a linearizable execution of set operations? (initially x ∉ set)
Linearizability
Linearizability (of higher level operations)
p0
time
p1
insert(x)true contains(x)true
remove(x)true
The University of Sydney Page 47
– Linearizability can also apply to other kind of operations.
Consider an integer set object that exports (as opposed to the previous register exporting read/write):
– insert(int a)boolean b that adds an element to the set if not already present and return true, returns false if
already present
– remove(int a)boolean b that removes an integer from the set if it is currently present and returns true, false if
not present
– contains(int a)boolean b that checks whether an integer is present in the set
– Example 8: this is not a linearizable execution of set operations (initially x ∉ set)
Linearizability
Linearizability (of higher level operations)
p0
time
p1
insert(x)true contains(x)true
remove(x)true
The University of Sydney Page 48
– Linearizability can also apply to other kind of operations.
Consider an integer set object that exports (as opposed to the previous register exporting read/write):
– insert(int a)boolean b that adds an element to the set if not already present and return true, returns false if
already present
– remove(int a)boolean b that removes an integer from the set if it is currently present and returns true, false if
not present
– contains(int a)boolean b that checks whether an integer is present in the set
– Example 9: is this a linearizable execution of set operations? (initially x ∉ set)
Linearizability
Linearizability (of higher level operations)
p0
time
p1
insert(x)true
remove(x)true
contains(x)false
The University of Sydney Page 49
– Linearizability can also apply to other kind of operations.
Consider an integer set object that exports (as opposed to the previous register exporting read/write):
– insert(int a)boolean b that adds an element to the set if not already present and return true, returns false if
already present
– remove(int a)boolean b that removes an integer from the set if it is currently present and returns true, false if
not present
– contains(int a)boolean b that checks whether an integer is present in the set
– Example 9: this is a linearizable execution of set operations (initially x ∉ set)
Linearizability
Linearizability (of higher level operations)
p0
time
p1
insert(x)true
remove(x)true
contains(x)false
The University of Sydney Page 50
– Linearizability can also apply to other kind of operations.
Consider an integer set object that exports (as opposed to the previous register exporting read/write):
– insert(int a)boolean b that adds an element to the set if not already present and return true, returns false if
already present
– remove(int a)boolean b that removes an integer from the set if it is currently present and returns true, false if
not present
– contains(int a)boolean b that checks whether an integer is present in the set
– Example 10: is this a linearizable execution of set operations? (initially x ∈ set)
Linearizability
Linearizability (of higher level operations)
p0
time
p1
insert(x)false
remove(x)true
contains(x)false
The University of Sydney Page 51
Linearizability
– Linearizability can also apply to other kind of operations.
Consider an integer set object that exports (as opposed to the previous register exporting read/write):
– insert(int a)boolean b that adds an element to the set if not already present and return true, returns false if
already present
– remove(int a)boolean b that removes an integer from the set if it is currently present and returns true, false if
not present
– contains(int a)boolean b that checks whether an integer is present in the set
– Example 10: this is a linearizable execution of set operations (initially x ∈ set)
Linearizability (of higher level operations)
p0
time
p1
insert(x)false
remove(x)true
contains(x)false
The University of Sydney Page 52
Conclusion
– There are several consistency criteria
– Strong criteria (restrictive):
• provides lots of safety guarantees (are enough for most safety
requirements)
• provides low performance
– Weak criteria (not restrictive):
• provides less safety guarantees (can be enough for specific
applications)
• gives high performance
– Some criteria strength are comparable (from the weakest to the
strongest):
– causal consistency < sequential consistency
– serial ⇒ sequential consistent ⇒ causally consistent
– serializable ≠ linearizability
The University of Sydney Page 53
Mid-term Quiz
– 15% of final mark
– During Week 7 tutorial timeslot – 10:00am to 1pm on
Wednesday
– Online exam
– Multiple choice questions via Canvas
– Password protected exam
– Password will be announced on Ed (and Zoom).
– <= 50 questions, 55-60 minutes.
– Test course content from week 1 to week 6.
The University of Sydney Page 54
Sample questions for mid-term Quiz
1. Starvation can happen in;
a) Centralized mutual exclusion
b) Decentralized mutual exclusion
c) Distributed mutual exclusion
d) Token ring mutual exclusion
2. HTTP is a stateless protocol
a) True
b) False
3. Which one is reliable transport protocol?
a) TCP
b) UDP
4. Which one is distance vector protocol?
a) RIP
b) OSPF
The University of Sydney Page 55
What’s Next ?
– Mid-term Quiz – 10:00am to 1pm on Wednesday.
– Assignment 1 is due Week 8
– Next week: Blockchain
– See you all !