1. The Illusion of a Single Machine

When you use a search engine or a social network, you interact with it as a single, coherent entity. But behind the curtain, it's a sprawling, chaotic system of thousands of computers.

When you use a search engine, book a flight, or check your bank balance, you interact with what appears to be a single, monolithic application. It's an illusion. Behind that simple web interface lies a system composed of hundreds or thousands of independent computers, scattered across datacenters around the globe. Our entire modern digital infrastructure is built this way. Why? For scalability and fault tolerance. A single machine, no matter how powerful, has limits. A system of many can handle immense load and can, in theory, survive the failure of some of its components. But this architecture introduces a fundamental puzzle: how do you maintain the illusion of a single, coherent system when it's actually a loosely coupled collective of independent, failure-prone parts? If you make a bank transfer, how do all the database replicas agree on your new balance, especially if a network link between them is severed? If one machine fails mid-calculation, how does the rest of the system know to pick up the work without producing an incorrect result? Getting this wrong means corrupted data, inconsistent states, and catastrophic system failure. This is the central problem we will spend this course trying to solve.

• Getting this wrong means corrupted data, inconsistent states
• Behind that simple web interface lies a system composed of hundreds
• A single machine, no matter how powerful, has limits
• Our entire modern digital infrastructure is built this way
• A system of many can handle immense load

2. What Is a Distributed System?

A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable.

That witty and slightly terrifying definition comes from Leslie Lamport, a foundational figure in this field. It captures the most salient property of these systems: non-local effects and partial failure. A more formal definition, from Andrew Tanenbaum, is that a distributed system is 'a collection of independent computers that appears to its users as a single coherent system.' Let's break that down. 'A collection of independent computers' means we have multiple nodes, each with its own private memory and operating system. They are autonomous. They communicate by passing messages over a network. 'Appears to its users as a single coherent system' is the crucial part. The complexity, the distribution, the failures—all of that should be hidden from the user. This property is often called transparency, or more specifically, distribution transparency. The system manages its own internal complexity, presenting a clean, simple abstraction. The entire field, in many ways, is about building and maintaining this abstraction in the face of the inherent messiness of the physical world.

• They communicate by passing messages over a network
• It captures the most salient property of these systems: non-local effects
• The entire field, in many ways
• 'Appears to its users as a single coherent system'
• The complexity, the distribution, the failures—all of that should be hidden

3. From ARPANET to the Cloud

The internet began as a distributed system designed to survive a nuclear attack. The core principles of fault tolerance have been with us from the beginning.

The intellectual roots of distributed systems are deep, but a practical starting point is the ARPANET in the late 1960s. It was explicitly designed as a decentralized, packet-switching network that could withstand the failure of individual nodes or links—a direct response to the Cold War threat of nuclear attack. The theoretical foundations were laid in the late 1970s and 1980s. This was the era of seminal papers. Leslie Lamport's 1978 paper 'Time, Clocks, and the Ordering of Events in a Distributed System' gave us the formal tools to reason about causality without a global clock. Then, in 1985, the famous 'FLP result' from Fischer, Lynch, and Paterson proved that reaching consensus in a purely asynchronous system is impossible if even a single process can fail. This impossibility result didn't stop the field; it defined its boundaries and forced researchers to design practical systems that worked around these fundamental limits. The 2000s saw the rise of industrial-scale distributed systems, driven by companies like Google, who published influential papers on their internal infrastructure like the Google File System and MapReduce, kicking off the 'big data' and cloud computing era we live in today.

• Then, in 1985, the famous 'FLP result' from Fischer, Lynch
• Leslie Lamport's 1978 paper 'Time, Clocks
• The 2000s saw the rise of industrial-scale distributed systems
• It was explicitly designed as a decentralized
• This impossibility result didn't stop the field; it defined its boundaries

4. The Three Fundamental Challenges

Why is this so hard? It boils down to three unavoidable truths: things fail, things happen at the same time, and nobody knows what time it is.

Unlike programming a single computer, designing a distributed system forces you to confront three fundamental and unavoidable challenges. First, partial failure. A single computer usually fails completely—a 'fail-stop' model. A distributed system, however, can fail partially. One server might crash, a network link might become slow or drop packets, while the rest of the system continues to operate. The system is in a state of being neither fully functional nor fully broken, and reasoning about all possible partial failure modes is immensely complex. Second, concurrency. Multiple processes on multiple machines are executing simultaneously and interacting with each other. Without the guardrails of shared memory and locks that we have on a single machine, coordinating these concurrent actions to maintain a consistent state is a major challenge. Third, and most subtle, is the lack of a global clock. Each computer has its own physical clock, but these clocks are not perfectly synchronized and they drift apart over time. There is no single, unambiguous source of truth for the time. This means we cannot rely on timestamps to determine the order of events across different machines. This single fact has profound consequences, forcing us to rethink our entire notion of time and causality, which we'll formalize next.

• Multiple processes on multiple machines are executing simultaneously
• The system is in a state of being neither fully functional
• Most subtle, is the lack of a global clock
• Without the guardrails of shared memory
• Each computer has its own physical clock

5. The Happened-Before Relation

To bring order to the chaos of distributed events, we need a way to talk about causality without talking about time. This is the 'happened-before' relation.

To reason about distributed systems, we need a formal model. We model a system as a collection of processes. Each process is a sequence of events. An event can be internal to a process, or it can be the sending or receiving of a message. In his 1978 paper, Lamport defined the 'happened-before' relation, denoted by an arrow. This relation allows us to create a partial ordering of events in the system without relying on physical clocks. The definition is inductive and based on three simple rules. First, if two events, 'a' and 'b', occur in the same process, and 'a' occurs before 'b' in that process's sequence, we say 'a' happened-before 'b'. Second, if event 'a' is the sending of a message and event 'b' is the reception of that same message, then 'a' happened-before 'b'. You can't receive a message before it's sent. Third, the relation is transitive. If 'a' happened-before 'b', and 'b' happened-before 'c', then 'a' happened-before 'c'. This builds causal chains. If two events are not related by this relation, they are defined as concurrent. We write this as 'a' is parallel to 'b'. This formalism is the bedrock of reasoning about distributed algorithms.

• An event can be internal to a process
• In his 1978 paper, Lamport defined the 'happened-before' relation
• This formalism is the bedrock of reasoning about distributed algorithms
• The definition is inductive and based on three simple rules
• 'b' happened-before 'c', then 'a' happened-before 'c'

6. Implications of a Partial Order

The happened-before relation doesn't tell us the 'true' order of all events. It tells us something much more important: which events could have possibly affected which other events.

The most important implication of the happened-before relation is that it defines a partial order on the set of all events in the system. It does not define a total order. In a total order, for any two distinct events 'a' and 'b', either 'a' comes before 'b' or 'b' comes before 'a'. In our partial order, there's a third possibility: they are concurrent. This isn't a limitation of the model; it is a feature that accurately reflects the physical reality of a distributed system. The happened-before relation captures potential causality. If 'a' happened-before 'b', then it is possible that event 'a' had some causal effect on event 'b'. If 'a' and 'b' are concurrent, then it is impossible for them to have affected one another. They are causally independent. This insight is incredibly powerful. It allows us to analyze the correctness of distributed algorithms by examining the causal relationships between their constituent events. It's the tool we use to determine if a database is providing consistent views of the data, or if a distributed computation has race conditions. This concept of a partial, causal ordering is a fundamental departure from the sequential, totally-ordered world of single-machine computation.

• Defines a partial, not total, order of events.
• Captures potential causality within the system.
• Formally defines concurrency between events.
• Forms the basis for algorithms like vector clocks.

7. A Space-Time Diagram in Action

Let's visualize causality. A space-time diagram maps processes against time, showing the flow of messages and the ordering of events.

Let's make this concrete with a space-time diagram. Imagine three processes, P1, P2, and P3, running over time, which flows from left to right. Each process executes a sequence of events. Let's say P1 executes event e11, then sends a message to P2. P2 receives this message at its event e21, does some computation, and then has a final event e22. Meanwhile, P3 is just doing its own thing, executing event e31. Let's apply our rules. Within P2, e21 happened-before e22 by Rule 1. Because P1 sent the message at e11 and P2 received it at e21, we know by Rule 2 that e11 happened-before e21. Now, using transitivity, since e11 happened-before e21, and e21 happened-before e22, we can conclude that e11 happened-before e22. The initial event at P1 causally precedes the final event at P2. What about event e31 at P3? There is no chain of messages connecting it to the events at P1 or P2. Therefore, e31 is concurrent with e11, e21, and e22. We cannot say which 'happened first' in any meaningful way. They are in different causal realities, so to speak.

• P2 receives this message at its event e21, does some computation
• Meanwhile, P3 is just doing its own thing, executing event e31
• There is no chain of messages connecting it to the events
• Each process executes a sequence of events
• Three processes, P1, P2, and P3, running over time

8. The Cost of Coherence

Making a distributed system act like a single machine isn't free. The price is paid in performance, availability, and complexity.

The goal of making a distributed system appear as a single, coherent whole is a powerful abstraction, but achieving it involves fundamental tradeoffs. If we want strong consistency—for example, ensuring every user of a social media site sees the exact same set of posts in the exact same order at the exact same time—we need coordination. The nodes in the system must communicate, exchange information, and run a consensus protocol to agree on the state of the world. This coordination takes time. It introduces latency. Sending messages across continents is bound by the speed of light. Furthermore, this requirement for agreement can reduce the system's availability. If a set of nodes cannot communicate with another set due to a network partition, a system that prioritizes consistency might have to halt operations entirely to avoid serving inconsistent data. This is the core tension captured later by the CAP theorem, which states that a system can only provide two out of three guarantees: Consistency, Availability, and Partition Tolerance. Since network partitions are a fact of life, the real choice is between consistency and availability. There is no single 'best' system; there are only systems that make different tradeoffs for different use cases.

• The nodes in the system must communicate, exchange information
• Core tension captured later by the CAP theorem
• This requirement for agreement can reduce the system's availability
• A system that prioritizes consistency might have to halt operations entirely
• The real choice is between consistency and availability

9. Distributed vs. Parallel vs. Concurrent

These terms are often used interchangeably, but they describe distinct concepts with different goals and challenges.

It's important to be precise with our terminology. Let's distinguish distributed computing from two related concepts: parallel and concurrent computing. Parallel computing is primarily about performance. It uses multiple processing units, often tightly coupled with shared memory, to solve a single, large computational problem faster. Think of rendering a 3D movie or running a scientific simulation on a supercomputer. The goal is speedup. Concurrent programming is a property of a program's structure, allowing multiple tasks to be in progress at the same time. This can happen on a single CPU core through interleaving, or on multiple cores. It is about dealing with shared resources and logical control flow, but not necessarily about physical distribution. Distributed computing is different. Its primary challenges are not just about speed, but about handling partial failure and the lack of a shared state or clock across physically separate machines. While a distributed system is inherently concurrent, its defining problems are fault tolerance, scalability, and managing consistency over an unreliable network. The goal is to build a reliable system out of unreliable parts.

• It uses multiple processing units, often tightly coupled with shared memory
• It is about dealing with shared resources and logical control flow
• Its defining problems are fault tolerance, scalability
• Think of rendering a 3D movie or running a scientific
• Concurrent programming is a property of a program's structure

10. The Eight Fallacies of Distributed Computing

Engineers new to distributed systems often carry assumptions from single-machine programming. These assumptions are not just wrong; they are dangerously wrong.

In the 1990s, a group at Sun Microsystems, including Peter Deutsch, compiled a list that has become canonical: the Eight Fallacies of Distributed Computing. These are a set of assumptions that every programmer implicitly makes about a local computation, but that are demonstrably false when working with a network. For example, the first fallacy is 'the network is reliable.' It isn't. Packets are dropped, links fail, routers crash. Your code must assume failure and handle it gracefully, perhaps by retrying. The second is 'latency is zero.' It isn't. The speed of light is a hard limit, and network congestion adds variable delays. Ignoring this leads to performance bottlenecks. The third, 'bandwidth is infinite,' is equally false. Other fallacies include assuming the network is secure, that the network topology doesn't change, that there is only one administrator, and that transport cost is zero. Building a robust distributed system begins with acknowledging that all eight of these assumptions are false. Every successful system is, in essence, a collection of engineering solutions designed to mitigate the consequences of these fallacies.

• In the 1990s, a group at Sun Microsystems, including Peter Deutsch
• The first fallacy is 'the network is reliable.' It isn't
• The third, 'bandwidth is infinite,' is equally false
• These are a set of assumptions that every programmer implicitly makes
• The second is 'latency is zero.' It isn't

11. Essential Papers and Tools

To truly understand this field, you must go to the source. The foundational papers are as important today as when they were written.

Beyond this course, your most important resources will be the primary literature and modern texts that synthesize it. You should read Lamport's 'Time, Clocks...' paper. It is clear, foundational, and surprisingly accessible. You should also be familiar with the FLP impossibility result, which sets the boundaries of what is possible. For a modern, practical perspective, Martin Kleppmann's book, 'Designing Data-Intensive Applications', is indispensable. It connects the theory to the architecture of real-world databases and stream processors. When it comes to tools, you should get your hands dirty. Start with a modern remote procedure call framework like gRPC to understand the mechanics of communication. For those of you interested in the formal side, Leslie Lamport also created TLA+, a formal specification language used at companies like Amazon Web Services to design and verify the correctness of complex distributed algorithms before a single line of implementation code is written. It is a tool for thinking clearly about concurrency and failure.

• You should also be familiar with the FLP impossibility result
• For a modern, practical perspective, Martin Kleppmann's book, 'Designing Data-Intensive Applications'
• It connects the theory to the architecture of real-world databases
• Start with a modern remote procedure call framework like gRPC
• For those of you interested in the formal side

12. Build a Happened-Before Detector

This week's problem set: move from theory to practice. You will write a program that can determine the causal relationship between any two events in a simulated distributed system.

For your first assignment, you will implement the core logic we've discussed today. You will build a small simulation of a distributed system with three processes. These processes can perform two types of actions: an internal event, or sending a message to another process. Your program will take a script of these actions as input, such as 'P1 sends to P2', 'P3 internal', 'P2 sends to P1', and so on. It will simulate the execution and generate a complete log of all events that occurred in the system. The main task is to then write a function that, given any two events from this log, can determine their causal relationship. Your function should output one of three results: 'A happened-before B', 'B happened-before A', or 'A and B are concurrent'. To do this, you cannot use a global clock or a simple counter. You must derive the relationship solely from the three rules of the happened-before relation. This exercise will force you to internalize how causality is tracked in a system where the only shared information is that which is explicitly communicated in messages.

• These processes can perform two types of actions: an internal event
• The main task is to then write a function
• It will simulate the execution
• This exercise will force you to internalize how causality is tracked
• For your first assignment, you will implement the core logic we've

13. Agreeing to Disagree on Time

Today we defined distributed systems as independent computers that create the illusion of a single, coherent machine. We explored the fundamental challenges of partial failure, concurrency, and the lack of a global clock that make this illusion so difficult to maintain.

• A distributed system appears as one but is composed of many autonomous, networked computers.
• The core challenges are partial failure, concurrency, and the absence of a global clock.
• The 'happened-before' relation provides a formal way to reason about causality without physical time.
• Happened-before defines a partial order, where some events are causally related and others are concurrent.
• Building robust systems requires acknowledging the fallacies of distributed computing from the start.

Mastery quiz

1. What does the Two Generals' Problem demonstrate about distributed systems?
   • Two processes cannot agree on a mutual course of action over an unreliable communication channel
   • Two armies can always coordinate if they send enough messengers
   • Messages always arrive eventually given infinite time
   • A single fast computer can solve any coordination problem
2. Which three fundamental challenges does the lecture say designing a distributed system forces you to confront?
   • Partial failure, concurrency, and the lack of a global clock
   • Encryption, compression, and routing
   • Memory leaks, deadlocks, and stack overflows
   • Latency, bandwidth, and storage cost
3. According to the happened-before relation, when are two events defined as concurrent?
   • When they are not related by the happened-before relation
   • When they occur on the same process
   • When one is the send and the other is the receive of the same message
   • When they have identical physical timestamps
4. What does the CAP theorem state a system can guarantee, and what is the real practical choice?
   • Only two of Consistency, Availability, and Partition tolerance; since partitions are unavoidable, the choice is between consistency and availability
   • All three of Consistency, Availability, and Partition tolerance simultaneously
   • Only speed and cost, trading one for the other
   • Consistency only, never availability