Distributed Systems — History, Time, Failure, and Replication

01What makes a system distributed

• A distributed system consists of separated processes that exchange messages yet present one service or computation to a user. Leslie Lamport’s 1978 paper puts separated processes and non-negligible communication delay at the centre of the definition. The decisive fact is not machine count; it is that one process cannot instantly know another process’s state.
• Parallel work inside one large machine overlaps with distributed computing, but the terms are not interchangeable. Across a network, messages can be delayed, lost, reordered, or delivered only to one side. A component can fail while the rest continues, and different machines can observe the same events in different orders.

02Separate the neighbouring terms

• Distributed, decentralised, peer-to-peer, grid, cloud, and blockchain describe related but different properties. Distribution is about where computation and state reside. Decentralisation is about where control and authority reside. A service can be geographically distributed across many data centres while remaining controlled by one company.
• Peer-to-peer describes a network in which participants need not be permanently divided into clients and servers. Grid computing pools resources across sites or organisations; cloud computing makes provisioned resources available on demand. A blockchain is a family of replicated, tamper-evident shared-ledger designs. It occupies one region of the much larger distributed-systems field.

03From ARPANET to an open-participation ledger

• ARPANET connected geographically separated computers through packet networking in 1969. Calling it simply “the first distributed system” would overstate the claim. A network provides communication; the research that followed dealt with coordinating state, replication, failure, and computation on top of that communication layer.
• From the late 1970s through the 1990s, logical clocks, Byzantine faults, impossibility conditions, Paxos, and state-machine replication shaped the theory. In the 2000s, MapReduce distributed bulk data processing across commodity clusters, while Dynamo documented a data store designed around high availability. These systems made distribution practical for goals and trust models unlike Bitcoin’s.
• The 2008 Bitcoin paper combined peer-to-peer communication, hash-linked history, proof of work, and incentives to address double spending in electronic cash. Its novelty was not the invention of distributed computing, but the integration of existing components for maintaining transaction history among open participants.

04There is no universal “now”

• In a distributed system, it is not always meaningful to say which of two events happened first. If an event at process A causes a message that is received before an event at process B, there is a causal order. If the events have no communication path between them, they are concurrent; a tiny wall-clock difference does not create a meaningful causal relationship.
• Lamport’s happened-before relation and logical clocks assign event numbers consistent with causality. The implication works in one direction: if `a → b`, then `C(a) < C(b)`. A smaller clock value alone does not prove that one event caused another. Vector clocks can retain more information about concurrency, at additional metadata cost.
• This matters for double booking, balances, file updates, and block arrival. In Bitcoin, two miners can find valid tips at nearly the same time and different nodes can temporarily see different heads. The protocol converges on ordering through chain-selection rules, not by assuming a perfect physical clock.

05Partial failure — broken, or merely slow?

• The distinctive difficulty of distribution is partial failure. When a node does not answer, an observer cannot perfectly tell whether it crashed, the network partitioned, the reply was lost, or the node is simply slow. A timeout is a useful suspicion mechanism, not proof of death.

• A Byzantine fault does not require a malicious person. Software bugs, bad memory, corrupted traffic, and a compromised node can all produce arbitrary behaviour outside the specification. The selected fault model determines both the replication factor and the communication cost a protocol needs.

06Keep safety separate from liveness

• Distributed guarantees are often split into safety and liveness. Safety means that something bad never happens: two replicas do not commit different values at the same log position, or an invalid transaction is never accepted. Liveness means that something good eventually happens: a request completes, or the system eventually decides.
• A design may stop during severe network trouble to preserve safety. Another may continue returning responses while permitting temporary inconsistency. “Never stops” and “stays correct” are not one metric; the system specification must state which property it preserves under which fault.
• Bitcoin has the same separation. Full nodes rejecting invalid blocks is a safety property. Continued production of valid blocks is a liveness property that depends on assumptions about network propagation and honest hash power.

07Replicated state machines — same order, same state

• Replication is the basic tool for reliability, but copying data to several machines is insufficient. If concurrent updates are applied in different orders, the replicas diverge. State-machine replication starts each deterministic replica from the same state and applies commands in the same order, making the replicas act as one service.
• The central job of a consensus algorithm is to decide which command occupies each position in the log. Paxos and Raft construct replicated logs among known servers under crash faults. PBFT extends the model to replicas that may behave arbitrarily. Before comparing algorithms, identify the membership, fault bound, and network assumptions.
• Bitcoin full nodes also recompute UTXO state from common validation rules, but block proposers are open-participation miners and history selection uses cumulative proof of work. This is a different membership model from a registered enterprise replica set.

08What FLP actually makes impossible

• The 1985 Fischer–Lynch–Paterson result, or FLP, shows that in a completely asynchronous message system, no deterministic consensus protocol can guarantee termination in every admissible execution if even one process may crash. It does not say that practical distributed consensus is impossible.
• The theorem combines strong conditions: unbounded message and process delay, no perfect distinction between delay and failure, determinism, and termination across every execution. Practical protocols add an eventual timing assumption, randomisation, failure detectors, or operational timeouts to make progress.
• Dwork, Lynch, and Stockmeyer formalised partial synchrony, where useful timing bounds exist but may become known only eventually. The lasting lesson is to read what a protocol assumes about time before reading its brand name.

09CAP is more precise than “pick two”

• CAP says that while a network partition is occurring, a service cannot simultaneously guarantee atomic consistency — behaviour equivalent to one up-to-date copy — and availability — every request to a non-failing node receives a response. Partition tolerance is not a decorative feature to drop when the environment can partition.
• The familiar triangle saying “choose two of consistency, availability, and partition tolerance” is memorable but can imply a permanent design-time choice even during healthy operation. Real systems make finer decisions by operation, data item, latency budget, and the part of the network affected.
• CAP’s C is not the vague statement that data is eventually similar, and A is not ordinary annual uptime. The paper’s formal properties and a product’s service-level objectives must be kept distinct.

10Clusters, grids, and clouds changed the scale

• The 2004 MapReduce paper hid input partitioning, task placement, failed-task re-execution, and machine communication behind a programming model for large commodity clusters. Treating failure as routine and recovering through re-execution was as important as parallel speed.
• Amazon’s 2007 Dynamo paper documented a highly available key-value store for always-on services such as shopping carts. Consistent hashing, vector clocks, sloppy quorums, and read repair expressed deliberate trade-offs rather than one universally correct consistency model.
• Grid and volunteer computing took another path, pooling unused resources scattered across organisations and homes. They distribute separable work and validate returned results instead of building a common transaction ledger. The Volunteer Computing article follows that lineage in depth.

11What Bitcoin inherited — and what it changed

• Bitcoin inherited peer-to-peer messaging, replicated state, cryptographic hashing, digital signatures, and the distributed problem of ordering events. Unlike a registered server cluster, however, it had to admit anyone and withstand one actor creating many pseudonymous identities.
• Proof of work is not one-node-one-vote. It converts verifiable computational resources into weight for proposing history. Each node follows the valid chain requiring the most cumulative work. Under model assumptions such as attacker hash power remaining below the honest share, deeper confirmation lowers reversal probability; it does not create immediate mathematical finality.
• Miners propose ordering, but work cannot make an invalid block valid. Each full node independently checks signatures, double spending, issuance, and script rules. Sybil resistance through scarce resources and validity through rule verification are separate jobs.

12Six questions for reading any distributed design

• Before trusting a product label or the word “decentralised,” ask six structural questions.

• BOINC, Raft, and Bitcoin are all distributed, but they solve different problems. BOINC sends independent jobs to untrusted home computers, applies a project-specific validator, and cross-checks replicated answers when needed. Raft orders a log among known servers. Bitcoin maintains value-transfer history among open participants. Connecting them without erasing those differences is the shortest route to understanding distributed computing.