# Distributed Systems Bridges Blockchain papers and modules reuse distributed-systems ideas constantly — often without stopping to unpack them. This note collects the bridges that come up most often: what each result or pattern means, why blockchains care, and what you already know that rhymes with it. Referenced from [[01 Replicated State Machines]], [[04 Consensus]], [[05 Execution and Smart Contracts]], and [[09 Scaling - Rollups and Data Availability]]. ## FLP impossibility In 1985, Fischer–Lynch–Paterson proved that no **deterministic** consensus protocol can guarantee both safety and liveness if messages may be delayed arbitrarily and even one process can crash. Why blockchains care: pure agreement under worst-case asynchrony is impossible. So open chains sidestep the theorem — probabilistic finality (Bitcoin), timeouts plus slashing (Ethereum PoS), or smaller validator sets with explicit rounds (BFT appchains). They trade perfect guarantees for economics and engineering pragmatism. Bridge: Raft and Paxos assume eventually reliable delivery and crashed (not lying) replicas. FLP says you cannot get deterministic consensus if delivery is unbounded — blockchains accept that and design around it. ## Byzantine fault tolerance and `n >= 3f + 1` A **Byzantine** replica may crash *or* lie — send conflicting messages, collude, censor. In Byzantine agreement, `f` is how many nodes may behave that way. You need more than triple that many honest nodes to tell truth from coordinated fiction: three liars can outvote two honest nodes, but four honest nodes can outvote three liars. Hence the bound: ```text n >= 3f + 1 ``` Why blockchains care: open participation means you cannot assume honesty. BFT protocols (Tendermint, HotStuff, Casper-FFG's finality layer) encode this math. Nakamoto-style chains instead make lying expensive through work or stake. Bridge: Raft tolerates `f` crashes with `2f + 1` nodes. Byzantine tolerance needs the extra replicas because votes from liars cannot be trusted without a larger honest quorum. ## Detect-and-recover vs prevent-by-construction Two classic ways to handle suspected bad state: | **Pattern** | **Idea** | **Blockchain example** | |---|---|---| | Detect-and-recover | Assume valid unless someone proves otherwise | Optimistic rollups, fraud proofs | | Prevent-by-construction | Submit only what can be proved valid upfront | ZK rollups, validity proofs | Why blockchains care: optimistic designs are cheaper and simpler but need watchers and delay (challenge windows). ZK designs are heavier to build but remove the "hope someone is watching" assumption. Bridge: like running production with audit logs and rollback versus formal verification before deploy — different cost and trust tradeoffs. ## Fork choice vs finality Two questions that sound alike and are not: - **Fork choice**: given competing valid heads, which one do I build on *right now*? - **Finality**: when can I treat a block as irreversible? Why blockchains care: Nakamoto consensus always has a fork-choice rule (heaviest chain) but only probabilistic finality. BFT layers add explicit finality checkpoints. Products must know which question they're answering when they show "confirmed." Bridge: fork choice is "current best view"; finality is "safe to ship the goods." In a database analogy: reading your replica's latest write vs waiting for cross-region commit acknowledgment. ## Deterministic execution constraint Every node must run the same program on the same inputs and get **bit-identical** results. Therefore anything that varies between machines — wall-clock time, randomness, network I/O, floating point — is forbidden inside the execution layer. Why blockchains care: this is why the EVM has no `fetch()`, no real `random()`, no HTTP. External facts enter only via transactions something else signed (oracles, oracle updates). Bridge: like requiring all replicas in a state machine to apply the same pure function — except here "replicas" are adversarial and anyone can submit inputs.