9 Consistency (117)

Now we can focus on several consistency models.

9.1 Consistency models (117)

distributed system a collection of concurrent processes operating on a collection of objects. A process is a sequence of operations on objects. Think of an opperation as an:

    Operation = Invocation * Completion

A consistency model is a set of histories. But keep in mind that a system can only violate a model.

9.1.1 Common consistency models (119)

There have been some more well-defined consistency models that have arisen over the last few decades.

9.1.2 Virtues and limitations (119)

There might be some models that overlap or completely are a subset of an other.

A consistency model can help a developer by showing that there is more things that they can rely on, but this will have a trade-off as the system will be slower and require more time to get to the consistent state. A System can be less consistent making it harder for the programmer but will allow the system to be more responsive.

9.2 Linearizability (121)

Here is where we talk about the the order of the operations and then the outcome of those operations.

9.2.1 Queue and stack (122)

A queue is first in and first out (FIFO)

A stack is first in and last out (FILO)

9.2.2 Formal definition of linearizability (123)

Sequential is every invocation is followed by its completion. Concurrent is not sequential.

A history H is linearizable if
¡ Sequential equivalence—There exists a sequential history H′ such that H′ is 
  equivalent to H—that is, H′ and H yield the same results.
¡ Real-time ordering—The ordering of operations in H′ respects the real-time 
  ordering of nonconcurrent operations in H—that is, any operation that is invoked
  after a previous operation completes must witness the effects of the completed
  operation.

9.3 Eventual consistency (124)

There are a few ways of making sure that a system will get to the same place. We might need a convergence guarantee. This says that eventually all nodes will end up at the same state. We would say then that the system will have eventual consistency.

9.3.1 The shopping cart (124)

If there is a replica of a state:

Both start with item a in the cart
One removes A adds B
One adds C
Amazon would make both have ABC as they would prioritize additions.

9.3.2 Variants of eventual consistency (125)

Basic Eventual Consistency

¡ Eventual delivery—An update made to one nonfaulty replica is eventually 
  delivered to every other nonfaulty replica.
¡ Weak convergence—After no further updates occur, all replicas eventually con-
  verge to the same state.

Strong Eventual Consistency

¡ Eventual delivery—This guarantee is the same as in basic eventual consistency.
¡ Strong convergence—Any two replicas that received the same set of updates are in
  the same state.

9.3.3 Implementation (125)

_Application-Specific Reconciliation

Algorithmic Reconciliation

conflict-free replicated data types (CRDTs)

Operation-based CRDTs known as commutative all operations are applied to the local state. In order to maintain consistency all operations must be sent and received.

State-based CRDTs known as convergent take all states and merge them locally. The merge function must be: associative, communities, and idempotent.

9.4 Consistency, availability, and partition tolerance (126)

Consistency, availability, and partition tolerance (CAP) is a way to talk about the trade-offs.

9.4.1 History (126)

It was first postulated that you must pick 2 of the 3 from above.

9.4.2 Conjecture vs. theorem (127)

¡ Consistency (informally)—Every read request receives a response indicating suc-
  cess and reflecting the value of the most recent write request or a response 
  indicating failure.
¡ Availability (informally)—Every read request eventually receives a response
  indicating success (not necessarily reflecting the value of the most recent write
  request).

9.4.3 CAP theorem (128)

System Model

3 Nodes: C, N1, N2
Partition between N1, and N2
C and communicate with N1, N2

The Proof

The choose to prove it but contradiction saying that there exists an algorithm exists that is all the above.

The Algorithm’s Failure

They say simply that if a write occurs on N1 and then a read occurs on N2 then we know consistent it is not.

Critique

¡ Brewer’s original interpretation of CAP is intuitive and practical, but it is not a
  theorem.
¡ Gilbert and Lynch’s subsequent interpretation of CAP is a theorem, but it is not
  intuitive or practical.