Distributed-Systems

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: ...

The Gossiping Problem The Gossiping Problem is a classic problem in distributed systems and graph theory. N people each know a unique secret, and they share information through phone calls. On each call, both parties share all secrets they know. The goal: find the minimum number of calls needed for everyone to know all secrets. The Scenario N people, N secrets: Person i knows secret Si initially When persons i and j call each other, they share ALL secrets they know Goal: Everyone knows all N secrets Question: What’s the minimum number of calls? The Mathematical Result For n ≥ 4 people: ...

The Token Ring Problem The Token Ring is a classic distributed mutual exclusion algorithm where nodes are arranged in a logical ring, and a single token circulates. Only the node holding the token can access the shared resource. It’s simple, fair, and starvation-free. The Scenario Nodes arranged in a ring: N nodes form a logical ring A single token passes around the ring Only token holder can enter critical section After using resource, pass token to next node Properties: Fair (FIFO order), no starvation, deadlock-free The challenge: ...

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 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: ...

← Ticket Seller | Series Overview | Monte Carlo Pi → The Problem: Counting What You Can’t See Count concurrent users. On login: increment. On logout: decrement. Simple, right? Now add reality: The counter is distributed across multiple servers A user’s session times out on one server but they’re active on another The increment message arrives after the decrement message Network partitions split your cluster Servers crash mid-operation Suddenly, this “simple” counter becomes a distributed systems nightmare. Welcome to distributed counting, where even addition is hard. ...