Course contentsShow
← Java
Lesson 2704 of 2,87049. Synchronization and LockingFree lesson

Breaking Livelock: Randomization and Backoff

Discover how introducing randomness or exponential backoff prevents synchronized reactive behavior.

Breaking Livelock: Randomization and Backoff

You'll learn how to prevent livelock by introducing randomness or exponential backoff to break synchronized reactive behavior.

The Problem with Symmetric Politeness

In our previous livelock examples, threads became stuck in a cycle of mutual politeness—each thread responded to the other in exactly the same way, at exactly the same time. They're like two people trying to pass in a hallway who keep stepping in the same direction simultaneously. The issue is their perfectly synchronized reactions.

Solution 1: Randomization

Introduce random delays when a thread detects contention. Instead of immediately retrying or backing off predictably, add unpredictability:

When a thread encounters a conflict, it waits for a random duration before trying again. This breaks the symmetry—it's unlikely both threads will choose the exact same random wait time, so eventually one will proceed while the other waits.

Think of it like two people in the hallway: if they both pause for different random moments before moving again, they'll naturally desynchronize and one will get through first.

Solution 2: Exponential Backoff

Use exponential backoff: each retry waits progressively longer. Start with a small delay (e.g., 1ms), then double it after each failed attempt (2ms, 4ms, 8ms, etc.), often with a maximum cap.

This works because:

  • Initial attempts are fast when contention is low
  • Growing delays reduce collision probability over time
  • Even if threads start synchronized, their backoff times will likely diverge

Combining Both Approaches

The most robust solution combines exponential backoff with randomization: use growing delay ranges with a random value chosen from each range. This maximizes the chances that threads will desynchronize quickly.

Key Takeaway: Break livelock by adding randomness or exponential backoff to retry logic, ensuring threads don't remain synchronized in their reactive behavior indefinitely.