Distributed System

---

tbd… A distributed system is many machines with no shared clock and independent failure, and the field is the work of reconstructing the two guarantees a single machine gave for free, a global “now” and all-or-nothing failure.

I

---

1.1. Beyond One Machine

tbd…

1.2. Time & Causality

tbd…

1.3. Failure & Impossibility

tbd…

II

---

2.1. Communication

The actor model, popularised by Erlang, encapsulates state within actors that communicate exclusively through asynchronous message passing, eliminating shared mutable state by design. Frameworks like Akka (JVM) and Ray (Python) implement this pattern. Message queues such as RabbitMQ and Apache Kafka extend asynchronous communication across services, decoupling producers from consumers for high-throughput stream processing with durability and replay guarantees.

2.2. Consistency & CAP

Distributed concurrency extends threading and synchronisation primitives across network boundaries, where communication is unreliable and latency is orders of magnitude higher than shared-memory access. Systems must contend with network partitions (where nodes cannot communicate), partial failures (where some nodes crash while others continue), and clock skew. The CAP theorem formalises a fundamental constraint, that a distributed system can guarantee at most two of Consistency, Availability, and Partition tolerance. In practice, partitions are inevitable, so systems choose between CP (e.g. ZooKeeper, etcd) and AP (e.g. Cassandra, DynamoDB) trade-offs. Eventual consistency relaxes strong guarantees, allowing replicas to temporarily diverge and converge over time through conflict resolution strategies such as last-writer-wins, vector clocks, or CRDTs.

2.3. Consensus

Consensus is the problem of getting multiple nodes to agree on a single value or sequence of values in the presence of failures. Paxos, proposed by Lamport (1998), was the first provably correct consensus protocol but is notoriously difficult to implement. Raft (2014) was designed as an understandable alternative, decomposing consensus into leader election, log replication, and safety. Both use quorum-based decisions, requiring a majority of nodes to agree before a value is committed. Coordination services like ZooKeeper and etcd build on consensus to provide distributed locks, leader election, and service discovery.

III

---

3.1. Distributed Data

MapReduce, introduced by Dean and Ghemawat at Google (2004), formalises a pattern where input data is split into partitions, each processed independently by a map function, and intermediate results are aggregated by a reduce function. Apache Spark improves upon Hadoop’s MapReduce with in-memory computation and lazy evaluation of RDD transformations, achieving significant speedups for iterative algorithms. The shuffle phase, where intermediate key-value pairs are redistributed across nodes, remains the primary bottleneck due to serialisation, network transfer, and disk I/O.

Database systems are among the most complex concurrent systems. Transaction isolation levels (Read Uncommitted, Read Committed, Repeatable Read, and Serialisable) define the degree to which concurrent transactions observe each other’s intermediate state. MVCC (Multi-Version Concurrency Control), used by PostgreSQL, MySQL/InnoDB, and Oracle, allows readers and writers to operate concurrently by maintaining multiple row versions, avoiding read-write locks entirely. Distributed databases like CockroachDB and Spanner extend these guarantees across nodes using distributed consensus and synchronised clocks.

3.2. Distributed ML

In ML, the key concurrency challenge is overlapping computation with communication. DataLoader prefetches batches concurrently with GPU computation, while DDP overlaps backward computation with gradient synchronisation via bucketed AllReduce, the primary communication bottleneck in distributed training. High-frequency trading represents the opposite extreme, with sub-microsecond latencies achieved through lock-free data structures (e.g. LMAX Disruptor), CPU affinity and interrupt isolation (isolcpus), and kernel bypass techniques (DPDK, RDMA).

---