Consensus (computer science) Study Guide

📖 Core Concepts Consensus – A set of processes must eventually decide on one common value. Correct process – A non‑faulty participant that follows the protocol. Fault models Crash: process stops permanently. Byzantine: arbitrary (malicious) behavior, can send conflicting messages. Validity types Weak: output equals the input of some correct process. Strong: if all correct inputs are identical, the output must be that value. t‑resilience – A protocol tolerates up to t faulty processes; it is t‑resilient if it works despite any ≤ t failures. System models Synchronous: execution proceeds in lock‑step rounds; messages sent in a round are received before the next round starts. Asynchronous: no bound on message delays or round lengths. Authentication models Oral: receiver knows the immediate sender. Written: messages carry a digital signature, revealing the original creator. --- 📌 Must Remember FLP Impossibility – In a fully asynchronous system with even one possible crash, no deterministic algorithm can guarantee consensus. Byzantine bound (anonymous synchronous): consensus possible iff $$ n > 3t $$ Oral‑messages impossibility: no solution when $$ n \le 3f $$ where f = number of Byzantine processes. Written‑messages capability: tolerates up to f Byzantine failures as long as $$ n > f $$ Phase King complexity – Runs for f + 1 phases, 2 rounds per phase ⇒ total of 2(f + 1) rounds. Paxos / Raft – Synchronous, leader‑based, tolerate crash failures (not Byzantine). Consensus number – Minimum object consensus number needed to solve consensus for n processes: Read/write register: 1 Test‑and‑set, fetch‑and‑add, stack, queue: 2 Compare‑and‑swap (CAS): ∞ 51 % attack – In proof‑of‑work blockchains, an adversary controlling > ½ of total hash power can dictate the ledger. --- 🔄 Key Processes Phase King (Binary Byzantine Consensus) Initialize each process with a preferred value (0/1). For phase = 1 … f + 1 Round 1: Every process broadcasts its current preferred value. Round 2: The king (process whose id = current phase) collects all received values, computes the majority, and broadcasts that majority. Update: If a process saw a majority count > \( \frac{n}{2} + f \), it keeps its own value; otherwise it adopts the king’s broadcast value. After the final phase, output the current preferred value (all are equal). Paxos (high‑level) Prepare – Leader proposes a proposal number to a majority of acceptors. Promise – Acceptors respond with the highest-numbered proposal they have already accepted (if any). Accept – Leader sends the value (either its own or the highest received) with the proposal number. Learn – Learners gather accept messages from a majority and decide. Randomized Consensus (asynchronous) Processes repeatedly exchange random bits or values; with probability 1 the protocol eventually satisfies agreement and termination despite crash failures. --- 🔍 Key Comparisons Oral‑messages vs. Written‑messages Oral: only immediate sender known → Byzantine tolerance limited to \( n > 3f \). Written: signatures reveal original creator → tolerance improves to \( n > f \). Crash‑only vs. Byzantine Crash: simpler algorithms (Paxos, Raft) suffice. Byzantine: need stronger assumptions (authentication, extra rounds, Phase King). Synchronous vs. Asynchronous Synchronous: bounded rounds, deterministic consensus possible (e.g., Phase King). Asynchronous: FLP prevents deterministic guarantee; randomness or failure detectors are required. --- ⚠️ Common Misunderstandings “Consensus = any agreement” – Consensus also requires validity (output must be an input of a correct process) and termination for all correct processes. “Byzantine tolerance = crash tolerance + extra steps” – Byzantine failures can corrupt messages arbitrarily; authentication and stricter bounds (n > 3t) are essential, not just extra rounds. “Proof‑of‑Work is always secure” – A 51 % attack can rewrite history; security hinges on the honest majority of hash power. “Read/write registers can solve two‑process consensus” – Their consensus number is 1; you need a stronger primitive (e.g., test‑and‑set) for even two processes. --- 🧠 Mental Models / Intuition “Round‑trip majority” – In synchronous Byzantine algorithms, think of each round as “collect everybody’s opinion → take the majority → let a designated leader (king) break ties.” “Thresholds as safety nets” – The inequalities \( n > 3t \) and \( n > f \) are safety nets: they guarantee that the correct majority can outvote the worst‑case collusion of faulty processes. “FLP as a timing paradox” – Asynchrony hides the ability to detect whether a process has crashed; without timing guarantees, a deterministic protocol cannot differentiate a slow message from a crash. --- 🚩 Exceptions & Edge Cases Partial synchrony – Systems that are eventually synchronous can use protocols that wait for a timeout that eventually becomes a true bound; deterministic consensus becomes possible after the “unknown” stabilization time. Authenticated Byzantine model with fewer than n > 3t – If digital signatures are unforgeable, some protocols can tolerate up to \( n > t \) (e.g., written‑messages model). Randomized protocols – Guarantee probability 1 liveness, but not a strict deterministic bound on the number of rounds. --- 📍 When to Use Which Crash‑only, known participants, low latency → Paxos or Raft (leader‑based, simple). Byzantine adversary, synchronous network, authenticated messages → Phase King (binary) or any algorithm assuming \( n > 3t \). Permissionless, open participation → Proof‑of‑Work (high energy) or Proof‑of‑Stake (lower energy, requires staking). Shared‑memory multiprocessor → Use objects with consensus number ≥ n (e.g., CAS) for wait‑free consensus; otherwise augment with higher‑level protocols. Asynchronous environment with possible crashes → Randomized consensus or add failure detectors (e.g., ♦ Ω). --- 👀 Patterns to Recognize “Majority + king” pattern in Byzantine rounds → indicates Phase King or similar algorithms. “Prepare/Promise/Accept” message flow → Paxos family. “Signed broadcast” → written‑messages model, implying stronger Byzantine tolerance. “Two‑phase commit” in permissioned blockchains (e.g., Tendermint) → looks like synchronous Byzantine consensus with \( n > 3t \). “Increasing difficulty target” in PoW blocks → indicates Bitcoin‑style proof‑of‑work. --- 🗂️ Exam Traps Confusing validity levels – A question may ask for “strong validity”; answer that all inputs equal ⇒ output must be that same value (not just any correct input). Misapplying FLP – Remember FLP applies only to asynchronous deterministic algorithms with crash failures; randomized or partially synchronous protocols are not covered. Wrong Byzantine bound – Some students pick \( n > 2t \); the correct bound for anonymous synchronous Byzantine consensus is \( n > 3t \). Assuming Paxos tolerates Byzantine nodes – Paxos only handles crash failures; any answer claiming Byzantine safety is wrong. Mixing consensus numbers – Read/write registers cannot solve two‑process consensus; selecting them for n > 1 will be marked incorrect. 51 % attack wording – A distractor may say “requires > 50 % of nodes” – the correct metric is computational hash power, not node count.