Consensus Algorithm

The guarantees of a consensus algorithm depend on its assumptions about network timing.

• Synchronous: Assumes a known upper bound on message delays. Simplifies design but is unrealistic for wide-area networks like the internet.
• Asynchronous: Makes no timing assumptions. While ideal, the FLP result shows perfect consensus is impossible here.
• Partial Synchrony: The most practical model. Assumes the network is asynchronous but will become synchronous (messages delivered within a known bound) for unknown, finite periods. Most production algorithms (PBFT, Raft) are designed for this model, providing safety always and liveness once the network stabilizes.

This property defines the coordination structure of the protocol.

• Leader-Based (e.g., Raft, Paxos, PBFT): A single leader node coordinates the consensus process, proposing values and driving replication. This simplifies the protocol and can be highly efficient. However, it creates a single point of contention and requires a leader election sub-protocol if the leader fails.
• Leaderless (e.g., Paxos variants, some blockchain protocols): Any node can propose a value. Agreement is reached through a more complex mesh of communication, such as multiple voting phases. This improves decentralization and robustness against targeted leader attacks but often increases communication complexity and latency.

This refers to the number of messages that must be exchanged among nodes to reach a single decision. It's a key determinant of scalability and latency.

• Raft: Requires a linear number of messages per decision (O(N)), as the leader communicates with all followers.
• PBFT: Has quadratic message complexity (O(N²)) for its view-change protocol, as each node must broadcast messages to all others to agree on a new leader after a suspected failure. This limits the practical size of a PBFT cluster to tens of nodes.
• Modern Innovations: Protocols like HotStuff and its variants reduce this to linear complexity for the view-change, enabling larger, more scalable BFT networks.

This defines the nature of the agreement reached.

• Finality (Deterministic): Once a value is agreed upon by correct nodes, it is immutable and cannot be reverted. Protocols like PBFT and Raft provide immediate finality. This is critical for enterprise systems requiring absolute state guarantees.
• Probabilistic Agreement (Nakamoto Consensus): Used in Proof-of-Work blockchains like Bitcoin. Agreement is not immediate but becomes exponentially more certain over time as blocks are extended. There is always a non-zero probability of a chain reorganization. This trades off immediate finality for the ability to scale to a permissionless, global network of anonymous participants.

Raft is a consensus algorithm designed for understandability, decomposing consensus into three sub-problems: leader election, log replication, and safety.

• Core Mechanism: A single elected leader manages all client requests, replicating a log of commands to follower agents. Consensus is achieved when a majority of agents have stored the log entry.
• Advantage over Paxos: Raft's state machine and strong leadership model make its correctness arguments and implementations significantly more straightforward.
• Widespread Adoption: Used in etcd, Consul, and many Kubernetes control plane components for reliable distributed state management.

Proof-of-Work (PoW) is a Sybil-resistant, Nakamoto consensus mechanism where agents (miners) compete to solve a computationally expensive cryptographic puzzle. The first to solve it proposes the next block, and the network accepts the longest valid chain.

• Security Model: Relies on economic incentives and the assumption that the majority of computational power (hash rate) is honest.
• Key Trade-off: Provides robust decentralization and permissionless participation at the cost of immense energy consumption and low transaction throughput.
• Primary Example: The consensus algorithm securing the Bitcoin blockchain.

Proof-of-Stake (PoS) is a consensus mechanism where the right to propose or validate the next block is determined by an agent's economic stake (ownership) in the network, often combined with a pseudo-random selection algorithm.

• Security Model: Security derives from financial skin-in-the-game; malicious behavior leads to the slashing (loss) of the staked assets.
• Advantages over PoW: Dramatically more energy-efficient and enables higher transaction throughput and faster finality.
• Primary Example: The consensus algorithm used by Ethereum 2.0 (Casper FFG), Cardano, and many other modern blockchains.

Two-Phase Commit (2PC) is a distributed atomic commitment protocol, not a general consensus algorithm, that ensures all agents in a transaction either commit or abort unanimously.

• Phases: 1) Prepare/Vote Phase: A coordinator asks all participants if they can commit. 2) Commit/Abort Phase: If all vote 'yes', the coordinator sends a global commit; otherwise, it sends abort.
• Failure Mode: It is a blocking protocol; if the coordinator fails after the prepare phase, participants may remain in an uncertain state indefinitely, requiring manual intervention.
• Use Case: Classic protocol for achieving ACID transactions across distributed databases, though largely superseded by more resilient patterns like Sagas in microservices.