Consensus

The Two Generals’ Problem The Two Generals’ Problem, also known as the Two Armies Problem, is a classic thought experiment that demonstrates the impossibility of achieving perfect consensus over an unreliable communication channel. It was first formulated by E. A. Akkoyunlu, K. Ekanadham, and R. V. Huber in 1975. The Scenario Two armies need to coordinate an attack: General A and General B surround an enemy They must attack simultaneously to win If only one attacks → defeat They communicate via messengers through enemy territory Messages can be lost or intercepted Question: Can they guarantee coordinated attack? The Impossible Dilemma %%{init: {'theme':'dark', 'themeVariables': {'primaryTextColor':'#e5e7eb','secondaryTextColor':'#e5e7eb','tertiaryTextColor':'#e5e7eb','textColor':'#e5e7eb','nodeTextColor':'#e5e7eb','edgeLabelText':'#e5e7eb','clusterTextColor':'#e5e7eb','actorTextColor':'#e5e7eb'}}}%% sequenceDiagram participant GA as General A participant Enemy as Enemy Territory participant GB as General B Note over GA: Wants to attackat dawn GA->>Enemy: "Attack at dawn" Enemy->>GB: Message delivered Note over GB: Received message,but A doesn't know! GB->>Enemy: "Acknowledged" Enemy->>GA: ACK delivered? Note over GA: Received ACK,but B doesn't know! GA->>Enemy: "ACK of ACK" Enemy->>GB: Delivered? Note over GA,GB: This never ends! The Core Problem The infinite regress: ...

The Bully Election Algorithm The Bully Algorithm, proposed by Hector Garcia-Molina in 1982, is a classic leader election algorithm for distributed systems. It’s called “bully” because the highest-numbered process always wins and “bullies” the others into accepting it as leader. The Scenario A distributed system needs a coordinator: N nodes in a network Each node has a unique ID (priority) One node must be elected as leader When the leader fails, a new leader must be elected Rule: The node with the highest ID wins The protocol: ...

The Byzantine Generals Problem The Byzantine Generals Problem, proposed by Leslie Lamport, Robert Shostak, and Marshall Pease in 1982, is one of the most important problems in distributed systems. It addresses the challenge of achieving consensus when some participants may be faulty or malicious. The Scenario Byzantine army divisions surround a city: N generals command their divisions They must coordinate: attack or retreat They communicate via messengers Some generals are traitors who send conflicting messages Goal: All loyal generals must agree on the same plan The challenge: ...

Introduction Building robust distributed systems requires understanding fundamental patterns that solve common challenges like consensus, fault tolerance, request distribution, and asynchronous communication. This comprehensive guide uses visual diagrams to illustrate how these patterns work, making complex distributed systems concepts easier to understand and implement. We’ll explore: Raft Consensus Algorithm: How distributed systems agree on shared state Circuit Breaker Pattern: Preventing cascading failures in microservices Load Balancing Algorithms: Distributing traffic efficiently across servers Message Queue Patterns: Asynchronous communication strategies Part 1: Raft Consensus Algorithm The Raft consensus algorithm ensures that a cluster of servers maintains a consistent, replicated log even in the face of failures. It’s designed to be more understandable than Paxos while providing the same guarantees. ...