Fairness

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 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 Ultimatum Game: Are Humans Really Rational? Imagine this: I give you $100 and ask you to propose how to split it with a stranger. There’s one catch - if the stranger rejects your offer, neither of you gets anything. Game theory predicts you’ll offer $1 and keep $99. After all, $1 is better than $0, so the stranger should accept. In reality? Most people offer $40-50, and offers below $30 are frequently rejected. ...