Rajendra Mane College of Engineering & Technology, Ambav.
Department of Computer Engineering
B. E. Computer Engineering
Course: (CSC802) Distributed
Computing
Lecture - 27
Subject Teacher: Mr. Laxman S. Naik
Assistant Professor
Academic Year: 2020-21
1
Module 5
Consistency, Replication
and Fault Tolerance
2
Causal Consistency
This model distinguishes between events that are “causally related”
and those that are not.
If event B is caused or influenced by an earlier event A, then causal
consistency requires that every other process see event A, then
event B.
Operations that are not causally related are said to be concurrent.
3
More on Causal Consistency
A causally consistent data-store obeys this condition:
Writes that are potentially causally related must be seen by all
processes in the same order. Concurrent writes may be seen in a
different order on different machines (i.e., by different processes).
This sequence is allowed with a causally-consistent store, but not with
sequentially or strictly consistent store. Note: it is assumed that W2(x)b
and W1(x)c are concurrent. 4
Another Causal Consistency Example
incorrect
correct
a) Violation of causal-consistency – P2’s write is related to P1’s write due to the
read on ‘x’ giving ‘a’ (all processes must see them in the same order).
b) A causally-consistent data-store: the read has been removed, so the two
writes are now concurrent. The reads by P3 and P4 are now OK. 5
FIFO Consistency
Defined as follows:
Writes done by a single process are seen by all other processes in the
order in which they were issued, but writes from different processes
may be seen in a different order by different processes.
This is also called “PRAM Consistency” – Pipelined RAM.
The attractive characteristic of FIFO is that it is easy to implement.
There are no guarantees about the order in which different
processes see writes – except that two or more writes from a single
process must be seen in order.
6
FIFO Consistency Example
A valid sequence of FIFO consistency events.
Note that none of the consistency models studied so far would allow
this sequence of events.
7
Introducing Weak Consistency
Not all applications need to see all writes, let alone seeing them in
the same order.
This leads to “Weak Consistency” (which is primarily designed to
work with distributed critical regions).
This model introduces the notion of a “synchronization variable”,
which is used update all copies of the data-store.
8
Weak Consistency Properties
The three properties of Weak Consistency:
1. Accesses to synchronization variables associated with a data-store
are sequentially consistent.
2. No operation on a synchronization variable is allowed to be
performed until all previous writes have been completed
everywhere.
3. No read or write operation on data items are allowed to be
performed until all previous operations to synchronization
variables have been performed.
9
Weak Consistency: What It Means
By doing a sync., a process can force the just written value out to all
the other replicas.
Also, by doing a sync., a process can be sure it’s getting the most
recently written value before it reads.
In essence, the weak consistency models enforce consistency on a
group of operations, as opposed to individual reads and writes (as is
the case with strict, sequential, causal and FIFO consistency).
10
Weak Consistency Examples
before sync., any results are acceptable
Wrong!!
a) A valid sequence of events for weak consistency. This is because P2 and P3
have yet to synchronize, so there’s no guarantees about the value in ‘x’.
b) An invalid sequence for weak consistency. P2 has synchronized, so it cannot
read ‘a’ from ‘x’ – it should be getting ‘b’. 11
Introducing Release Consistency
Question: how does a weakly consistent data-store know that the
sync is the result of a read or a write?
Answer: It doesn’t!
It is possible to implement efficiencies if the data-store is able to
determine whether the sync is a read or write.
Two sync variables can be used, “acquire” and “release”, and their
use leads to the “Release Consistency” model.
12
Release Consistency
Defined as follows:
When a process does an “acquire”, the data-store will ensure that all
the local copies of the protected data are brought up to date to be
consistent with the remote ones if needs be.
When a “release” is done, protected data that have been changed
are propagated out to the local copies of the data-store.
13
Release Consistency Example
A valid event sequence for release consistency.
Process P3 has not performed an acquire, so there are no guarantees
that the read of ‘x’ is consistent. The data-store is simply not
obligated to provide the correct answer.
P2 does perform an acquire, so its read of ‘x’ is consistent.
14
Release Consistency Rules
A distributed data-store is “Release Consistent” if it obeys the
following rules:
1. Before a read or write operation on shared data is performed, all
previous acquires done by the process must have completed
successfully.
2. Before a release is allowed to be performed, all previous reads and
writes by the process must have completed.
3. Accesses to synchronization variables are FIFO consistent
(sequential consistency is not required).
15
Thank you for patient listening!
---- Keep Learning!
16