Bounded Priority Rotation¶
Coordination rule — instantiates Progress-Guarded Livelock Disruption
Breaks a mutual-yielding stalemate by imposing a strict precedence order — but rotates who holds priority on a bound, so the winner keeps changing and no actor is permanently deprived.
Many livelocks are made of politeness: two actors each defer to the other, and the deference itself is what keeps them stuck. Bounded Priority Rotation breaks the tie by ranking the contending actors so exactly one is entitled to proceed — and then rotating that ranking on a fixed bound, so precedence circulates instead of freezing. Its distinguishing idea is that all actors stay active (unlike a single-token scheme that idles everyone but one); conflicts are simply decided by a rotating rank. That rotation is what separates it from a static priority — which permanently starves the loser — and from a token, which serializes everyone.
Example¶
At a busy unsignalled junction, two drivers each wave the other on: "after you," "no, after you." The whole queue seizes in a spasm of courtesy — plenty of gestures, not one car through. Bounded Priority Rotation is the rule a four-way-stop convention or a metering signal encodes: at each moment one approach is ranked first and simply goes; the rank then rotates to the next approach on a bound — every few seconds, or every N cars — so no lane is ever permanently starved. Courtesy is replaced by a crisp, rotating right-of-way, and throughput resumes precisely because the symmetry that caused the mutual yielding is broken — but broken fairly, so the arrangement is one everyone will accept next time too.
How it works¶
- Impose a total order. Rank the contending actors so ties resolve deterministically — the symmetry break that ends the mutual deference.
- Grant the top rank the right of way. The highest-ranked actor makes its state transition; others defer only when in direct conflict, so uncontended actors keep moving.
- Rotate on a bound. Precedence circulates on a fixed period (time, turns, or served-count), so the "winner" keeps changing.
- Guarantee reach. The bound ensures every actor reaches the top of the order within a finite window — the property that makes it starvation-free rather than merely unstuck.
Tuning parameters¶
- Rotation period — how long a rank holds before rotating. Short is very fair but adds switching overhead; long is efficient but risks transient starvation of whoever is currently low.
- Ranking basis — round-robin, longest-wait-first (aging), or cost-of-delay. An aging basis auto-prioritizes whoever has been starved longest.
- Conflict scope — whether priority governs always, or only on direct contention. Narrower scope preserves parallelism among non-conflicting actors.
- Preemption — may a higher rank interrupt a lower's in-flight action, or only gate new conflicts. Preemption is more responsive but can waste partial work.
- Tie-break determinism — the fallback order (IDs, timestamps) that guarantees a unique winner when ranks themselves tie.
When it helps, and when it misleads¶
Its strength is that it is cheap, local, needs no central coordinator, and converts a symmetric stalemate into guaranteed progress with a fairness guarantee a static priority lacks — the rotation acts as a starvation guard in the same spirit as priority aging in a scheduler.[^aging] Because non-top actors are not idled, it preserves parallelism.
Its failure modes: rotation adds switching overhead, and a rotation period set too long still starves someone transiently; a poorly chosen ranking basis can systematically disadvantage one class of actor under load; and it assumes the loop is the kind a precedence order can resolve — it does nothing if the cause is not a symmetric tie. The classic misuse is to freeze the rotation "temporarily," at which point it decays into a static priority that quietly serves the strongest actor forever. The discipline is to monitor per-actor wait and served counts, and to keep the rotation actually rotating.
How it implements the components¶
Bounded Priority Rotation fills the asymmetry-with-fairness side of the archetype:
symmetry_breaking_rule— the strict, rotating precedence order that ends the symmetric mutual yielding sustaining the loop.fairness_and_starvation_guard— the bound on rotation guarantees every actor reaches priority within a finite window, so breaking the tie never permanently deprives anyone.
It enforces no single-holder exclusive region — that mutual-exclusion boundary (safe_race_boundary) belongs to Leader Election or Token Passing; it invokes no outside authority (external_progress_resolver, stakeholder_priority_contract — that's External Arbitration/Escalation); and it halts nothing via cooldown (quiescence_or_hold_window — Circuit Breaker and Cooldown).
Related¶
- Instantiates: Progress-Guarded Livelock Disruption — it is the coordination-rule change that replaces symmetric deference with a fair, rotating precedence.
- Sibling mechanisms: Leader Election or Token Passing · External Arbitration/Escalation · Exponential Backoff with Jitter · Circuit Breaker and Cooldown · Randomized Retry Desynchronization
Editorial Notes¶
Form Classification¶
Form family: Rule, Policy & Commitment
Rationale: Breaks a mutual-yielding stalemate by imposing a strict precedence order — but rotates who holds priority on a bound, so the winner keeps changing and no actor is permanently deprived, making its operative form a standing constraint, permission, threshold, obligation, or conditional rule.
Independent corroboration: The frozen evidence defines Bounded Priority Rotation as 'Breaks a mutual-yielding stalemate by imposing a strict precedence order — but rotates who holds priority on a bound, so the winner keeps changing and no actor is permanently deprived', so its operative form is Rule, Policy & Commitment.
Review outcome: Independent reviewer agreement; high confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Cross-disciplinary synthesis
Present-day reach: Multi-domain
Rationale: Rotating bounded priority to prevent livelock and starvation is a concurrency and scheduling technique.
Related originating lineages:
- Operations Research — Fair scheduling and service disciplines formalize rotation under scarce capacity.
- Political Science — Rotating offices and precedence provide an institutional fairness analogue that prevents permanent domination.
Review resolution: Computer science is the agreed primary lineage through bounded waiting and rotating priority in schedulers. Operations research contributes queue discipline and political science contributes rotation as an anti-entrenchment institution; the generalized mechanism is a cross-disciplinary Encyclopedia synthesis.
Attribution caveat: Scheduler fairness and institutional office rotation developed in distinct traditions; computer science is primary because the mechanism specifies an executable bounded-priority rule.
Encyclopedia synthesis: The exact catalogued form synthesizes established practice rather than reproducing a single standard historical label.
Review outcome: Reconciled after independent review; high confidence.