Consensus; highly available service

Reaching consensus

Consensus means that all correct processes agree on the same value, though some may fail. Properties: termination (every correct process decides), agreement (same decision), validity (decided value was proposed).

Approach (synchronous system, up to f crash failures):

1. Every process Pi holds a proposed value in its set Vi.
2. For f+1 rounds, each process multicasts values in its set that it has not sent before.
3. Each process merges the values it receives into Vi.
4. After round f+1, each process decides by the same function (e.g. minimum value or majority). In at least one of the f+1 rounds no process crashes, and in that round all correct processes learn the same values, so they end up with the same set and agree.

For asynchronous systems with crash failures, Paxos/Raft reach agreement by electing a leader and obtaining acceptance from a majority quorum; for Byzantine faults 3f+1 processes are needed.

Making a service highly available

A service is highly available if clients get a response with high probability even when some servers fail. The approach is replication:

1. Keep copies of the data and service on several servers, preferably on different machines, networks and sites.
2. A front end (proxy) sends client requests to the replicas, and may send to several, taking the first reply.
3. Primary-backup or active replication keeps replicas consistent; with the primary down, a backup is promoted by an election/consensus (e.g. bully algorithm) without service interruption.
4. Use of heartbeat failure detection, automatic failover, load balancing, and (lazy) update propagation, as in the gossip architecture, where any replica can respond.
5. Availability with n replicas each with failure probability p is 1 − pⁿ; e.g. with p = 0.05 and 3 replicas: 1 − 0.000125 = 99.9875%.