[SOLVED] CS Causal consistency (1)

Causal consistency (1)
Causal consistency is a weaker version of sequential consistency
If event a caused or influenced event baeveryone should see a and then b
Writes that are potentially causally related must be seen by all the processes in the same order

Copyright By Assignmentchef assignmentchef

Concurrent writes may be seen in a different order on different machines
Causally related writes
Within the same process Read followed by a write

Causal consistency (2)
causal relation first a then b
concurrent
no matter order of b and c

Causal consistency (3)
causal relation
concurrency

Causal consistency (4)
To implement causal consistency, it is necessary to keep track of which process has seen which write operation
We need a graph of dependencies among processes

Sequential and causal consistency: exercise
P1: R(X = 1) R(X = 4) R(X = 3)
P2: R(X = 1)W(X = 2) R(X = 3) R(X = 4) P3: W(X = 1)W(X = 3) R(X = 2)
P4: R(X = 3) R(X = 2)W(X = 4)

Sequential and causal consistency: exercise
P1: R(X = 1) R(X = 4) R(X = 3)
P2: R(X = 1)W(X = 2) R(X = 3) R(X = 4) P3: W(X = 1)W(X = 3) R(X = 2)
P4: R(X = 3) R(X = 2)W(X = 4)

Eventual consistency (1)
How fast updates should be made available to read-only processes? In many scenarios (e.g., DNS and Web pages) there cannot be write-
write conflicts as only one authority can write data
We only need to solve read-write conflicts
It may be acceptable to propagate updates in a lazy fashion: readers will see the update with some delay (e.g., browser cache)

Eventual consistency (2)
If no update takes place for a long time, all replicas will gradually become consistent (they converge)
It works well if clients always access the same replica
What if the same client accesses different copies of the data?

Eventual consistency (3)
Access a distributed database through a laptop
1. At time T1 you access the data at location A and make read and write operations
2. At time T2 you move and
access replica
at location B,
you may notice inconsistencies (e.g., your updates @A are not present @B!)

Client-centric consistency
Client-centric consistency guarantees that a single client sees consistency in her accesses to the data store
The data store appears consistent to each single client
No guarantees are given to concurrent accesses by different clients

Client-centric consistency models
Monotonic reads
Monotonic writes
Read your writes
Writes follow reads

Monotonic reads
If a process reads the value of a data item x, any successive read operation on x by that same process will always return that same value or a more recent value
Example: mailbox
If I read my mailbox at time t
At time t1>t I expect to see all the emails I read at time t, and possibly additional (more recent) ones

Monotonic reads: example
WS(x2) does not take into account operation WS(x1) and hence R(x2) may not be properly updated

Monotonic writes
A write operation by a process on a data item x is completed before any successive write operation on x by the same process
Requires that write operations by the same process are propagated in the correct order
The copy on which a process operates reflects all the effects of previous writes by the same process
Example: software library
When a process updates a function in the library, it operates on the latest version of the same, with all the functions previously updated

Monotonic writes: example
Operation W(x1) has not been propagated to the copy at location L2, hence W(x2) operates on an old copy

Read your writes
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
A write operation is always completed before a read by the same process, who sees its updates
Example: web documents
When you update your web page, your Web browser should show the newest version of the page (instead of its cached copy)

Read your writes: example
WS(x2) does not take into account operation WS(x1) and hence R(x2) may not be properly updated

Writes follow reads
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
Updates are propagated as the result of previous reads
Example: comment posting
When a user posts a comment on an article/post, it has seen the article/post

Writes follow reads: example
WS(x2) does not take into account operation WS(x1) and hence W(x2) may operate on an old version of the data item

CS: assignmentchef QQ: 1823890830 Email: [email protected]