9. Consistency and Consensus

Question 1

Distributed Consistency such as Linearizability

VS

Transaction Isolation such as Serializability.

Answer 1

Distributed consistency is about coordinating the state of replicas in the face of delays and faults.

Linearizability is one of consistency models. Its goal is to make replicated data appear as though there were only a single copy.

Transaction isolation is about avoiding race conditions due to concurrently executing transactions.

Serializability is one of transaction isolation, where every transaction may read and write multiple objects, it guarantees that transactions behave the same as if they has executed in some serial order.

Question 2

Consistency model - Causality.

Answer 2

Causality imposes an ordering on events in a system (what happened before what, based on cause and effect).

Causality provides weaker consistency model compared to linearizability. Things can be concurrent but it doesn’t have coordination overhead of linearizability and is much less sensitive to network problems.

Question 3

Total Order Broadcase

Answer 3

Total order broadcast is usually described as a protocol for exchanging messages between models. It has two properties:

1. Reliable delivery: no messages are lost
2. Totally ordered delivery: messages are delivered to every node in the same order.

Question 4

Consensus - what

Answer 4

Consensus means deciding something that all nodes agree on.

Question 5

Consensus - why

Answer 5

Considered the example of ensuring that a username is unique and rejecting concurrent registrations for the same username. If one node is going to accept a registration, it needs to somehow know that another node isn’t concurrently in the process of registering the same name.

Question 6

Problems equivalent to Consensus

Answer 6

1. Linearizable compare-and-set registers
   The register needs to atomically decide whether to set its value, based on whether its current value equals the parameter given in the operation.
2. Atomic transaction commit
   A database must decide whether to commit or abort a distributed transaction.
3. Total order broadcast
   The messaging system must decide on the order in which to deliver messages.
4. Locks and leases
   When several clients are racing to grab a lock or lease, the lock decides which one successfully acquired it.
5. Membership/coordination service
   Given a failure detector (e.g., timeouts), the system must decide which nodes are alive, and which should be considered dead because their sessions timed out.
6. Uniqueness constraint
   When several transctions concurrently try to create conflicting records with the same key, the constraint must decide which one to allow and which should fail with a constraint violation.

Question 7

ZooKeeper

Answer 7

ZooKeeper plays an important role in providing an “outsourced” consensus, failure detection, and membership service that applications can use.