Livelock

The problem it solves

Two threads, both trying not to deadlock. Each takes the first lock, tries the second, and if it cannot get it, releases the first and starts over rather than waiting. No thread ever blocks, so no cycle can form, so deadlock is impossible.

And the program can still get nothing done, forever, at full CPU.

Livelock is the failure where every individual decision is correct and defensive and the emergent behaviour is a system that makes no progress. The threads are running. They are executing instructions. The process looks healthy in every way that a deadlock does not: no thread is parked, no lock is held for long, a deadlock detector finds nothing because there is no cycle to find. And the counter that should be going up is not going up.

It is worth its own page because it is the failure that makes people distrust their own reasoning. The deadlock fix was correct. The problem is that it introduced a different failure that the fix’s logic cannot see.

The mechanism

Livelock needs symmetry. Both threads make the same decision at the same moment, and the decision is one that undoes the other’s progress.

Thread 1 takes A, finds B held, releases A, retries. Thread 2 takes B, finds A held, releases B, retries. Both are now back at the start, both grab their first lock again, both fail again. Nothing in the rules says this must stop, because at every point both threads are behaving exactly as designed.

The fix is not to try harder or back off longer. It is to break the symmetry. If the two threads stop making identical decisions at identical times, one of them wins and the other simply waits its turn. Two ways to do that:

• Impose an order. Both take A before B, so one of them gets both and the other blocks briefly. This is lock ordering again, and it fixes deadlock and livelock at once.
• Randomise the backoff. Wait a random interval before retrying, so two threads that collided do not collide again on the next attempt. This is why every retry loop in every distributed system carries jitter, and it is the same mechanism as randomised election timeouts in Raft.

The general principle is worth carrying past this page: when two agents must not do the same thing at the same time, and neither can be told which is which, randomness is the cheapest way to tell them apart.

What the enumeration shows

Livelock is non-termination, so no enumerator can observe one without deciding how long to watch. This page therefore bounds each run and reports “did not finish” — never “never finishes”, which is a claim a finite run cannot support.

With the threads taking locks in opposite orders, 927 of 3,000 sampled runs get nowhere: they hit the step bound with both threads still grabbing, failing and releasing. With both taking the locks in the same order, none do.

Two things are worth checking in the explorer. First, no outcome anywhere is a deadlock — the threads are never stuck, which is exactly why a deadlock detector reports a healthy process. Second, step through a livelocked schedule slowly: the pattern is try A / try B / back off / try A / try B / back off, with the state panel showing locks being taken and released constantly and the work counter never moving.

The numbers worth carrying

• Opposite lock order with polite backoff: 927 of 3,000 runs make no progress. Common order: 0.
• Livelock never appears as a blocked thread, so it does not show up in a thread dump the way deadlock does. What it shows as is 100% CPU and flat throughput, which is the signature to recognise.
• Randomised backoff reduces the chance of repeated collision geometrically: with a random wait drawn from n slots, the probability of colliding k times running is n^-k. Even a small amount of jitter converges fast.

Where it breaks down

Livelock is not always about locks. Two systems that each back off when the other is busy, two schedulers that each yield to the other, two nodes that each stand down during an election — same shape. Any protocol where “detect contention, retreat, retry” is symmetric can livelock.

Backoff without jitter is still symmetric. Doubling the wait after each failure does not help if both threads double identically: they collide, both wait 2ms, collide, both wait 4ms. The randomness is the part that does the work, not the growth.

Starvation is a different failure. In livelock nobody progresses; in starvation the system progresses and one participant never gets a turn. They are often confused because both look like “a thread that never finishes”.

Bounded observation cannot prove absence. The ordered variant shows zero non-terminating runs among those explored, which is strong evidence and not a proof — unlike the deadlock page, where exhaustive enumeration genuinely proves the cycle is unreachable. The page says which it has.

What people get wrong

“It is a kind of deadlock.” It is the opposite in every observable way. Deadlock: threads blocked, CPU idle, detector fires. Livelock: threads running, CPU pinned, detector silent.

“Adding backoff fixed it.” Adding randomised backoff fixed it. Fixed backoff preserves the symmetry that caused it.

“trylock is safer than lock.” It removes the possibility of blocking, which removes deadlock and introduces this. Neither primitive is safe by itself; the acquisition policy is what determines which failure you get.

“It will resolve eventually.” With randomness, yes, quickly. Without it, there is no mechanism that makes it resolve — the state after a collision is identical to the state before.

In production

You are most likely to meet this outside lock code. Retry storms are livelock at the scale of a distributed system: every client detects failure, every client backs off identically, every client returns at the same moment and fails again — see retry storms for the same dynamic with a network in the middle. The standard fix is identical: full jitter, meaning a random wait between zero and the exponential cap rather than the cap plus noise.

Inside a process, tryLock with a bounded retry count and a jittered sleep is the usual construction, and it should be a fallback rather than a first choice: consistent lock ordering prevents both deadlock and livelock without needing to retry at all.

The diagnostic to remember: if CPU is high and throughput is flat, and thread dumps show threads running rather than parked, look for a retry loop where everybody retreats at once.

The follow-up questions

“What is the difference between deadlock and livelock?” — Blocked and idle versus running and useless. Say what each looks like in a thread dump; that is the answer that shows you have diagnosed one.

“You replaced lock with tryLock and a retry. What did you introduce?” — This page. Then say jitter.

“Why does randomised backoff work?” — It breaks the symmetry. Two threads that cannot be told apart by anything else can be told apart by luck.

“Your service is at 100% CPU and serving nothing. Where do you look?” — Retry loops and contention, not blocked threads. A thread dump full of running threads is the tell.