Distributed Computing Fundamentals

Distributed computing uses several independent computers to perform one larger computation or provide one service. The computers coordinate by sending messages across a network.

That arrangement can add capacity, shorten processing time, place work near data, and survive some failures. It also removes assumptions that local programs often make. Messages take time. Machines do not share one perfect clock. One component can fail while the rest continue.

The central skill is not memorizing a framework. It is learning which facts each computer can know, when it can know them, and what happens when communication stops.

The basic shape

Picture a large input divided into partitions. Workers process those partitions at the same time. A coordinator assigns work and combines results.

input → partition → worker A → result A
      ↘ partition → worker B → result B → combined result
      ↘ partition → worker C → result C

Google's MapReduce design is a concrete example. A map function produces intermediate key-value pairs. A reduce function combines values for each key. The runtime partitions input, schedules tasks, manages communication, and reassigns failed work.

This pattern works best when useful work can be divided. More workers do not guarantee a faster result. Coordination, network transfer, uneven partitions, and sequential steps can dominate the runtime.

Distribution changes the failure model

A local function either returns, raises an error, or keeps running. A remote operation adds an ambiguous outcome.

Suppose a client sends a request and times out. The server might never have received it. The server might have completed it while the reply was lost. The server might still be working.

The client cannot distinguish those cases from the timeout alone. Retrying is safe only when the operation is idempotent, meaning repeated execution has the same intended effect as one execution.

Failures are often partial. One worker can crash while others continue. A network partition can split healthy machines into groups that cannot communicate. Redundant copies help only when they do not share the same failure cause.

Design from explicit assumptions:

Which failures can occur?
Can messages be delayed, lost, duplicated, or reordered?
Does a stopped worker recover with durable state?
How long may the system wait before reducing service?
Which component decides whether work is complete?

Time is not one global sequence

Each machine observes its own events and received messages. Physical clocks drift, and network delay varies. Two distant events may have no observable cause-and-effect relationship.

Lamport's happened-before relation captures causal order. An earlier event in one process happened before a later event in that process. Sending a message happened before receiving it. The relation also carries through chains of such events.

If neither event happened before the other, they are concurrent. A logical clock assigns timestamps that respect happened-before order. It does not reveal the exact wall-clock time or prove causality from timestamp order alone.

This distinction matters when you merge updates, inspect traces, or reproduce a failure. A timestamp can help order observations, but its meaning depends on the clock model.

State, replication, and consistency

Parallel workers can process independent input without sharing much mutable state. Stateful services are harder because several machines may hold copies of the same data.

Replication stores or executes the same logical state on multiple machines. It can improve availability and read capacity. It also creates a coordination problem: which updates are accepted, and when may a copy answer a read?

A consistency model defines which results clients may observe. Stronger consistency can make a replicated service behave more like one copy. Weaker models can permit older or differently ordered observations in exchange for other properties.

The CAP result is narrow and precise. In an asynchronous system that may lose messages, an atomic read-write object cannot guarantee a response from every nonfailed node during a network partition. During that partition, the design must give up either that availability guarantee or atomic consistency.

CAP is not a menu for choosing two properties during normal operation. It describes behavior when communication is partitioned under a specific model.

Consensus and replicated state machines

Some problems require machines to agree on one ordered sequence of decisions. Leader election and replicated logs are common examples.

Consensus lets participating machines agree on a value despite some failures. A practical consensus algorithm has a stated fault model and progress conditions. It does not make all failures harmless.

Raft organizes consensus around leader election, log replication, and safety. Its leader accepts commands and replicates log entries. Deterministic state machines that apply the same committed commands in the same order produce the same state.

A majority matters because two majorities overlap. Under Raft's assumptions, a cluster can continue when a communicating majority remains. A minority cannot safely commit a competing history.

Consensus is coordination infrastructure, not a default tool for every distributed task. Independent computations often need scheduling and retry rather than global agreement.

Partitioning, placement, and movement

Partitioning divides data or work into separate units. Good partitioning creates enough independent work and keeps related operations together.

Placement then decides which worker handles each partition. Place computation near its input when network transfer is expensive. Rebalance when a worker fails or load changes.

Watch for three costs:

Skew: one partition contains much more work than others.
Shuffle: intermediate data crosses the network before the next stage.
Stragglers: slow tasks delay completion after most tasks finish.

The best design reduces movement and coordination before adding machines.

Safety and liveness

Distributed algorithms are easier to reason about when you separate two goals.

Safety means a forbidden outcome never occurs. Two clients must not both acquire one exclusive lease, for example.

Liveness means useful progress eventually occurs. A queued task must eventually run when the required resources remain available.

Timeouts and leader elections can improve liveness. They must not violate safety when messages arrive late. State each property and the assumptions needed to preserve it.

When distributed computing fits

Use distribution when one machine cannot meet a justified requirement for capacity, latency, locality, or fault tolerance. Common uses include batch data processing, search indexing, scientific simulation, replicated storage, stream processing, and globally placed services.

Keep work on one machine when it already meets the requirement. A local design avoids network ambiguity, distributed coordination, replica repair, and cross-node observability.

A practical learning path follows this order:

Trace messages, state, and failure outcomes in a two-node request.
Partition a batch computation and measure skew, transfer, and stragglers.
Model retries and make state-changing operations idempotent.
Compare consistency guarantees during delay and partition.
Study logical clocks and causal order.
Implement a small replicated state machine in a controlled lab.
Test safety and liveness under injected delay, loss, restart, and partition.