Randomized Retry Desynchronization¶
Retry policy — instantiates Progress-Guarded Livelock Disruption
Injects randomness into each actor's retry timing so identical, lock-stepped actors scatter in phase and stop making the same move at the same instant.
Some livelocks survive precisely because the actors are identical and synchronized: they detect the same conflict, react the same way, at the same moment, and so collide again on the very next tick. Randomized Retry Desynchronization breaks that by making each actor wait a random amount before retrying, so their phases scatter and one gets clear air to complete a move while the others are still waiting. Its defining idea is that the randomness is a symmetry-breaker, not merely a delay: two deterministic, indistinguishable actors cannot reliably break a tie between themselves without some source of difference, and an unbiased coin is the cheapest such source. It changes nothing about who the actors are or what they want — only when they act — and that is enough to dissolve the lock-step.
Example¶
Two threads share a lock-free counter guarded by compare-and-swap. Under contention they livelock: thread A reads the value, thread B reads the same value, A's swap succeeds, B's swap now fails because the value moved, so B retries — reads afresh, and this time its swap lands first, making A's retry fail. Each keeps invalidating the other's attempt; both spin at full tilt, neither reliably commits. Because the two are symmetric and retry immediately, they re-collide on essentially every cycle. The fix is a randomized backoff before retry: after a failed swap, each thread waits a small random interval before reading again. The two waits are almost never equal, so their retries fall out of phase — one thread reaches its compare-and-swap while the other is still pausing, and its update finally sticks. No priority, no coordination, no central authority; just enough injected noise to make the two actors stop moving in unison.
How it works¶
The policy inserts a randomly-drawn wait between a failed attempt and the next one, sized from a window rather than a fixed constant. The essential property is decorrelation: because each actor draws independently, the probability that they keep colliding falls off sharply with each round, so progress becomes overwhelmingly likely even though it is never guaranteed on any single try. What distinguishes this from a growth-based backoff is the emphasis: the job here is to break phase alignment between symmetric actors, not principally to shed load — the randomness is doing the work, and it can be applied over a fixed window with no exponential growth at all.
Tuning parameters¶
- Randomization window — the range the wait is drawn from. Too narrow and the actors stay effectively synchronized; too wide and every retry pays needless latency.
- Distribution shape — uniform, or weighted toward shorter waits. Uniform decorrelates most simply; a skew trades some collision probability for lower typical delay.
- Growth vs. fixed window — whether the window widens after repeated collisions or stays constant. Growth also relieves load under sustained contention; a fixed window keeps latency flat when the goal is purely to break symmetry.
- Independent seeding — ensuring each actor's randomness is genuinely independent. Shared seeds or a common clock quietly re-synchronize the fleet and silently defeat the whole policy.
When it helps, and when it misleads¶
Its strength is that it needs no coordination, no shared state, and no authority: each actor decorrelates itself locally, which makes it the lightest possible cure for a symmetric livelock and the natural first reach before anything heavier. It dissolves exactly the lock-step that keeps identical actors colliding.
Its failure mode is subtle: randomness that is not actually independent. If every actor seeds the same way, draws from the same fixed window, or keys off a shared clock, they stay phase-aligned and the livelock survives the "fix" — the most common and most invisible way this policy fails. It is also probabilistic: it makes progress overwhelmingly likely, not certain, so a hard liveness guarantee still needs a deterministic backstop. And a window set too wide converts a livelock into sluggishness. The classic misuse is treating it as sufficient on its own for a system that requires a bound. The discipline is to seed each actor independently, keep the window as small as decorrelation allows, and pair it with a deterministic guarantee — a Liveness Watchdog, or a priority scheme — where progress must be assured rather than merely likely.[n1]
How it implements the components¶
Randomized Retry Desynchronization realizes the archetype's symmetry-breaking side — the components that change when and how differently actors act, not the ones that detect the stall or halt the system:
symmetry_breaking_rule— random draws turn indistinguishable, lock-stepped actors into differently-timed ones, which is what lets one proceed while the others wait.desynchronization_backoff_policy— it is the retry-timing policy: an independent, randomized wait between attempts that scatters the actors' phases apart.
It does not detect or diagnose the loop (Liveness Watchdog, State-Machine Cycle Detection), it does not halt everyone to a quiet state (Quiescence Barrier's quiescence_or_hold_window), and it breaks symmetry by chance rather than by rank — deterministic asymmetry via priority or a single token is Bounded Priority Rotation and Leader Election or Token Passing.
Related¶
- Instantiates: Progress-Guarded Livelock Disruption — it is the lightweight, per-actor move that breaks the lock-step keeping symmetric actors colliding.
- Sibling mechanisms: Quiescence Barrier · Liveness Watchdog · Exponential Backoff with Jitter · Bounded Priority Rotation · Leader Election or Token Passing · Circuit Breaker and Cooldown · State-Machine Cycle Detection · Progress Counter Heartbeat · Joint-State Cycle Trace · Contention Trace Replay · External Arbitration/Escalation
Editorial Notes¶
Form Classification¶
Form family: Control, Automation & Runtime
Rationale: Randomized Retry Desynchronization operates as a live operational control that automatically routes, enforces, adapts, or responds during execution because it injects randomness into each actor's retry timing so identical, lock-stepped actors scatter in phase and stop making the same move at the same instant.
Independent corroboration: The frozen evidence defines Randomized Retry Desynchronization as 'Injects randomness into each actor's retry timing so identical, lock-stepped actors scatter in phase and stop making the same move at the same instant', so its operative form is Control, Automation & Runtime.
Nearest alternative: Rule, Policy & Commitment — Randomized Retry Desynchronization includes features of a standing rule, threshold, contractual commitment, or policy constraint governing future conduct, but its defining operation is a live operational control that automatically routes, enforces, adapts, or responds during execution.
Review outcome: Independent reviewer agreement; medium confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Single lineage
Present-day reach: Specialized
Rationale: Randomized retry backoff used to break lockstep contention is canonical networking and distributed-systems practice.
Related originating lineages:
- Engineering & Design — Contention resolution in communication systems materially shaped the backoff lineage.
Review outcome: Independent reviewer agreement; high confidence.
Notes¶
Randomization and rank are the two ways to break a tie between symmetric actors, and they trade off. This policy uses chance — cheap, decentralized, needing no identifiers, but only probabilistically fair and never a hard guarantee. Bounded Priority Rotation and Leader Election or Token Passing use rank — a deterministic ordering or a single privileged holder — which guarantees one actor proceeds but requires distinguishable identities and some coordination to maintain. Where actors are truly anonymous and lightweight, chance is the only option available; where a firm progress guarantee is required, rank is the safer one.
[n1] Breaking symmetry between identical, deterministic actors is provably impossible without some source of difference — either randomness or distinguishing identifiers. This is the classic reason randomized backoff exists (and why two indistinguishable processes retrying in lock-step can collide indefinitely): an independent random draw is the cheapest way to manufacture the difference that lets exactly one of them win. ↩