Concurrency

The Classic Dining Philosophers Problem The Dining Philosophers problem is one of the most famous concurrency problems, introduced by Edsger Dijkstra in 1965. It beautifully illustrates the challenges of resource sharing and deadlock in concurrent systems. The Setup: Five philosophers sit around a circular table. Between each pair of philosophers is a single fork (5 forks total). Each philosopher needs two forks to eat - one from their left and one from their right. ...

The Elevator Problem The Elevator Problem is a classic scheduling and optimization challenge that models how multiple elevators coordinate to serve passengers efficiently. It demonstrates load balancing, scheduling algorithms, optimization trade-offs, and decentralized coordination. Unlike many concurrency problems, it focuses on real-time decision-making and multi-objective optimization. The Scenario A building has: N elevators moving between floors M floors Passengers arriving at random floors with random destinations Call buttons (up/down) on each floor Destination buttons inside each elevator The goals: ...

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 Fairness Problem We’ve seen two extremes: Readers preference: Writers can starve Writers preference: Readers can starve The fair solution ensures no starvation - everyone gets served in the order they arrive. The Solution: FIFO Ordering Key idea: Use a queue to serve requests in arrival order. This prevents both reader and writer starvation. Arrival Order: R1, R2, W1, R3, R4, W2 Execution: R1+R2 → W1 → R3+R4 → W2 (batch) (excl) (batch) (excl) Consecutive readers can still batch together, but writers don’t get skipped! ...

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 Readers-Writers Problem The Readers-Writers problem is fundamental in concurrent systems where data is shared between multiple threads: Readers: Can access data simultaneously (read-only, no conflicts) Writers: Need exclusive access (modifications can’t overlap) The challenge: Maximize concurrency while maintaining data integrity. Real-World Applications This pattern is everywhere: Databases: SELECT queries (readers) vs UPDATE/INSERT (writers) Caching: Cache reads vs cache updates Configuration: Reading config vs reloading config File systems: Multiple readers, exclusive writes Web servers: Read sessions vs update sessions Readers Preference Solution In this variant, readers get priority: ...

The Drinking Philosophers Problem The Drinking Philosophers Problem is a generalization of the classic Dining Philosophers Problem, proposed by K. M. Chandy and J. Misra in 1984. Unlike the dining version where philosophers share forks with immediate neighbors in a circle, drinking philosophers share bottles with arbitrary neighbors based on a conflict graph. This makes it much more realistic for modeling real-world resource allocation. The Scenario The drinking party has: ...

← Bank Account Drama | Series Overview | Login Counter → The Problem: Selling Tickets That Don’t Exist A concert has 1,000 tickets. Multiple goroutines handle sales concurrently. Each seller checks if tickets remain, and if yes, decrements the count and sells one. Sounds simple, right? Two sellers check simultaneously. Both see “1 ticket remaining.” Both sell. You’ve just sold ticket number -1. Congratulations, you’ve discovered the check-then-act race condition, one of the most common concurrency bugs in the wild. ...

← Monte Carlo Pi | Series Overview | Mandelbrot Set → The Problem: Finding Primes with Filters The Sieve of Eratosthenes is an ancient algorithm for finding prime numbers. The concurrent version creates a pipeline of filters: each prime spawns a goroutine that filters out its multiples. The Algorithm: Generate sequence: 2, 3, 4, 5, 6, 7, 8, 9, 10, … Take first number (2), it’s prime, filter all multiples of 2 Take next number (3), it’s prime, filter all multiples of 3 Take next number (5), it’s prime, filter all multiples of 5 Repeat until desired count The Beauty: Each prime creates its own filter. Numbers flow through a pipeline of increasingly selective filters. What passes through all filters must be prime. ...

← Login Counter | Series Overview | Sieve of Eratosthenes → The Problem: Computing Pi by Throwing Darts Imagine a square dartboard with a circle inscribed inside it. Throw random darts at the square. The ratio of darts landing inside the circle to total darts thrown approaches π/4. Why? Mathematics: Square side length: 2 (from -1 to 1) Square area: 4 Circle radius: 1 Circle area: π × 1² = π Ratio: π/4 Throw 1 million darts, multiply by 4, and you’ve estimated π. More darts = better estimate. This is Monte Carlo simulation: using randomness to solve deterministic problems. ...