Distributed Systems Algorithms: What Each One Solves

A distributed system is a group of computers that work together over a network. They share no memory and no clock. The only way one machine learns anything about another is by a message, and messages can be lost, delayed, duplicated or arrive out of order.

That one fact breaks most ordinary programming habits. You cannot ask "is that server dead?" and get a sure answer. A server that does not reply may be down, slow, or cut off by the network. You cannot compare two timestamps from two machines and trust the order, because their clocks drift apart.

So distributed systems use special algorithms. Each one solves one narrow problem under these conditions. Most of them answer a question that sounds simple: who is in charge, what happened first, does everyone know, or which copy is right.

Many systems need one node to make the final call. It orders writes, hands out locks, or runs a job that must run only once. That node is the leader. The trouble is that the nodes are peers. There is no boss to appoint one, so they must elect a leader using only network messages.

Two outcomes are bad. If two nodes both think they lead, you get split-brain: both accept writes, and the writes conflict. If no node thinks it leads, the system freezes. The lesson notes that when a Kafka cluster stops processing or a Kubernetes API server stops responding, the cause is often an election that failed or took too long.

The lesson covers four methods.

• Bully algorithm. The alive node with the highest ID wins. A node that notices the leader is gone messages every node with a higher ID. If none answer, it declares itself leader. Simple, but the highest ID wins even when that node is slow. About n squared messages.
• Ring election. Nodes form a logical ring. An election message travels all the way round, collecting IDs, and the highest ID wins. Fairer, but slow, because the message must visit every node in turn.
• Raft election. Followers wait a random timeout for the leader's heartbeat. The first to time out asks the others for votes, and a majority makes it leader. etcd, CockroachDB, TiKV and Consul use Raft or close variants.
• ZAB, ZooKeeper's protocol. It picks the node with the most complete transaction log, so the new leader never has to fetch missing entries from peers.

The lesson walks through etcd, the store behind Kubernetes. Its defaults are a 100 ms heartbeat and a 1,000 ms election timeout, randomized per follower to between one and two times the base. While etcd has no leader, the Kubernetes API server cannot accept writes. A slow election freezes deployments and scheduling for the whole cluster.

Three practices follow from the lesson. First, persist votes to disk before sending them. If a node could forget its vote after a crash, it could vote twice in one term and break safety. Second, run 3, 5 or 7 members, never an even number. Four members survive one failure, the same as three, but cost more per election. Third, watch the leader change counter. Frequent changes mean a flaky network, a slow disk or a timeout set too tight.

Kubernetes controllers use a lighter form of election called a lease. Several replicas run, but only the one holding a Lease object does work. The holder renews it every few seconds. If renewals stop, a standby takes over with a conditional update, and the API server lets only one such update win. The client-go defaults are a 15 second lease, a 10 second renew deadline and a 2 second retry period.

A lease alone is not enough. A paused process can wake up still believing it holds the lease. The fix is a fencing token, a number that grows with each new holder and that every write must carry, so writes from a stale holder are rejected. The distributed locks page covers this in detail.