Experiments

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 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 Writer Starvation Problem In the readers preference solution, we saw how continuous readers can starve writers. The writers preference solution fixes this by giving writers priority. Key idea: When a writer is waiting, no new readers are allowed to start, even if other readers are currently reading. Real-World Need for Writer Priority Some systems need writer priority: Databases with critical updates (billing, inventory) Real-time systems (sensor updates must not be delayed) Logging systems (log writes can’t be delayed) Configuration systems (updates must propagate quickly) Leader election (state changes need priority) The Solution Go’s sync.RWMutex uses readers preference, so we need to implement writer preference manually using additional synchronization: ...

The Santa Claus Problem The Santa Claus problem is a delightful synchronization challenge by J.A. Trono (1994). It demonstrates group coordination, prioritization, and conditional wake-up patterns. The Scenario Characters: Santa Claus (1) Reindeer (9) Elves (10) The rules: Santa sleeps in his shop at the North Pole Santa can be awakened by either: All 9 reindeer return from vacation → prepare sleigh, deliver toys Any 3 elves have problems → get help from Santa Reindeer have priority over elves Santa helps 3 elves at a time, then goes back to sleep After delivering toys, Santa unhitches reindeer and goes back to sleep The Challenge Coordination: Wake Santa only when conditions met Grouping: Exactly 9 reindeer OR 3 elves Priority: Reindeer interrupt elf help Fairness: All elves should eventually get help Real-World Applications This pattern models many production scenarios: ...

The Sleeping Barber Problem The Sleeping Barber is a classic synchronization problem proposed by Edsger Dijkstra in 1965. It elegantly demonstrates resource management, waiting, and signaling in concurrent systems. The Scenario A barbershop has: 1 barber 1 barber chair N waiting room chairs The rules: If no customers, the barber sleeps When a customer arrives: If barber is sleeping → wake him up If barber is busy → sit in waiting room (if space available) If waiting room is full → leave When barber finishes a customer → check waiting room Real-World Applications This pattern appears in many systems: ...

The Bathroom Problem The Bathroom Problem is a classic coordination puzzle that illustrates fairness, starvation prevention, and group coordination in concurrent systems. First proposed by Jon Kleinberg, it demonstrates how to manage resource access with group-based constraints. The Scenario A unisex bathroom has: Capacity for N people Only people of one gender at a time Random arrivals from multiple genders The rules: Multiple people of the same gender can enter simultaneously (up to capacity) People of different genders cannot be in the bathroom at the same time When empty, either gender can enter Must prevent starvation - no gender should wait forever The Challenge: Fairness vs Throughput The trap is starvation. Consider: ...

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