Why Distribute, and Why It Is Hard

A distributed system is a group of computers that act as one

A distributed system is a set of independent computers (called nodes) that communicate only by sending messages over a network, yet try to look like a single coherent service to the user. We distribute for three reasons: fault tolerance (one machine will eventually die, so keep copies elsewhere), scale (one machine cannot hold all the data or serve all the requests) and latency (put data near users). The price is partial failure. On one laptop, a crash usually takes the whole program down, which is easy to reason about. In a cluster, one node can crash while others keep running, a network link can drop messages in one direction only, and a slow node looks exactly like a dead one from the outside. Every algorithm in this course exists to keep a group of nodes agreeing on facts despite this uncertainty.

The mental model for this course

Clients send requests to a replicated service; nodes exchange messages; some messages are lost or delayed and some nodes fail; a consensus protocol makes the survivors agree on one answer.

Why replicas: availability of a majority

If each node is independently down 1% of the time, how often is a majority unavailable? This is the arithmetic behind 3- and 5-node clusters. Real failures are often correlated (same rack, same bad deploy), so treat these numbers as an optimistic lower bound.

from math import comb

def p_no_majority(n, p_fail):
    """Probability that fewer than a majority of n nodes are up."""
    need = n // 2 + 1
    p_up = 1 - p_fail
    return sum(comb(n, k) * p_up**k * p_fail**(n - k) for k in range(0, need))

for n in (1, 3, 5, 7):
    print(f"n={n}: survives {(n - 1) // 2} crash(es), "
          f"P(cluster unavailable) = {p_no_majority(n, 0.01):.1e}")

Output:

n=1: survives 0 crash(es), P(cluster unavailable) = 1.0e-02
n=3: survives 1 crash(es), P(cluster unavailable) = 3.0e-04
n=5: survives 2 crash(es), P(cluster unavailable) = 9.9e-06
n=7: survives 3 crash(es), P(cluster unavailable) = 3.4e-07

Odd cluster sizes

A 4-node cluster tolerates only 1 crash, the same as 3 nodes, because a majority of 4 is 3. Adding the fourth node adds cost and one more voter to wait for, without adding fault tolerance. That is why consensus clusters are almost always 3, 5 or 7 nodes.

Quick check: What makes distributed systems fundamentally harder than a single-machine program?

• Programs must be written in a special language
• Parts of the system can fail independently while others keep running
• Networks are always too slow for databases
• Every node must have identical hardware