[SOLVED] CS代写 Causal consistency (1)

Causal consistency (1)
• Causal consistency is a weaker version of sequential consistency
• If event a caused or influenced event bàeveryone 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 PowCoder代写加微信 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]