Livelock and Starvation
Livelock keeps threads busy but useless — each repeatedly detects conflict and backs off in perfect sync — while starvation starves specific tasks of resources despite system progress.
Definition
Livelock is the state where threads continuously change state in response to each other but make no progress: two tasks each politely retrying, yielding, and retrying again forever. Starvation is the state where the system progresses but particular tasks never get scheduled or acquire resources due to unfair policies or adversarial timing. Neither blocks; both fail to finish.
Context and scope
Appears in optimistic concurrency with symmetric backoff, polite message-passing loops, and unfair schedulers starving background maintenance threads.
Common misconceptions
- Livelock is a kind of deadlock — deadlock blocks; livelock burns CPU while accomplishing nothing, which is why liveness probes can miss it
- Randomized backoff solves livelock — it breaks the symmetry with high probability, but bounds are needed to guarantee eventual success
- Starvation means the system is halted — the system progresses; specific work waits indefinitely, quietly missing deadlines
Anti-patterns
- Two services rejecting each other transactions and retrying in lockstep with identical timers
- Fair-queue-less thread pools where long tasks permanently shadow short maintenance jobs
- Monitoring thread states only, so a livelocked system shows busy threads and looks healthy
Related concepts
Related examples
Authoritative source
What it is
Two failure modes hide behind no-progress. Deadlock stands still waiting. Livelock moves constantly — retrying, backing off, handing over — and never completes. Starvation lets the whole system move while chosen tasks never do.
How it works
Livelock comes from symmetric protocols: both parties detect conflict, both yield, both retry at the same cadence. The fix is asymmetry — randomized exponential backoff, distinct priorities, or a tiebreaker resource. Starvation comes from unfair scheduling or resource policies; aging — raising effective priority with wait time — restores eventual service.
When to watch
Optimistic lock retry loops, distributed lease handoff, message redelivery between competing consumers, and scheduler configurations without fairness or aging. Alert on operation age, not only on thread state.
Pitfalls
Liveness probes see CPU and runnable threads, so livelock looks healthy — track per-operation completion rates. Backoff without jitter preserves synchrony. Distributed livelock spans services, so local thread dumps show nothing stuck; correlate retries across boundaries.