Distributed Algorithms in System Architecture

Distributed Algorithms: Reaching Agreement at Scale In a distributed environment, you cannot rely on a single source of truth. If one node says "X" and another says "Y," the system must have an algorithmic way to resolve the conflict and maintain the global state. These algorithms provide the mathematical foundation for consistency and fault tolerance. 1. Raft: Consensus via Leader Election Raft was designed to make distributed consensus understandable. It organizes the cluster into three states: Follower, Candidate, and Leader . How it works: Leader Election: If Followers don't hear from a Leader (via heartbeats), they become Candidates and start an election. The node with the most votes becomes the new Leader. Log Replication: The Leader receives all client commands, appends them to its log, and forces all Followers to replicate these entries. Why use it? It is the standard for modern systems (like Etcd and HashiCorp Consul ) because it explicitly handles state transitions in a way that is verifiable and robust. 2. Paxos: The Foundation of Consensus Paxos is the "Grandfather" of consensus algorithms. It is notoriously complex but mathematically rigorous. The Logic: It works in rounds involving Proposers, Acceptors, and Learners . A Proposer attempts to reach consensus by sending a proposal; Acceptors vote to "accept" the value. The Guarantee: Once a value is "chosen" by a majority of Acceptors, it is immutable. Even if nodes fail and recover, they can query the network to learn the "chosen" value. Production Context: While pure Paxos is rarely implemented from scratch, it serves as the theoretical base for many proprietary systems (like Google’s Chubby lock service). 3. Gossip Protocol: Epidemic Communication The Gossip Protocol is a peer-to-peer communication algorithm where nodes periodically exchange information with a random subset of other nodes. How it works: Like a rumor in a crowd, the information spreads exponentially. Node A tells Node B; then A and B tell others, and within a very short time, the entire cluster knows the information. Resilience: It is incredibly robust. Because there is no "Leader," there is no single point of failure. If 30% of your nodes go down, the information still propagates through the remaining healthy network. Production Use: Used by Cassandra for cluster membership (knowing which nodes are up/down) and by service discovery tools to sync cluster state across thousands of nodes. 4. Quorum: The Math of Majority A Quorum is the minimum number of nodes that must agree on an operation to ensure consistency. The Formula: If you have $N$ total nodes, a read/write quorum $R$ and $W$ must satisfy: $W > N/2$ (Ensures only one writer can succeed at a time). $R + W > N$ (Ensures the read "sees" the latest write). Why it matters: It allows you to tune your system's performance. You can perform "fast" writes by requiring only a small quorum, or "safe" writes by requiring a majority. Trade-off: This is the core of Eventual vs. Strong Consistency . If you set $W=1$ , you get fast writes, but your reads might return stale data unless your read quorum ( $R$ ) is large enough to find the newest value. Distributed Algorithm Reference Matrix Algorithm Primary Purpose Key Characteristic Raft Strong Consistency Understandable Leader-based model. Paxos Strong Consistency Mathematically rigorous, complex. Gossip Health/State propagation Peer-to-peer, "epidemic" spread. Quorum Data Integrity Majority-based validation for read/write.