Tutorial 5: Consistency Flashcards
What is a consistency model?
A contract between a distributed data store (e.g., distributed database, shared memory, shared files, etc.) and a set of processes, which specifies what the results of read/write operations are in the presence of concurrency.
Why do we need consistency models in distributed systems?
With concurrent read & write operations on a distributed data store there is a potential for inconsistencies. Different consistency models describe different degrees of consistency that are tolerable for the application that resides on top of it. When designing such distributed systems a consistency model helps to identify the desired consistency level. In most cases the cost is traded off against the guarantees. High consistency is expensive but might not always be needed.
What is the difference between (data-centric) consistency models and client-centric consistency models?
(Data-centric) consistency models care about system-wide consistency, whereas client-centric consistency models focus on the client point of view.
Name two advantages and disadvantages of replication, respectively.
Advantages: • Performance (replicas can increase the throughput, especially of read operations) • High Availability (e.g., when a single machine fail) • Fault-tolerance Disadvantages: • Communication/Storage cost • Stale (inconsistent) data
Name three use cases for replication? Why is replication used in the three cases?
Distributed File Systems e.g. GFS, HDFS → Data blocks are replicated – Ensure availability of data – Provide recovery mechanisms in case of a system crash Database replication e.g. MySql, Cassandra → Rows of tables are replicated – Ensure fault tolerance – Distribute the load of reads and writes (increase performance) – Data Warehousing, run analytical queries File-based replication e.g., backup solutions → Files are replicated – Store data/files at different places
Strict Consistency means that any read on a resource x returns a value corresponding to the result of the most recent write on x. This definition implicitly assumes the existence of absolute global time. Is Figure 2.2 strictly consistent? If yes, find a valid execution sequence to prove it. If not, give an explanation.
Solution: w(x)a r(x)a w(x)b r(x)b
Linearizability means that all operations that are ordered in real-time are similarly ordered in the execution sequence. We assume ordering according to a set of synchronized clocks. This implies the operation can be executed at an arbitrary point within a given interval. Is Figure 2.3 lineralizable? Is Figure 2.3 strictly consistent, when neglecting the intervals? If yes, find valid execution sequences to prove it. If not, give an explanation.
As the physical clocks of the processes in the system are synchronized up to a bounded error the execution of operation can happen at any point in the given interval.
- w(x)a w(x)c w(x)b r(x)b r(x)b is a correct linearized sequence.
- Strict consistency is violated as sequence w(x)a r(x)b in the beginning is not valid.
Sequential Consistency means that any valid interleaving of read and write operation is acceptable behavior, but all processes see the same interleaving of operations. Nothing is said about time. Is Figure 2.4 sequentially consistent? Is Figure 2.4 linearizable? If yes, find valid execution sequences to prove it. If not, give an explanation. Consider the intervals only to check linearizibility.
- w(x)a w(x)c w(x)b r(x)b r(x)b
- Assuming a global time, the ordering of events w(x) bw(x) c r(x) b cannot be changed. Therefore every execution order is invalid and linearizability cannot be achieved.
Causal consistency means that concurrent writes do not need to be seen in the same order by all readers. Causally related writes, however, must be seen in the same order by every process. This means processes can possibly have different execution sequences. Nothing is said about time. Is Figure 2.5 causally consistent? Is Figure 2.5 sequentially consistent? If yes, find valid execution sequences to prove it. If not, give an explanation.
- Due to the following valid execution sequences for processes P1, P2, P3 the situation is causally consistent
- P1: w(x)a w(x)c w(x)b r(x)b
- P2: w(x)a w(x)b w(x)c r(x)c
- P3: w(x)b w(x)c w(x)a r(x)a
- For sequential consistency concurrent writes need to be seen in the same order by all readers. For example the schedule w(x)a w(x)b r(x)b w(x)c r(x)c r(x)a is invalid. Similar, in every combination of write operations there will always be one read operation that cannot be satisfied, therefore all execution sequences are not valid and the situation is not sequentially consistent.
Is Figure 2.6 causally or sequentially consistent? If yes, find valid execution sequences to prove it. If not, give an explanation.
- The write operations w(x)b by P2 and w(x)c by P3 are concurrent although they are causally related to w(x)a. Therefore, the following valid execution sequences for P4 and P5 show that the situation is causally consistent
- P4: w(x)a r(x)a w(x)b r(x)b w(x)c r(x)c
- P5: w(x)a r(x)a w(x)c r(x)c w(x)b r(x)b
- For sequential consistency concurrent writes need to be seen in the same order by all readers. As different write orders for w(x)b and w(x)c are necessary at P4 and P5 to provide the correct read order this situation is not sequential consistent.
FIFO consistency means write operations 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 different orders by different processes. Is Figure 2.7 FIFO consistent? Is Figure 2.7 causally consistent? If yes, find valid execution sequences to prove it. If not, give an explanation.
- The order of write operations w(x)a and w(x)c at P1 is also reflected in the read operations at P3, which makes the situation FIFO consistent.
- w1(x)a r2(x)a r3(x)a w2(x)b r1(x)b r2(x)b w2(x)d r3(x)d w1(x)c r3(x)c
- The following write operations are causally related:
- (w(x)a and w(x)b), (w(x)b and w(x)c), and (w(x)b and w(x)d).
- Due to the following correct execution sequence, the given situation is also causally consistent:
- w1(x)a r2(x)a r3(x)a w2(x)b r1(x)b r2(x)b w2(x)d r3(x)d w1(x)c r3(x)c
Monotonic-read means that once read, subsequent reads on that data item return the same or a more recent value. Do you see any problems why monotonic-read in Figure 3.8 could not be guaranteed. If yes, how would you correct Figure 3.8?
The mobile client has to read a consistent version of data. Therefore the writes at location L1 have to be reflected at L2. Referring to the email example: The client wants to retrieve all emails when synchronizing with a local replica and not only parts of it.
Monotonic-write means that a write operation by a process on a data item x is completed before any subsequent write operation can be issued on x by the same process. Do you see any problems why monotonic-write in Figure 3.9 could not be guaranteed? If yes, how would you correct Figure 3.9 ?
In fact the write to the replica at location L1 is reflected in the update operations at location L2 and L3. The problem here is that at L2 the writes are executed in the wrong order. Since writes in different orders can lead to different results, monotonic writes cannot be guaranteed.
Read-your-writes means that the effect of a write operation by a process on data item x will always be seen by a successive read operation on x by the same process. Do you see any problems why read-your-writes in Figure 3.10 could not be guaranteed? If yes, how would you correct Figure 3.10?
The write operation at L1, i.e., w(x1) is not reflected at L3. Therefore, the situation is not read-your-writes consistent. In order to correct the situation, w(x1) must be added to the write set at L3.
Writes-follow-reads means that a write operation by a process on a data item x following a previous read operation on x by the same process, is guaranteed to take place on the same or a more recent value of x that was read. Do you see any problems why writes-follow-reads in Figure 3.11 could not be guaranteed? If yes, how would you correct Figure 3.11?
The write operation that led to the value read in L2 is not reflected at L3. Therefore, the situation is not writes-follow-read consistent. In order to correct the situation, w(x2) must be added to the write set at L3.
