Livelock

TL;DR

• A Livelock occurs when two or more threads are actively changing their state in response to each other, but doing so prevents either from making actual progress.
• Unlike a deadlock, the threads are not blocked (they are RUNNABLE and consuming CPU), but they are stuck in an infinite loop of yielding to each other.

Concept

Imagine two people walking towards each other in a narrow hallway.

• Person A steps to the right to let B pass.
• Person B steps to the left to let A pass.
• They are still blocking each other.
• Person A steps to the left.
• Person B steps to the right.
• They are still blocking each other.

They are continuously moving (not deadlocked/frozen), but they are not making any forward progress (livelocked). In programming, this often happens when you write overly-polite error recovery code where threads detect a conflict, back off, and instantly retry at the exact same time.

Examples

class Pedestrian {
    private String name;
    private boolean isPolite;
    
    public Pedestrian(String name) { this.name = name; this.isPolite = true; }
    
    public void pass(Pedestrian other) {
        while (this.isPolite && other.isPolite) {
            System.out.println(this.name + ": 'You first, " + other.name + "!'");
            
            try { Thread.sleep(100); } catch (Exception e) {}
            
            // They both keep yielding to each other infinitely
            // Neither of them ever successfully executes the logic below this loop
        }
        System.out.println(this.name + " passed successfully.");
    }
}

public class LivelockExample {
    public static void main(String[] args) {
        Pedestrian alice = new Pedestrian("Alice");
        Pedestrian bob = new Pedestrian("Bob");
        
        // They will livelock instantly
        new Thread(() -> alice.pass(bob)).start();
        new Thread(() -> bob.pass(alice)).start();
    }
}

Interview Questions

Q: What is the difference between Deadlock and Livelock?
A: In a Deadlock, threads are stuck in the BLOCKED or WAITING state. They are completely frozen and consume 0% CPU.
In a Livelock, threads are in the RUNNABLE state. They are actively executing code, usually an infinite loop of backing off and retrying, which causes CPU usage to spike to 100%, but no actual business logic is accomplished.

Q: How do you fix a Livelock?
A: The most common solution to a livelock is to introduce randomized backoff timers. Instead of both threads waiting exactly 100ms and retrying simultaneously, Thread A waits random(10, 100) ms and Thread B waits random(10, 100) ms. This random jitter ensures that one thread will wake up slightly earlier than the other and successfully acquire the lock/resource.