Consensus Protocol

A consensus algorithm designed for understandability, equivalent to Paxos in fault-tolerance. It manages a replicated log and is widely used for leader election and cluster membership in distributed systems.

• Core Mechanism: Elects a single leader who manages log replication to follower nodes.
• Fault Model: Provides Crash Fault Tolerance (CFT), handling nodes that fail by stopping.
• Real-World Use: The default consensus engine in etcd and Consul, which are critical for service discovery and configuration storage in Kubernetes and microservices architectures.

The seminal family of protocols for solving consensus in a network of unreliable processors. It is known for its theoretical elegance and forms the basis for many practical systems.

• Core Mechanism: Uses a series of proposals and promises to achieve agreement among a majority of nodes (a quorum).
• Fault Model: Tolerates Crash Faults.
• Real-World Use: Variants like Multi-Paxos are used in Google's Chubby lock service and Apache ZooKeeper for coordination.

A replication algorithm that provides Byzantine Fault Tolerance (BFT), meaning it can tolerate arbitrary (malicious or faulty) behavior from some nodes.

• Core Mechanism: Uses a three-phase protocol (pre-prepare, prepare, commit) involving multiple rounds of voting among replicas.
• Fault Model: Tolerates Byzantine faults, where nodes may act maliciously.
• Real-World Use: Inspired many early permissioned blockchain platforms like Hyperledger Fabric. It is suitable for consortium settings where participant identity is known but not fully trusted.

The consensus mechanism underlying Bitcoin. It achieves decentralized, permissionless consensus without requiring nodes to know each other's identities.

• Core Mechanism: Nodes (miners) compete to solve a computationally difficult cryptographic puzzle. The first to solve it proposes the next block, and the longest valid chain is accepted.
• Fault Model: Provides Byzantine Fault Tolerance in a Sybil-resistant, adversarial environment.
• Real-World Use: Bitcoin, Ethereum (pre-Merge), and other cryptocurrencies. It prioritizes decentralization and censorship resistance over transaction speed and energy efficiency.

A family of consensus mechanisms where validators are chosen to create new blocks based on the amount of cryptocurrency they "stake" as collateral.

• Core Mechanism: Replaces energy-intensive mining with economic staking. Validators are randomly selected, and malicious acts lead to slashing (loss of stake).
• Fault Model: Provides Byzantine Fault Tolerance with different economic and security assumptions than Proof-of-Work.
• Real-World Use: Ethereum 2.0 (The Merge), Cardano, Solana. Variants include Delegated PoS (DPoS) used by EOS, where stakeholders vote for delegates.

While not a single-value consensus protocol, gossip-based dissemination combined with Conflict-Free Replicated Data Types (CRDTs) provides a powerful model for eventual consistency without central coordination.

• Core Mechanism: Nodes periodically exchange state with random peers (gossip). CRDTs are mathematical data structures that guarantee convergence to the same state across all replicas, even with concurrent updates.
• Fault Model: Highly resilient to network partitions and node churn.
• Real-World Use: Amazon's DynamoDB, Redis Enterprise for active-active replication, and collaborative editing applications like Automerge.

The characteristic of a distributed system that can reach agreement correctly even when some components fail arbitrarily—meaning they can behave maliciously or send conflicting information, as defined by the Byzantine Generals Problem. This is a stronger guarantee than Crash Fault Tolerance (CFT). BFT protocols, like Practical Byzantine Fault Tolerance (PBFT), are critical for blockchain networks and high-security financial systems where nodes cannot be fully trusted. They require a higher number of replicas (typically 3f+1 to tolerate f faulty nodes) to achieve consensus despite adversarial behavior.

A fundamental distributed algorithm by which nodes in a cluster autonomously select a single node to act as the coordinator or leader. This process ensures there is a single decision-maker to manage tasks like ordering requests in a consensus protocol (e.g., Raft). If the leader fails, the algorithm triggers a new election. Key properties include:

• Safety: At most one leader is elected per term.
• Liveness: Eventually, a leader is elected if a majority of nodes are alive. It is a prerequisite for many state machine replication and consensus systems to avoid split-brain scenarios.

A core method for implementing a fault-tolerant service by replicating a deterministic application or state machine across multiple servers. The core principle is that if all replicas start in the same state and process the same sequence of commands in the same order, they will produce identical outputs and state transitions. Consensus protocols like Raft and Paxos are used to agree on this exact command sequence. This pattern is the backbone of highly available systems like distributed databases (e.g., etcd, Consul) and forms the theoretical foundation for implementing consistent, replicated services.

Distributed systems that require a majority or a specific subset of nodes (a quorum) to agree before an operation like a write or a leader election is considered successful. This is a fundamental mechanism for ensuring strong consistency in the face of network partitions and node failures. For a cluster of N nodes, a typical read or write quorum is (N/2 + 1).

• Examples: The Raft consensus algorithm uses quorums for leader election and log commitment.
• Purpose: Prevents split-brain decisions by ensuring any two quorums must overlap by at least one node, guaranteeing that only one decision can achieve a majority.

A widely adopted consensus algorithm designed for understandability while providing equivalent fault-tolerance to Paxos. It explicitly decomposes consensus into three relatively independent sub-problems: Leader Election, Log Replication, and Safety. Raft ensures that all nodes agree on an ordered log of commands, which is then applied to a state machine. It guarantees:

• Election Safety: At most one leader can be elected in a given term.
• Leader Append-Only: A leader never overwrites or deletes entries in its log.
• Log Matching: If two logs contain an entry with the same index and term, they are identical. It is the consensus engine for systems like etcd and K3s.

A critical property of a system, function, or state machine where, given the same initial state and an identical sequence of inputs, it will always produce the exact same outputs and state transitions. This property is non-negotiable for state machine replication because all replicas must converge to the same final state. If a replicated service contains non-deterministic operations (e.g., random number generation, local timestamps), the replicas will diverge, breaking consistency. Ensuring deterministic execution often requires careful design, such as using agreed-upon external inputs (like leader-provided timestamps) for all replicas.