Multiprocessors, Multicomputers & Distributed Systems

When we say a system has "more than one CPU", we could mean three quite different things, and conflating them is the first mistake to avoid. The useful way to organise them is by how tightly the processors are coupled — how much they share and how tied together their fates are. As we loosen that coupling we gain the ability to scale to enormous size, and we pay with coordination problems that get progressively nastier.

Multiprocessor (shared memory)

Several CPU cores inside one machine, all reading and writing one physical memory, managed by a single OS. Your phone and laptop are here. Tightest coupling.

Multicomputer (cluster)

Many complete machines, each with its own CPU and its own private memory, tightly wired by a fast interconnect and cooperating by sending messages. No shared memory. HPC supercomputers live here.

Distributed system

Independent computers, often in different racks, rooms, or continents, cooperating over a general network. No shared memory, no shared clock, and no shared fate — each can fail on its own. Loosest coupling.

The single most important axis hiding in that table is shared fate. In a multiprocessor, if the machine dies, everything dies together — you never have to reason about "half the cores are up". In a distributed system the whole point is that one node can vanish while the rest carry on, which sounds like a feature (and it is) but turns out to be the source of almost every hard problem in the field. Hold that idea; the last three sections are essentially its consequences.

The dominant shape of a modern multiprocessor is SMP — symmetric multiprocessing. "Symmetric" means every core is equal: there is no master core, any core can run user code or kernel code, and they all reach the same physical memory through a shared interconnect. Critically, there is one operating system, one kernel image, cooperatively driving all the cores at once. When you buy an 8-core laptop, you are buying an SMP machine, and Linux runs a single kernel across all eight.

This is wonderful for programmers because the mental model barely changes: threads still share one address space, memory still looks like one flat array, and a thread can be picked up by any idle core. But running one kernel on many cores at once resurrects, at the kernel’s own level, the exact problem we studied in the concurrency chapters. Two cores can try to modify the same kernel data structure — the run queue of ready threads, the open-file table, a memory allocator’s free list — at literally the same instant.

So the scheduler you met earlier becomes a multi-core scheduler. Rather than one global run queue that every core fights over (a lock everyone contends for, which does not scale), modern kernels keep a per-core run queue and periodically balance load between them, pulling a waiting thread onto a core that has gone idle. And every shared kernel structure that two cores might touch has to be protected by exactly the locking discipline from the synchronization chapter — except now the "threads" contending are whole CPUs, and a lock held too long stalls real hardware.

• ▸One kernel drives all cores; any core can execute kernel code, so kernel data structures are shared and must be synchronized.
• ▸Per-core run queues with periodic load balancing beat a single global run queue, because a global queue becomes a contended lock that caps scalability.
• ▸Coarse locks are simple but serialize the kernel; fine-grained locks scale better but risk deadlock and are far harder to get right — the same trade-off you met for application code.
• ▸Cross-references: scheduling (the run queue and how a thread is chosen) and locks/mutexes (protecting the shared structures) are the two prior chapters you are now applying at kernel scale.

Here is the catch buried inside that friendly SMP picture. Each core has its own private caches (L1, L2) for speed, and those caches hold copies of memory. So the same memory address can sit in two cores’ caches at once. If core 0 writes a new value into its cache and core 1 keeps reading its own stale copy, the two cores now disagree about what memory says — and the tidy illusion of one shared memory shatters. This is the cache coherence problem.

Hardware solves it with a coherence protocol that the cores run among themselves over the interconnect, so that software mostly does not have to think about it. The classic one is MESI, named for the four states each cached line can be in. You do not need to implement it, but the intuition pays off when you reason about performance.

Modified

This core has the only copy and has changed it; memory is now stale. The core must write back before anyone else can read.

Exclusive

This core has the only copy and it matches memory. It can write freely without telling anyone (no other cache to invalidate).

Shared

Several cores hold identical read-only copies. Fine for reading; a write here forces the next state change.

Invalid

This copy is stale and must not be used. A core reaching this line must re-fetch a fresh copy.

The mechanism is simple to state: when a core wants to write a line that other caches hold, it broadcasts an invalidate, flipping every other copy to Invalid, so its write becomes the single source of truth. That keeps everyone honest — but it also means a write shared across cores is not free; it triggers cross-core traffic. This is why heavily shared, frequently written variables (a global counter behind every request, say) can quietly become a scaling bottleneck: the cache line ping-pongs between cores.

The subtlest trap is false sharing. Caches move data in fixed-size lines (commonly 64 bytes), not individual variables. If two threads on two cores update two different variables that happen to sit in the same cache line, the hardware cannot tell they are logically unrelated — every write invalidates the other core’s copy of the whole line, and the line bounces back and forth as if the threads were fighting over one variable. The code looks perfectly parallel and runs shockingly slowly. The fix is to pad or align hot per-thread data so unrelated fields land on separate cache lines.

Coherence answers "do all cores eventually agree on the value at an address?". A second, distinct question — memory consistency — asks "in what order does one core see another core’s writes become visible?". This is exactly the memory-model material from the previous chapter: because CPUs and compilers reorder operations for speed, a plain write by one thread may become visible to another out of program order. That is why concurrent code needs memory barriers and atomics, and why the language memory model exists. Coherence is about which value; consistency is about which order.

The neat SMP picture assumes every core reaches memory at the same speed. That holds for small machines, but once you scale to big servers with many sockets and lots of RAM, a single shared bus becomes a bottleneck — every core funnelling through one path cannot keep up. So large machines are built as several NUMA nodes: each node bundles a group of cores with a slice of memory that is physically attached to them, and the nodes are joined by an interconnect. NUMA stands for Non-Uniform Memory Access, and the non-uniformity is the whole point.

It is still one shared address space — any core can read any address, and coherence still holds across the whole machine. But the cost is no longer flat. Reaching memory on your own node (local access) is fast; reaching memory attached to another node (remote access) means a trip across the interconnect and is meaningfully slower, often by a large factor. The address is the same to your program; the latency is not.

This turns placement into a performance decision the OS must make, and it connects two chapters at once. The memory allocator wants to satisfy a thread’s allocation from its local node (a common policy is "first touch": the page is placed on the node of whichever core first writes it). The scheduler, meanwhile, wants to keep a thread running on the node where its memory already lives, and to avoid migrating a thread to a distant node where every memory access would suddenly go remote. When the allocator and scheduler cooperate, a NUMA machine flies; when a thread and its data drift onto different nodes, the same code silently slows down.

• ▸Local memory access is fast; remote access crosses the interconnect and is slower — same instruction, different cost depending on where the page physically lives.
• ▸NUMA-aware allocation ("first touch") places a page on the node of the core that first uses it, so hot data starts out local.
• ▸NUMA-aware scheduling keeps a thread on the node holding its memory and resists migrating it to a distant node.
• ▸On Linux, tools like numactl and the kernel’s automatic NUMA balancing exist precisely to keep threads and their pages on the same node.

Take the multiprocessor and cut the wire to shared memory. Now you have many complete computers — each with its own CPU and its own private RAM — bolted together by a very fast interconnect. This is a multicomputer, and its defining feature is what it lacks: there is no memory that two nodes can both touch. A node cannot learn what another node computed by reading a shared variable, because no such variable exists. The only way to communicate is to send a message.

That flips the programming model. In shared-memory code, communication is implicit and free-looking — you write to memory, another thread reads it (with all the coherence and locking caveats above). In message-passing code, communication is explicit: one node calls something like send() with a chunk of data, another calls recv() to receive it, and the data is physically copied across the interconnect. There is nothing to lock, because there is nothing shared; but there is nothing free either, because every exchange is an explicit transfer you must design.

This is the world of high-performance computing — the supercomputers that run weather models, physics simulations, and, increasingly, large-scale training jobs. The dominant standard for writing such programs is MPI (the Message Passing Interface): a library that gives you send/receive between thousands of nodes plus collective operations (broadcast a value to everyone, sum a value across everyone, and so on). You do not need MPI’s API memorised; you need the shift in mindset it represents.

Shared memory (SMP)

Communicate by reading and writing the same memory. Implicit, fast, but needs locks and coherence; limited to one machine.

Message passing (multicomputer)

Communicate by explicit send/recv of data copied over the interconnect. No shared state to lock, but every exchange is deliberate; scales to thousands of nodes.

MPI

The Message Passing Interface — the standard library for writing message-passing programs across the nodes of an HPC cluster.

Interconnect

The fast, tightly-coupled network joining the nodes (e.g. InfiniBand). Faster and more specialised than a general datacenter network.

A distributed system loosens the coupling one final notch. Now the cooperating computers are fully independent — separate machines, often in different racks or datacenters, joined by an ordinary network rather than a dedicated interconnect. This is the shape of essentially every real backend: web servers, databases, caches, queues, each a separate machine (or many), all talking over the network. And here three assumptions you have relied on for the entire course quietly disappear.

• ▸No shared memory: a machine knows only what it has been told in a message. There is no global variable, no shared data structure — every fact about another node is second-hand and possibly already out of date.
• ▸No shared clock: each machine has its own clock, and they drift. "Which event happened first?" has no reliable answer from timestamps alone, which breaks a surprising amount of naïve reasoning.
• ▸No shared fate — the defining one: any single machine can fail, or the network between two machines can fail, while everything else keeps running. This is partial failure, and it is the heart of what makes distributed systems hard.

Sit with partial failure, because it is genuinely new. On one machine, a component either works or the whole machine crashes with it — there is no middle. Across a network there is a permanent, unavoidable middle: you send a request to another node and no reply comes back. Now answer one question — what happened? Maybe the node crashed before receiving it. Maybe it received and did the work but the reply was lost. Maybe it is merely slow and the reply is still coming. Maybe the network between you is cut but the node is perfectly healthy and serving others. From where you stand these are indistinguishable, yet they demand different responses — and this ambiguity is why distributed algorithms are so careful and so counter-intuitive.

Because these traps are so easy to walk into, the field has a famous list: the eight fallacies of distributed computing — false assumptions that engineers new to distribution make by reflex. A few worth burning in: the network is reliable (it is not — packets drop, links fail); latency is zero (a remote call is orders of magnitude slower than a local one, so chatty designs crawl); bandwidth is infinite (it is not); the network is secure (assume it is hostile); and topology never changes (machines come and go constantly). Every one of these has produced real outages when assumed away.

Once machines are independent, three deep problems show up again and again. You will not derive their solutions here — each is a field of its own — but you should know the names, the shape of each problem, and why it is genuinely hard, so the tools you use later stop looking like magic.

First, ordering. With no shared clock, how do we agree on the order events happened across machines? Wall-clock timestamps lie because clocks drift. The classic answer is logical clocks — Lamport’s insight that we do not need real time, only a consistent notion of "this event happened before that one". Each node keeps a counter it bumps on every event and piggybacks on every message; the rule that a send always precedes its receive lets everyone agree on a partial order of events without any shared clock. It is a small idea with enormous reach — it underpins how distributed databases and version-control-like systems reason about causality.

Second, consensus: how do a group of machines agree on a single value — who is the leader, what is the next entry in the log, did this transaction commit — when messages can be lost or delayed and nodes can crash mid-vote? This is mutual exclusion’s harder cousin, and it is provably subtle. The workhorse algorithms are Paxos (correct, famously hard to understand) and Raft (designed to be understandable, now the default in new systems). The common trick is a majority quorum: get more than half the nodes to agree and you can tolerate a minority failing without ever letting two different values both "win". Raft and Paxos are what sit underneath systems like etcd, ZooKeeper, and the replication in modern distributed databases.

Third, the CAP theorem — the intuition every backend engineer should carry. Picture three properties: Consistency (every read sees the latest write, as if there were one copy), Availability (every request gets a non-error response), and Partition-tolerance (the system keeps working even when the network splits nodes into groups that cannot talk). CAP says that when a network partition happens — and on a real network it eventually will — you cannot have both C and A. You must choose: either refuse some requests to avoid returning stale or conflicting data (choose consistency, sacrifice availability), or keep answering from each side of the split and reconcile later (choose availability, sacrifice consistency). Partition-tolerance is not really optional on a real network, so CAP is best read as: "when — not if — the network partitions, do you drop consistency or availability?".

Logical clocks (Lamport)

Counters that establish a consistent "happened-before" order across machines without any shared or synchronized real-time clock.

Consensus (Raft / Paxos)

Algorithms letting a group agree on one value despite lost messages and crashed nodes, typically via a majority quorum. Raft favours understandability; Paxos came first.

CAP theorem

Under a network partition you can guarantee Consistency or Availability but not both; since partitions are inevitable, you are really choosing which to give up when one occurs.

Quorum

Requiring agreement from a majority (more than half) so the system tolerates a minority of failures while never letting two conflicting decisions both stand.

Step back and the payoff of putting this chapter last becomes clear: the coordination themes recur at every scale, and knowing the OS-level version gives you the datacenter-level version almost for free. The mutex that guards a shared variable between two threads is the same idea as a distributed lock that stops two service instances from processing the same job — except now "held too long" means a network timeout and "the holder crashed" is a real, routine event you must plan for. Cache coherence across cores is the small-scale rehearsal for replica consistency across nodes. The OS scheduling threads onto cores is mirrored by an orchestrator like Kubernetes scheduling containers onto machines.

This is why the abstractions you build on daily are shaped the way they are. Microservices are just message-passing between independent, separately-failing nodes — with all of Section 6’s partial-failure problems baked in, which is exactly why they need retries, timeouts, and idempotent handlers. A distributed database or a coordination service like etcd earns its keep by running the consensus algorithms of Section 7 so you do not have to. A distributed lock or leader election is mutual exclusion stretched across machines that can crash. None of it is new physics; it is the OS concurrency toolkit re-derived where the participants are whole computers.

Distributed lock

A mutex whose scope is many machines (built on etcd, ZooKeeper, or Redis). Must handle a holder that crashes or a network that partitions — the on-one-box mutex never had to.

Microservices

Independent services cooperating by messages over the network. Inherit every partial-failure problem, which is why resilient design (retries, timeouts, idempotency, circuit breakers) is mandatory, not optional.

Replication & consensus

Keeping copies of state across nodes consistent, using quorum-based algorithms (Raft/Paxos). The scaled-up cousin of cache coherence.

That closes Part F. You have taken the single-machine OS — processes, scheduling, memory, concurrency — and scaled it outward: to many cores sharing memory under one kernel (SMP, coherence, NUMA), to many boxes passing messages (multicomputers, MPI), and finally to independent machines coordinating despite partial failure (distributed systems, consensus, CAP). The recurring lesson is that the fundamentals do not change with scale; only their difficulty and their names do.