Deadlock and Starvation

• Deadlock: a cycle of threads, each holding a resource and waiting for one another holds. Nobody can move, ever.
• Starvation: the system keeps moving, but one thread is perpetually overtaken and never gets its turn.
• Fairness is the guarantee that rules starvation out: everyone eventually gets served.

Both are liveness failures (“something good eventually happens” is violated). Race conditions, by contrast, are safety failures (“something bad happens”).

The Coffman conditions

Deadlock needs all four:

1. mutual exclusion
2. hold-and-wait
3. no pre-emption
4. circular wait

Break any one and deadlock is impossible. The cheapest to break is usually circular wait: impose a global lock order and always acquire locks in that order.

The classic illustration is the dining philosophers: five people, five forks, and everyone reaching for their left fork first.

The distributed cousin: livelock

Across services the version I see most is livelock: everyone is busy, nobody makes progress. Picture a fleet of clients whose auth tokens expire at the same moment and all retry instantly, in lockstep, hammering the service that would let them recover. The fix is the same idea as lock ordering, applied to time: exponential backoff with jitter, so retries spread out instead of synchronising.

Related: Synchronization · Threads and Processes · Types of Failure · Fallacies of Distributed Computing