Why replicate data?
- Enhance reliability (what if replica crashes). 2. Improve performance (more processes need access).
What is the main issue with replication?
Keeping replicas consistent - when one updated
What is a Read-Write conflict?
Read and write operation acting concurrently on same data.
What is a Write-Write conflict?
Two concurrent write operations on same data.
What is the scalability trade-off with consistency?
Guaranteeing global ordering on conflicting operations is costly - may need to weaken consistency.
What is a Consistency Model?
Contract between data store and processes specifying results of read/write in presence of concurrency.
What is a Data Store?
Distributed collection of storages.
Name 3 Data-Centric consistency models.
Continuous, Sequential, Causal.
Name 3 Client-Centric consistency models.
Monotonic Reads, Monotonic Writes, Read Your Writes.
What is Continuous Consistency?
Replicas may differ in numerical value
What is a Conit?
Consistency Unit - specifies data unit over which consistency is measured.
What is Order Deviation?
Number of tentative operations pending to be committed.
What is Numerical Deviation?
Number of operations at other replicas not yet seen
What is Sequential Consistency?
Result same as if all operations in some sequential order and each process’s operations appear in program order.
What notation means ‘P1 writes value a to x’?
W₁(x)a
What notation means ‘P1 reads x and gets value b’?
R₁(x)b
When is a data store NOT sequentially consistent?
When different processes see different interleavings of write operations.
What is the Happens-Before relation?
Event a → b means a happened before b (partial order).
What are the 3 rules for Happens-Before?
- Same node, a before b locally. 2. a is send, b is receive of same message. 3. Transitivity via c.
What are concurrent events?
When neither a → b nor b → a. Written a ‖ b.
What is Causal Consistency?
Writes that are potentially causally related must be seen by all processes in same order. Concurrent writes may differ.
When are two writes causally related?
When one process reads a value and then writes based on it.
What is the key difference between Sequential and Causal consistency?
Sequential: all processes see same order of ALL writes. Causal: only causally related writes must be in same order.
What is Client-Centric consistency?
Guarantees for single client about consistency of their accesses. No guarantees about concurrent accesses by different clients.
