Distributed Systems Fundamentals

A distributed system is a collection of independent computers that appears as a single system to users. Distributed systems introduce challenges around consistency, coordination, and fault tolerance that do not exist in single-machine systems. This lesson covers consensus, distributed locks, clock synchronisation, and more.

---

Why Distributed Systems Are Hard

graph TD
  subgraph Single["Single-machine system: one clock, one memory, one process. Simple."]
    Box["Everything is in one place"]
  end
  subgraph Distributed["Distributed system: messages can be lost/delayed/reordered, nodes crash, clocks unsynced, no shared memory"]
    NA["Node A"] <-->|"network (unreliable)"| NB["Node B"]
    NA <--> NC["Node C"]
    NB <--> ND["Node D"]
    NC <--> ND
  end

The Eight Fallacies of Distributed Computing

Fallacy	Reality
The network is reliable	Packets get lost, connections drop
Latency is zero	Network calls take milliseconds to hundreds
Bandwidth is infinite	Limited and shared
The network is secure	Always assume untrusted
Topology doesn't change	Servers added/removed constantly
There is one administrator	Multiple teams, multiple data centres
Transport cost is zero	Serialisation, TLS, load balancers add cost
The network is homogeneous	Different hardware, software, protocols

---

Consensus Algorithms

When multiple nodes need to agree on a value (e.g. who is the leader, what is the latest committed transaction), they need a consensus algorithm.

Raft

Raft is designed to be understandable. It elects a leader, and the leader manages log replication.

graph TD
  L["Leader Node A (handles all client writes)"]
  L -->|"AppendEntries (replicate log)"| B["Follower B"]
  L -->|"AppendEntries (replicate log)"| C["Follower C"]
  L -->|"AppendEntries (replicate log)"| D["Follower D"]
  note["1. Client sends write to Leader. 2. Leader appends to log. 3. Leader replicates to followers. 4. Majority confirms then committed. 5. Leader responds to client."]

Raft Leader Election

1. Leader sends heartbeats every ~150ms
2. If a follower receives no heartbeat for a timeout period
   (randomised 150-300ms), it becomes a candidate
3. Candidate requests votes from other nodes
4. Node that receives majority of votes becomes leader
5. If split vote → increment term, new election

Paxos

Paxos is older and more general than Raft, but notoriously difficult to understand and implement. It uses proposers, acceptors, and learners.

Feature	Raft	Paxos
Understandability	High (designed for it)	Low (famously complex)
Leader	Single leader	Multi-proposer possible
Implementation	Simpler	Many variants, complex
Used by	etcd, Consul, CockroachDB	Google Chubby, Spanner

---

Distributed Locks

When multiple processes across different machines need exclusive access to a shared resource, they need a distributed lock.

Redlock Algorithm (Redis)

graph TD
  Client["Client"] -->|"1. Acquire lock on majority (3/5) of Redis nodes"| Nodes["Redis nodes"]
  Nodes --> R1["R1 ✓"]
  Nodes --> R2["R2 ✓"]
  Nodes --> R3["R3 ✓"]
  Nodes --> R4["R4 ✗"]
  Nodes --> R5["R5 ✗"]
  note["Lock acquired (3/5 = majority)"]

Key Properties of Distributed Locks

Property	Description
Mutual exclusion	Only one client holds the lock at a time
Deadlock free	Lock is released after a timeout even if holder crashes
Fault tolerant	Lock works even if some lock servers fail

When to Use Distributed Locks

• Correctness: When concurrent access would corrupt data (e.g. bank transfers)
• Efficiency: When duplicated work is expensive (e.g. avoid sending the same email twice)

---

Clock Synchronisation