Consistency and Replication (I)

1. Replication

• Motivation

• Performance enhancement
• Enhanced availability/reliability
• Fault tolerance
• Scalability
• Tradeoff between benefits of replication and work required to keep replica consistent

• Requirements

• Consistency
• Depends upon applications
• In many applications, we want different clients making (read/write) requests to different replicas of the same logical items should not obtain different results
• Replica transparency
• Desirable for most application

2. Consistency Models

• Consistency model is a contract between processes and a data store
• If process follow certain rules, then the store will work correctly
• Needed for understanding how concurrent read and writes behave w.r.t shared data
• Relevant for shared memory multiprocessors
• Cache coherence algorithms
• Shared database, files
• Independent operations
• transactions

Strict Consistency

• Any read on a data item x returns a value corresponding to the result of the most recent write on x
• Challenge
• It requires absolute global time

Sequential Consistency

• The result of any execution is the same as if the read and write operation by all processes were executed in some sequential order and the operations of each individual process appear in this sequence in the order specified by its program.
• i.e., required to be seen by the same process in the same order
• Example

• Linearizability
• Definition of sequential consistency says nothing about time
• There is no reference to the "most recent" write operation
• Liearizability
• Weaker than strict consistency, stronger than sequential consistency
• Operations are assumed to receive a time stamp with a global available lock that is loosely synchronized
• The result of any execution is the same as if the operations by all processes on the data store were executed in some sequential order and the operations of each individual process appear in this sequence in the order specified by its program. 

Causal Consistency

• 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.
• Example
• (a) is not casual-consistent, since in process P2, a performs before b, so that in process P3 and P4, a should also performs before b
• While in (b) there is not casual relationship between a and b

FIFO consistency

• Writes done by a single process are seen by all other processes in the order in which there were issues.
• But writes from different processes may be seen in a different order by different process.

Weak Consistency

• Access to synchronization variable associated with a data store are sequential consistent.
• No operation on a synchronization variable is allowed to be performed until all previous writes have been completed everywhere
• No read or write operation on data items are allowed to be performed until all previous operations to synchronization variable have been performed.

Release Consistency

• Before a read or write operation on a shard data is performed, all previous requires done by the process must have completed successfully.
• Before a release is allowed to be performed, all previous reads and writes by the process must have completed.
• Access to synchronization variables are FIFO consistent (sequential consistent is not required).

Entry Consistency

• An acquire process of a synchronization variable is not allowed to perform with respect to a process until all updates to the guarded shared data have been performed with respect to that process.
• Before an exclusive mode access to a synchronization variable by a process is allowed to perform with respect to that process, no other process may hold the synchronization variable, not even in nonexclusive mode.
• After an exclusive mode access to a synchronization variable has been performed, any other process's next nonexclusive mode access to that synchronization variable may not be performed until it has performed with respect to that variable's owner.

3. A summary of Consistency Models

4. Weak Consistency Models

• The weak consistency models that use synchronization variable (release, entry consistency) are mostly relevant to shared multiprocessor systems
• Also modern CPU with multiple pipelines, out-of-order instruction execution, asynchronous writes, etc.
• In distributed systems, weak consistency typically refers to weaker consistency models than sequential consistency
• Casual consistency
• e.g., used in the Gossip system
• Optimistic approaches such as those used in Bayou, Coda that use application specific operations to achieve eventual consistency

5. Eventual Consistency

• Session Guarantees

• When clients move around and connects to different replicas, strange things can happen 
• Updates you just made are missing
• Database goes back in time
• Design choice
• Insist strict consistency
• Enforce some session guarantees, client-centric consistency

• Monotonic Reads

• If a process reads the value of a data item x, any successive read operation on x by that process will always return that same value on a more recent value.
• Disallow reads to a database less current than previous read
• Example error
• Get a list of email message, when attempts to read one, pop put "message does not exist"

• Monotonic Writes

• A write operation by a process on a data item x is completed before any successive write operation x by the same process
• Writes must follow any previous writes that occurred within their session

• Read your Writes

• A read operation by a process on a data item x is completed before any successive write operation on x by the same process.
• Every read in a session should see all previous writes in that session.
• Example error
• Deleted email message re-appear

• 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.
• If a write W followed by a read R at a server X, ten at all other servers
• If W is in T's database, then any writes relevant to R are also avaialble
• After users outside session
• Traditional write/read dependencies preserved at all servers
• Two guarantees: ordering and propagation
• Order
• If a read precedes a write in a session, then that read depends on a previous non-session write, then previous write will never be seen after second write at any server. It may not be seen at all.
• Propagation
• Previous write will actually have propagated to any data base where the second write is applied.

6. Supporting Session Guarantees

• Responsibility of session manager, not servers
• Two sets
• Read set
• set of writes that are relevant to session reads
• Write set
• Set of writes that performed in session
• Update dependencies captured in read-sets and write-sets
• Causal order of writes
• Use Lamport clocks