Distributed Systems Fundamentals

Why One Computer Is Easy And Many Are Hard

In week 1 you learned that a distributed system is a group of computers acting as one. This week we ask what makes that hard. The answer fits in one sentence: the computers share no memory and no clock, so they can only learn about each other by sending messages, and messages can go wrong.

On a single computer, a program reads a value from memory and gets an answer right away. If the computer breaks, everything stops together, and that is easy to notice. In a distributed system, one machine may break while the others continue. Messages take time. Two machines may disagree about what happened first.

Engineers sometimes call these the eight fallacies of distributed computing, a list attributed to Peter Deutsch and colleagues at Sun Microsystems. They are false beliefs beginners hold: the network is reliable, latency is zero, bandwidth is infinite, the network is secure, the topology never changes, there is one administrator, transport cost is zero, and the network is the same everywhere. Each belief causes bugs when the system leaves the lab.

Networks And Messages

A network carries messages between computers. A message is a chunk of bytes with an address. The Internet sends messages as small packets, and each packet may take its own path. The sender cannot see the path, so it cannot tell whether a packet is slow or gone.

Two protocols matter most. UDP sends a packet and forgets it. If the packet is lost, nobody is told. TCP adds numbering and acknowledgments: the receiver confirms what arrived, and the sender resends what did not. TCP gives the application an ordered, reliable stream, but only while the connection stays alive. If the connection breaks, TCP reports an error, and the application must decide what to do.

Even with TCP, an application can end up unsure. Suppose you send 'transfer 10 coins' and the connection drops before you hear back. Did the transfer happen? You do not know. The safe design is to make operations repeatable: if you send the same request twice, the result is the same as sending it once. Engineers call this property idempotence.

Latency And Bandwidth

Latency is the time for one message to travel from sender to receiver. Bandwidth is how much data the link carries per second. A motorway analogy helps: latency is the length of the road, and bandwidth is the number of lanes. More lanes do not shorten the road.

Latency has a hard floor set by physics. Light in a vacuum travels about 300,000 kilometers per second. In optical fiber it travels roughly two thirds as fast. A signal crossing 5,000 kilometers of fiber needs around 25 milliseconds one way, so a round trip costs at least 50 milliseconds before any computer does any work. No software update can remove that time.

Because of this floor, location matters. A user in Kuala Lumpur reading a database in Virginia will always wait longer than a user near it. Content delivery networks and regional replicas exist for this reason: they place copies of data close to users.

In real networks latency also varies. Queues in routers, busy servers and long routes add delay. Designers therefore think in terms of typical and worst-case times, and they set timeouts: a rule that says, give up waiting after this many seconds.

Failures And Partial Failure

Machines fail in many ways. A disk dies, a process crashes, a power cable comes loose, a software update contains a bug, a cable under the sea is cut. A crash failure means the machine stops. A more difficult case is when it keeps running and returns wrong answers.

Distributed systems face partial failure: some parts work while others do not. This is the biggest difference from a single computer. A request may succeed on three machines and fail on the fourth, and the system must continue sensibly.

Imagine machine A asks machine B a question and hears nothing for ten seconds. B may have crashed. B may be busy. The network between them may be broken. B's answer may be on its way. A cannot tell these cases apart from the outside. This is why timeouts are only guesses, not facts.

A network partition is the special case where the network splits the machines into groups that cannot talk to each other, though each group may work fine inside. Partitions are rare on a good day and always eventually happen. Real systems are built on the assumption that they will.

Time, Order And Replication

Each computer has its own clock, and clocks drift apart. Even with synchronization services, two machines can disagree by milliseconds or more. If two events happen close together on different machines, timestamps cannot always show which came first.

Distributed systems often use logical order instead of wall-clock time. Leslie Lamport's 1978 paper 'Time, Clocks, and the Ordering of Events in a Distributed System' showed that you can order events by what could have influenced what, using simple counters carried along in messages. We will use this idea in week 4.

To survive failure, systems keep several copies of the same data. These copies are called replicas, and keeping them in step is replication. If one replica dies, others serve users. The price is that a write must reach every replica, and replicas may briefly show different values.

Consistency is the word for how closely the replicas agree. Strong consistency means that after a write finishes, every reader sees the new value. Weaker forms allow readers to see older values for a while.

The CAP Theorem

Computer scientist Eric Brewer stated the idea in a talk in 2000, and Seth Gilbert and Nancy Lynch proved a precise version in 2002. It speaks about three properties of a replicated data service.

Consistency (C) means every read sees the most recent write. Availability (A) means every request to a working machine receives an answer. Partition tolerance (P) means the system keeps going when the network drops messages between machines.

The theorem says: when a partition happens, a system must choose between consistency and availability. It cannot provide both. Picture two replicas holding a bank balance, cut off from each other. A user asks the left replica to withdraw money. If the left replica answers, it risks disagreeing with the right one, so consistency is lost. If it refuses to answer until the network heals, availability is lost.

The popular phrase 'pick two of three' misleads, because partitions are not optional in a real network. The honest reading is: since partitions happen, you decide which of C or A to give up while they last. When the network is healthy, you can have both.

• CP systems refuse some requests during a partition to stay correct
• AP systems keep answering during a partition and repair differences later
• The choice depends on the cost of a wrong answer versus a missing answer

Eventual Consistency

Many systems choose availability and accept brief disagreement. Eventual consistency promises this: if no new writes arrive, all replicas will in time hold the same value. Werner Vogels, then at Amazon, described this style in a 2008 article titled 'Eventually Consistent'.

A social feed shows the idea. You post a photo, and a friend in another country sees it a few seconds later. Nobody is harmed. A bank balance is different, because a stale answer can let someone spend money twice. Designers pick the weaker model where staleness is cheap and the stronger model where it is costly.

When two replicas receive different writes during a partition, they must reconcile later. A simple rule is last write wins: keep the value with the newest timestamp. It is easy but can discard a legitimate update, and it relies on clocks. Better rules merge both updates, as in shopping carts that keep every item added on either side. Special data types called CRDTs (conflict-free replicated data types) are designed so that merging always gives the same result in any order.

Blockchains, which we meet from week 4, take a different path. They use agreement protocols to give all participants one shared history, accepting delay as the price.

Design Habits That Follow

Four habits come out of this week. First, assume any message may be late, lost or duplicated, and make operations safe to repeat. Second, treat timeouts as hints and design recovery for the case where you guessed wrong. Third, decide for each piece of data whether stale reads are acceptable. Fourth, test failure on purpose: stop a machine, slow a network link, and watch what happens.

These habits matter more when no single owner controls the machines, which is the situation in decentralized systems. In week 3 you will see how peers in a network find each other despite these problems.

Key Terms

Latency

The time a message needs to travel from sender to receiver.

Bandwidth

The amount of data a link can carry per second.

Timeout

A rule that stops waiting for a reply after a chosen time.

Partial failure

A situation where some parts of a system work while others fail.

Network partition

A network split that stops groups of machines from reaching each other.

Replica

One of several copies of the same data kept on different machines.

Idempotence

A property of an operation that gives the same result when repeated.

CAP theorem

During a network partition, a replicated service must give up either consistency or availability.

Eventual consistency

A promise that replicas will agree after writes stop and messages are delivered.

Exercise: Two Replicas That Drift And Heal

1. Install Python 3 (free from python.org) and create a file named replicas.py.
2. Paste the sample code from the slide titled 'Eventual consistency in 12 lines' and run it with python3 replicas.py.
3. Read the output and write down the value of each replica before and after the merge.
4. Change the merge rule so that the larger number wins instead of the later write, and run again.
5. Add a third replica and make all three sync with each other. Check that all values match.
6. Write a short note: in which real service would last write wins be acceptable, and in which would it be dangerous?

Further Reading

• Designing Data-Intensive Applications (chapters 8 and 9: The Trouble with Distributed Systems, Consistency and Consensus), Martin Kleppmann, O'Reilly
• CAP Twelve Years Later: How the Rules Have Changed, Eric Brewer, IEEE Computer, 2012
• Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services, Seth Gilbert and Nancy Lynch, ACM SIGACT News, 2002
• Eventually Consistent, Werner Vogels, Communications of the ACM, 2009
• Time, Clocks, and the Ordering of Events in a Distributed System, Leslie Lamport, Communications of the ACM, 1978