[S1..S6] Fundamentals / Fault & Network Models / Classic Protocols / Modern BFT & Blockchain Consensus / Scaling & Performance / Verification & Operations [S1|I1] Agreement | All correct replicas eventually decide exactly the same value | Steps: Propose value -> Exchange votes -> Validate quorum -> Decide value | Divergent decisions break safety and client trust [S1|I2] Validity | Decided value must have been proposed by some participant | Steps: Receive proposal -> Check origin -> Reject invalid -> Accept valid | Prevents invented values appearing from faulty leaders [S1|I3] Termination | Every correct replica eventually decides a value and halts | Steps: Start round -> Await messages -> Timeout retry -> Decide finally | Liveness fails under indefinite delay or deadlock [S1|I4] Quorum Intersection | Any two majority quorums share at least one correct replica | Steps: Count votes -> Reach majority -> Intersect quorums -> Confirm overlap | Small quorums risk disjoint majorities deciding differently [S1|I5] State Machine Replication | Replicas execute identical commands in identical order deterministically | Steps: Receive command -> Order command -> Execute deterministically -> Return result | Nondeterminism causes replicas to diverge silently [S1|I6] Leader Election | Participants select one coordinator to propose values per round | Steps: Detect failure -> Increment term -> Request votes -> Announce leader | Split elections stall progress until terms advance [CP 1/6 | NEXT: S2|I1] [S2|I1] Crash Faults | Node halts permanently and sends no further messages | Steps: Node fails -> Peers timeout -> Suspect crash -> Reconfigure membership | Distinguishing crash from slowness is impossible asynchronously [S2|I2] Byzantine Faults | Faulty nodes behave arbitrarily, lying, colluding, or omitting messages | Steps: Receive claims -> Cross-check messages -> Compare signatures -> Isolate liars | Needs over two thirds honest replicas [S2|I3] Partial Synchrony | Network delays bounded, but bound unknown or holds eventually | Steps: Assume delays -> Measure timeouts -> Adapt timeout -> Reach synchrony | Safety holds always; liveness only after stabilization [S2|I4] Asynchrony and FLP | No timing assumptions; deterministic consensus impossible with one crash | Steps: Assume asynchrony -> Attempt consensus -> Encounter bivalence -> Add randomization | Randomization or failure detectors restore practical progress [S2|I5] Partition Tolerance | System keeps operating despite messages lost between network groups | Steps: Partition forms -> Groups diverge -> Heal partition -> Reconcile states | Partitions force choice between consistency and availability [S2|I6] Failure Detectors | Oracles suspect crashed processes, possibly inaccurately, enabling consensus progress | Steps: Monitor heartbeats -> Miss threshold -> Suspect process -> Revise suspicion | False suspicions can elect duplicate leaders temporarily [CP 2/6 | NEXT: S3|I1] [S3|I1] Paxos | Leader-driven consensus using ballots, promises, accepts, and learned values | Steps: Prepare ballot -> Promise phase -> Accept value -> Learn decision | Multi-Paxos needed for sustained replicated log throughput [S3|I2] Raft | Leader-based log replication with terms, elections, and heartbeat messages | Steps: Elect leader -> Append entries -> Replicate log -> Commit entries | Leader bottleneck limits write throughput at scale [S3|I3] Two-Phase Commit | Coordinator atomically commits or aborts transactions across participants | Steps: Prepare phase -> Collect votes -> Commit decision -> Acknowledge completion | Coordinator failure blocks participants holding locks indefinitely [S3|I4] Three-Phase Commit | Adds pre-commit phase reducing blocking compared with two-phase commit | Steps: Prepare phase -> Pre-commit phase -> Collect acknowledgments -> Commit transaction | Still blocks under network partitions despite extra phase [S3|I5] PBFT | Byzantine consensus using pre-prepare, prepare, commit among replicated nodes | Steps: Pre-prepare proposal -> Prepare phase -> Commit phase -> Execute request | Quadratic message cost limits replica count severely [S3|I6] View Change | Replaces faulty leader after timeouts, transferring state to successor | Steps: Detect timeout -> Broadcast view-change -> Collect proofs -> Install leader | Repeated view changes can prevent any progress [CP 3/6 | NEXT: S4|I1] [S4|I1] HotStuff | Leader-based BFT with linear communication and three chained phases | Steps: Propose block -> Vote phase -> Chain certificates -> Commit block | Leader failure still pauses pipeline until rotation [S4|I2] Tendermint | Byzantine consensus locking validators on blocks in rounds | Steps: Propose block -> Prevote round -> Precommit round -> Finalize block | One third offline validators halt finality completely [S4|I3] Proof of Work | Miners compete solving puzzles; longest chain wins consensus | Steps: Broadcast transactions -> Mine block -> Propagate block -> Accept longest chain | Energy cost high; finality only probabilistic ever [S4|I4] Proof of Stake | Validators chosen proportionally to staked assets propose blocks | Steps: Stake assets -> Select validator -> Propose block -> Attest block | Nothing-at-stake and long-range attacks need slashing [S4|I5] Nakamoto Consensus | Probabilistic consensus following heaviest chain of proof-of-work blocks | Steps: Mine blocks -> Broadcast chain -> Compare weight -> Adopt heaviest | Reorganizations can reverse recent transactions unexpectedly [S4|I6] DAG-Based BFT | Separates transaction dissemination from ordering using directed acyclic graph | Steps: Disseminate batches -> Build DAG -> Order vertices -> Execute transactions | Memory grows fast under high transaction throughput [CP 4/6 | NEXT: S5|I1] [S5|I1] Sharding | Partition state and validators into parallel independent consensus groups | Steps: Assign shard -> Process locally -> Coordinate cross-shard -> Merge results | Cross-shard transactions need costly atomic coordination protocols [S5|I2] Pipelining | Overlap consecutive consensus phases to increase block throughput continuously | Steps: Queue proposals -> Overlap phases -> Vote concurrently -> Commit sequentially | Pipeline stalls propagate backpressure to earlier stages [S5|I3] Batching | Group many transactions into one consensus decision unit | Steps: Collect transactions -> Form batch -> Propose batch -> Execute batch | Larger batches increase latency for individual transactions [S5|I4] Threshold Signatures | Aggregate many validator signatures into one compact verifiable proof | Steps: Share keys -> Sign individually -> Aggregate shares -> Verify once | Key generation ceremony must be trusted carefully [S5|I5] Checkpointing | Periodically snapshot state, discarding logs before snapshot point | Steps: Reach stable -> Snapshot state -> Verify hash -> Prune log | Snapshot corruption can destroy recovery ability entirely [S5|I6] Throughput-Latency Tradeoff | Tuning block size and interval balances throughput against confirmation delay | Steps: Measure load -> Adjust parameters -> Benchmark results -> Select operating point | Optimizing one metric usually degrades the other [CP 5/6 | NEXT: S6|I1] [S6|I1] Formal Verification | Mathematically prove protocol safety and liveness properties hold always | Steps: Model protocol -> Specify properties -> Check model -> Refine proof | Models may omit real implementation bugs entirely [S6|I2] Model Checking | Exhaustively explore finite state spaces searching for property violations | Steps: Build model -> Generate states -> Check invariants -> Report counterexample | State explosion limits size of checkable systems [S6|I3] Fault Injection | Deliberately introduce crashes, delays, partitions to test resilience | Steps: Plan fault -> Inject fault -> Observe behavior -> Restore system | Tests cover only anticipated failure combinations realistically [S6|I4] Monitoring | Track leader changes, latency, quorum health, and error rates | Steps: Collect metrics -> Set thresholds -> Trigger alerts -> Triage incidents | Alert fatigue hides genuine incidents among noise [S6|I5] Reconfiguration | Change membership or protocol version without stopping consensus service | Steps: Propose change -> Approve jointly -> Activate epoch -> Retire old members | Mixed-version quorums can stall or fork state [S6|I6] Disaster Recovery | Restore service from snapshots and logs after catastrophic failure | Steps: Assess damage -> Restore snapshot -> Replay log -> Resume service | Stale backups lose recently committed transactions permanently [CP 6/6 | COMPLETE]