arXiv CSopen access

Wait-Free Locks Should Not Fear Later Arrivals

Wait-Free Locks Should Not Fear Later Arrivals Tong Che

NVIDIA Research USA [email protected] Can a deterministic helpable thunk lock charge a call only for the former? We present SeniorLock. Each call takes an increasing ticket and publishes itself with an atomic minimum update, so that no larger-ticket call can later replace its candidate. Its seniors are the smaller-ticket calls already active when its ticket is assigned; a later arrival always receives a larger ticket, but a delayed earlier invocation may receive one too. Repeated publication restores this guard after a senior completes, and a versioned owner compresses stale larger-ticket installations. We call the resulting guarantee retrospective wait-freedom: an operation’s worst-case bound may depend on its seniors when its key is fixed, but not on later invocations. To our knowledge, SeniorLock is the first deterministic helpable thunk lock in this model with such a bound. If 𝛽𝐷 is the ticket-time seniority of 𝐷, then Lock(𝐷) uses 𝑂 (𝛽𝐷 + 1) management steps and 𝑂 ((𝛽𝐷 + 1) (𝑇 + 1)) total local steps under every asynchronous schedule. Since 𝛽𝐷 ≤ 𝜅𝐷 − 1, the result is also point-contention adaptive. SeniorLock is also universal. One instance linearizably turns any deterministic sequential object whose private representation is accessed by thunks satisfying the uniform 𝑇 -step service contract into SeniorObj, a retrospective wait-free object that never copies that representation into one atomic state transition (Section 6.2). Prior generalized compare-and-swap work obtains the fixed-senior bound for atomic state transitions [18]. SeniorLock extends it to bounded, multi-step, effectful thunks. The bound relies on resettable min-CAS as one base-object step. For fixed 𝑁 , implementing this primitive from unbounded read-write-conditional registers has tight Θ(𝑁 ) black-box location complexity. With infinitely many arrivals, no read/write/CAS implementation has constant quiescent location complexity (Section 9).

arXiv:2607.16571v1 [cs.DC] 18 Jul 2026

Abstract Helping seems to make a lock wait-free: wrap the critical section in an idempotent thunk that any process can finish once the holder stalls. Yet helping protects the system, not the call. An overwritable candidate lets later requests bump one another in sequence, so a call can be forced to help newcomer after newcomer and never return, while point contention never exceeds two. We ask whether a call can instead be charged only for the requests active when it takes its ticket, never for what arrives afterward. We show that the answer is yes. SeniorLock is a deterministic helpable thunk lock in which a call with ticket-time seniority 𝛽 finishes in 𝑂 ((𝛽 + 1) (𝑇 + 1)) local shared-memory steps, where 𝑇 bounds one thunk’s cost, independently of later invocations. We call this guarantee retrospective wait-freedom. The same lock doubles as a universal construction we call SeniorObj: it turns any deterministic sequential object whose operations are bounded, concurrently idempotent thunks into a retrospective wait-free one, with no copying of its representation and, when no senior is active, at essentially the native cost of the operation. CCS Concepts: • Theory of computation → Concurrent algorithms; Shared memory algorithms. Keywords: wait-freedom, thunk locks, minimum update, helping, retrospective wait-freedom, universal constructions, adaptivity, idempotence, space lower bounds

1

Introduction

Helping seems to turn a lock into a wait-free object. Package the critical section as an idempotent thunk; if its holder stalls, another process finishes the thunk and releases the lock [9, 12, 13, 27]. The intuition confuses global progress with the progress of one call. The cited deterministic thunk locks are lock-free, while randomized wait-free alternatives give probabilistic contention-dependent bounds [1, 11]. In a single-candidate deterministic design, a newly arrived request can redirect the victim’s every step. Only the victim and the current redirecting call need be active, so point contention stays at two while the victim takes infinitely many steps without returning (Section 3). The gap is temporal. The calls already active at a chosen step are finite; the stream arriving afterward need not be.

Contributions. 1. We formulate retrospective wait-freedom, which freezes an operation’s contention-dependent bound when its key is fixed, and present SeniorLock, a deterministic helpable thunk lock with 𝑂 ((𝛽 + 1) (𝑇 + 1)) local-step complexity (Sections 2–4). 2. We prove a finite charge-set service theorem that applies beyond FAI ticket order, and give counterexamples showing why one-time publication and unversioned ownership lose the bound (Sections 6 and 7). 1

3. The same lock is also universal. We derive SeniorObj, an effectful retrospective universal construction that turns any deterministic sequential object whose operations satisfy the uniform concurrent-idempotence service contract into a retrospective wait-free one, with no representation-copying step (Section 6.2). 4. Resettable min-CAS is not a free primitive. For a fixed population of 𝑁 processes, we prove a tight Θ(𝑁 ) location bound for any long-lived black-box implementation from read-write-conditional registers, even with unbounded values, and that no read/write/CAS implementation keeps constant quiescent location complexity once arrivals are unbounded (Section 9).

2

idempotent, but excludes the lock-management operations shown in Algorithm 1. Definition 2 (Helpable thunk lock). A call Lock(𝐷) returns only after 𝐷.done is true. The logical execution interval of 𝐷 lies between the invocation and response of Lock(𝐷). Logical execution intervals of distinct descriptors do not overlap. We abbreviate Lock(𝐷, 𝑓 ) to Lock(𝐷). The interface serializes logical thunk intervals rather than physical acquire/release ownership; late physical runs are noneffectual. Contention and complexity. A lock call is active from invocation through response; we use the standard pointcontention measure [7]. For Lock(𝐷), its maximum point contention is

Model and lock semantics

𝜅𝐷 = max |{𝐸 : Lock(𝐸) is active at configuration 𝑠}| ,

Shared-memory model. There are 𝑁 deterministic asynchronous processes, each with at most one outstanding Lock call, communicating through linearizable atomic objects [8, 20]. One base-object access is one step, and the scheduler is unrestricted [19]. The main bound is independent of 𝑁 ; Section 9 fixes 𝑁 for its register-space classification.

𝑠

where the maximum ranges over configurations during Lock(𝐷). Retrospective wait-freedom. Point contention measures overlap at a configuration. The following object-independent property instead fixes the operations that may enter a contention-dependent bound at a designated step.

Descriptors and idempotent thunks. Every lock call allocates a fresh descriptor

Definition 3 (Retrospective wait-freedom). Consider any concurrent object whose operations each receive a unique key from a total order, fixed no later than some designated step 𝜎𝑜𝑝 during the operation’s execution. The smaller-key operations active immediately after 𝜎𝑜𝑝 are 𝑜𝑝’s seniors; its seniority is the size of that set. An implementation is retrospective wait-free if there is a function 𝑓 such that every operation completes within 𝑂 (𝑓 (seniority)) steps of its invoking process under every asynchronous schedule, independent of operations invoked after 𝜎𝑜𝑝 .

𝐷 = (𝐷.id, 𝐷.ticket, 𝐷.done, 𝐷.thunk, 𝐷.result). The identity and ticket are immutable and globally unique. 𝐷.done changes monotonically from false to true; reads and the one false-to-true update are linearizable atomic accesses. A run of a thunk is the sequence of shared-data steps taken by one process while executing or helping it. For an execution 𝐸, let 𝐸|𝐷 be the projection to steps belonging to runs of 𝐷’s thunk. We require the following observational form of concurrent idempotence from Ben-David, Blelloch, and Wei [12].

An operation’s seniors are a subset of the operations active at 𝜎𝑜𝑝 , so retrospective wait-freedom implies pointcontention adaptivity and additionally makes the bound independent of invocations after 𝜎𝑜𝑝 . We instantiate Definition 3 for SeniorLock’s Lock operation, using the FAI ticket as the key.

Definition 1 (Concurrent idempotence). For every valid execution 𝐸 containing arbitrarily interleaved runs of one thunk together with arbitrary other shared-data steps, there is a subsequence 𝐸 ′ of 𝐸|𝐷 such that replacing 𝐸|𝐷 by 𝐸 ′ leaves a valid history consistent with one run, preserves all non-thunk steps and responses, and is indistinguishable under every continuation. If a run finishes, the last step of the first finished run is the end of 𝐸 ′ .

SeniorLock seniority. For the call Lock(𝐷), let 𝜎𝐷 = 𝜏𝐷 be the linearization point of 𝐷’s FAI and let 𝑡𝐷 be the returned ticket. Define Seniors(𝐷) = {𝐸 : 𝐸 is active immediately after 𝜏𝐷 ,

Thus the physical runs contain one logical copy whose logical execution interval runs from the first thunk step to the end of the first finished run; subsequent steps are noneffectual. Every 𝐷.run() call, independently of helper count, takes at most 𝑇 local shared-memory steps to observe done or finish a run and set done; it does not return while 𝐷 remains active. If the thunk returns a value, its idempotence log records that value in the descriptor before publishing done, and Lock returns the recorded value. The bound 𝑇 includes the descriptor-local logging needed to make the thunk

𝜏𝐸 < 𝜏𝐷 }. 𝐷’s seniority is 𝛽𝐷 = |Seniors(𝐷)|. Here 𝜏𝐸 must exist: an invoked call still paused before its FAI is not a senior. Because FAI tickets increase, 𝜏𝐸 < 𝜏𝐷 is equivalent to 𝑡𝐸 < 𝑡𝐷 for ticketed calls. Every later arrival is therefore a larger-ticket call; the converse may fail for a call invoked before 𝜏𝐷 but delayed before its FAI. All calls represented in Seniors(𝐷) overlap Lock(𝐷) at 𝜏𝐷 , so 𝛽𝐷 ≤ 𝜅𝐷 − 1. The inequality can be strict by an arbitrary amount: 2

after 𝜏𝐷 , any number of larger-ticket calls may become active before 𝐷’s first minimum update. Our main bound depends on 𝛽𝐷 , not on that later peak. This differs from interval contention, which counts every call that overlaps Lock(𝐷) at any time. Interval contention can be unbounded while point contention is two: one later call may finish before the next begins. All complexity bounds count shared-memory steps by the process invoking Lock(𝐷). A management step is any shared-memory access shown in Algorithm 1 outside a thunk run. The bounds do not cover aggregate system work or wall-clock time under an asynchronous scheduler.

contention two. Thus the local bit does not impose a shared order; a pending request needs a shared ordering constraint. An unversioned installation cohort. Even with a monotone candidate, selection and owner installation are separate atomic steps. Suppose 𝑟 helpers read the same candidate 𝑥 and an empty, untagged owner, then all pause before CAS. After the first helper installs and completes 𝑥, every delayed CAS can successfully install the now-done 𝑥 again whenever the owner returns to null. All 𝑟 calls remain simultaneously active, so this does not violate a point contention bound of 𝑟 +1. Repeating such a cohort after several smaller-ticket completions gives a quadratic number of victim-visible tenures; Section 7 formalizes the schedule.

Base objects. The lock contains three abstract objects. • Next is an unbounded fetch-and-increment (FAI) counter. • Cand is a resettable min-CAS object. It stores either INF or a descriptor token, ordered by the descriptor’s immutable ticket, and supports atomic Read, CAS, and MinUpdate(𝑥) : 𝐶 ← min(𝐶, 𝑥). The initial value is INF. • Owner is a CAS object containing (𝑝, 𝑔), where 𝑝 is a descriptor pointer or ⊥ and 𝑔 is an unbounded generation. Initially Owner = (⊥, 0).

The ticket guard. Minimum update supplies the shared ordering constraint. Suppose 𝐷 has ticket 𝑡𝐷 and performs Cand.MinUpdate(𝐷). Immediately afterward, Cand ≠ INF

Cand.ticket ≤ 𝑡𝐷 .

(1)

No later request can falsify (1). Only a reset of the exact current candidate can do so. Our algorithm permits such a reset only after that candidate is done. Any smaller-ticket candidate is either from a call active at 𝜏𝐷 or is the one possible completed-token residue, which contributes one cleanup charge. Before (1) is established, several active helpers may have read a larger-ticket candidate and paused before owner installation. They may resume after the guard. If owner emptiness were represented by an untagged null pointer, all of those stale installations could succeed one after another as the owner repeatedly returned to null. In SeniorLock they all expect the same generation. At most one succeeds; when that tenure ends, the generation changes and the rest fail. No new larger-ticket installation can be prepared while the guard holds. Repeated self-publication restores the guard after a legitimate smaller-ticket completion, while direct owner installation uses the successful CAS itself as the unique selection event. The mechanism accepts any total order for which the call has a finite charge set. With increasing FAI tickets, the senior set itself is a valid charge set (Section 6).

Tickets are unique, so they totally order descriptors. The same candidate object also supports exact-token CAS reset, so its minimum-update monotonicity holds between successful resets. The theorem assumes unbounded tickets and generations and fresh descriptors; its three-object count is lock-resident only (Section 8).

3

and

From replacement to a ticket guard

Destructive replacement. The single-overwrite candidate pattern admits unbounded cumulative bypass at constant point contention. Consider a single overwrite slot and a victim 𝐷. In round 𝑖, let 𝐷 publish and pause; start one later call 𝑌𝑖 , overwrite 𝐷, and let 𝐷 help 𝑌𝑖 finish. Return 𝑌𝑖 before starting 𝑌𝑖+1 . The victim takes steps in every round and never completes, but at every configuration at most 𝐷 and one 𝑌𝑖 are active. The complexity driver is cumulative bypass, not point contention. A stranded descriptor-side obligation. Adding only a descriptor-local selected bit to this pattern still permits a helper to mark a descriptor after the candidate has changed. That mark is persistent only in the descriptor, not in the arbitration state. For example, let a smaller-ticket request 𝐸 replace 𝐷 after a helper reads Cand = 𝐷 but before it marks 𝐷. After 𝐸 finishes and clears the candidate, the stale helper can mark 𝐷 as selected. Now 𝐷 is selected but absent from Cand. Sequential larger-ticket calls can repeatedly install themselves immediately before 𝐷’s owner CAS, and 𝐷 can be forced to help each of them. Again the schedule has point

4

The SeniorLock algorithm

Algorithm 1 gives the construction. The requester initializes its descriptor, obtains a ticket, and repeatedly publishes itself before helping. The publication is unconditional while the descriptor is not done. A delayed smaller-ticket request can replace the current candidate token, so every still-active requester republishes to restore its ticket guard after that request completes. 3

Table 1. Authorization for destructive state changes.

Algorithm 1 SeniorLock for one helpable thunk lock. 1: procedure Lock(𝐷, 𝑓 ) 2: 3: 4: 5: 6: 7:

𝐷.thunk ← 𝑓 ; 𝐷.done ← false; 𝐷.result ← ⊥ 𝐷.ticket ← Next.FAI() while ¬𝐷.done do Cand.MinUpdate(𝐷) Assist return 𝐷.result

Change

Required evidence

Owner : (⊥, 𝑔) → (𝑥, 𝑔)

Empty owner was read in generation 𝑔; afterward 𝑥 was read not done. 𝑥 was observed done; the CAS matches the exact descriptor token. 𝑥 was observed done while the same owner tenure was still installed.

Cand : 𝑥 → INF

8: procedure Assist 9: (𝑤, 𝑔) ← Owner.Read() 10: if 𝑤 ≠ ⊥ then 11: HelpOwner(𝑤, 𝑔) 12: return

Owner : (𝑥, 𝑔) → (⊥, 𝑔 + 1)

13: 14: 15:

5

16: 17: 18: 19: 20:

𝑥 ← Cand.Read() if 𝑥 = INF then return if 𝑥 .done then Cand.CAS(𝑥, INF) return if Owner.CAS((⊥, 𝑔), (𝑥, 𝑔)) then HelpOwner(𝑥, 𝑔)

An owner tenure (𝑥, 𝑔) begins when a CAS changes (⊥, 𝑔) to (𝑥, 𝑔) and ends when a CAS changes (𝑥, 𝑔) to (⊥, 𝑔 + 1). Table 1 summarizes the state changes that require proof obligations. Lemma 1 (Generation uniqueness). For every generation 𝑔, at most one descriptor is installed from (⊥, 𝑔). After generation 𝑔 ends, every delayed installation expecting (⊥, 𝑔) fails. Lemma 2 (Release after completion). If tenure (𝑥, 𝑔) ends, then 𝑥 .done was true before the releasing CAS.

21: procedure HelpOwner(𝑥, 𝑔) 22: if Owner.Read() ≠ (𝑥, 𝑔) then 23: return 24: 25: 26: 27: 28:

4.1

Safety

Lemma 3 (Candidate responsibility). If Cand = 𝑥 and 𝑥 is not done, no process can reset Cand from 𝑥 to INF. A minimum update can replace 𝑥 only by a smaller-key descriptor.

if ¬𝑥 .done then 𝑥 .run() if 𝑥 .done then Cand.CAS(𝑥, INF) Owner.CAS((𝑥, 𝑔), (⊥, 𝑔 + 1))

Lemma 4 (One tenure per descriptor). Every descriptor is installed as owner at most once. Safety invariants. CAS on the complete owner pair gives generation uniqueness; the release code first observes the monotone done flag. Candidate reset likewise follows a done observation and compares the exact token. After one tenure, pre-release installation snapshots expect the old generation, while post-release snapshots observe done, proving one tenure. See Appendix A (“Safety invariants”) for the detailed proofs.

Critical interleavings

The done test and generation form a handshake. The required order in Assist is read empty owner (⊥, 𝑔) ≺ read 𝑥 .done ≺ owner CAS. Assume the middle read returns false but 𝑥 becomes done before the CAS. The only way to make 𝑥 done is through a tenure that must be released before the owner can again be empty. That release writes generation at least 𝑔 + 1, so the delayed CAS expecting 𝑔 fails. If the done test were moved before the owner read, a helper could read false, pause while another helper completes 𝑥, then read the new empty generation and install the completed descriptor. This ownerread/done-read/CAS order is required for correctness.

Theorem 1 (Safety). SeniorLock implements a helpable thunk lock. Proof sketch. Every effectual run follows validation of one owner tenure. A later tenure cannot begin before the prior descriptor is done; if a validated helper resumes after release, concurrent idempotence makes that run noneffectual. Thus generation order serializes logical thunk intervals. Publication and completion place each such interval within its call, and the generation order respects real-time precedence. □

Other stale observations. Three further schedules – a stale candidate becoming owner, a late physical run resuming after revalidation, and a new candidate published just after a reset – are handled by the same combination of exacttoken cleanup and concurrent idempotence. See Appendix A (“Critical interleavings”) for all four schedules.

6

Finite charge-set progress

The charging argument accepts any total order for which the operation has a finite charge set. It bounds a call by 4

a finite charge set containing every smaller-key operation that can affect it. With increasing FAI tickets, the senior set is a valid charge set, yielding retrospective wait-freedom (Definition 3). Section 9 instead uses static keys, which retain a finite wait-free bound but may charge later arrivals. The progress argument uses only monotone completion and bounded service; it is independent of the thunk semantics in Section 2.

Lemma 6 (Smaller-key chain compression). Smaller-key publications never destroy the guard or split a guarded interval. Within one guarded interval, changes of Cand caused by firsttime smaller-key publications form a strictly decreasing key chain of length at most 𝑚. Proof sketch. Every effective smaller-key publication strictly decreases the candidate key and comes from the charge set of size 𝑚. Repeated publications do not extend this chain, so they share one guarded interval rather than creating 𝑚 contention-sized phases. □

Definition 4 (Ordered service instance). An ordered service instance follows the control flow of Algorithm 1, except that every operation 𝑥 receives an arbitrary unique immutable key 𝜌 (𝑥) before its first publication. The done flag may be replaced by a monotone predicate Done(𝑥) that can first become true only through service of owner 𝑥. After revalidating tenure (𝑥, 𝑔), a matching service call makes or observes Done(𝑥) within at most 𝑇 local shared-memory steps. Every pending requester repeatedly applies Cand.MinUpdate(𝑥) before calling Assist.

Lemma 7 (Opening the guard). Before 𝐷 is done, every transition from a 𝐷-guarded configuration to an unguarded configuration is associated with a completed descriptor in S𝐷 , except for at most one done descriptor already resident in Cand at 𝜎𝐷 . Each descriptor in S𝐷 is associated with at most two such transitions. Proof sketch. The guard can be destroyed only by a successful reset of the exact current candidate after that candidate is done. Except for the initial residue, a smaller-key candidate belongs to S𝐷 by the charge-set definition. It is removed once after completion and can be reinserted only by one alreadystarted requester iteration, giving multiplicity two. □

Fix an execution 𝛼 and a descriptor 𝐷 in it. Let 𝜎𝐷 be the point at which 𝐷’s key is fixed and write 𝑑 = 𝜌 (𝐷). The pending suffix of 𝐷 is the part of 𝛼 after 𝜎𝐷 and before 𝐷 becomes done, or the entire remaining execution if it never does. Definition 5 (Charge set). A finite set S𝐷 (𝛼) is a charge set for 𝐷 in 𝛼 if every descriptor 𝑥 ≠ 𝐷 with 𝜌 (𝑥) < 𝑑 belongs to S𝐷 (𝛼) whenever, during 𝐷’s pending suffix, at least one of the following holds: (i) 𝑥 is not done at 𝜎𝐷 and is named there by Cand or Owner; (ii) the requester of 𝑥 publishes 𝑥 after 𝜎𝐷 ; (iii) 𝑥 begins an owner tenure after 𝜎𝐷 . Set 𝑚 = |S𝐷 (𝛼)| and abbreviate the set by S𝐷 when 𝛼 is fixed.

Lemma 8 (Done-candidate episodes). For each descriptor 𝑥, there are at most two maximal intervals in which Cand = 𝑥 and 𝑥 is done. Every failed cleanup CAS by 𝐷 after reading such an 𝑥 is charged to one of these intervals.

A smaller-key done token already in Cand at 𝜎𝐷 that is never republished need not belong to S𝐷 : it can be removed once. Likewise, one owner tenure already current at 𝜎𝐷 is treated as an initial residue. These are the two constant terms in the charging bounds below. A tenure is encountered by 𝐷 when a step of 𝐷 reads its owner pair or an owner transition in that tenure makes 𝐷’s CAS/revalidation fail. For a CAS prepared from an empty-owner read, charge failure to the first tenure that makes that expected pair unreachable and to the interval containing the read, even if the delayed CAS executes in a later interval.

Proof sketch. By Lemma 5, no larger-key descriptor can become the candidate while the interval is guarded. If a largerkey owner is current at interval start, it is the one bypass; its release invalidates all earlier snapshots, and the guard prevents new ones. Otherwise every prepared larger-key installation expects the same empty generation, so one succeeds and its release invalidates the cohort. □

Lemma 9 (One larger-key bypass per guard). During one maximal 𝐷-guarded interval, the requester encounters at most one larger-key owner tenure, including a tenure already current when the interval begins.

Lemma 10 (One larger-key tail bypass). After the guard is opened and before 𝐷’s next minimum update, the process executing Lock(𝐷) incurs at most one larger-key obligation: an encountered owner tenure or one done-candidate episode that it reads.

Definition 6 (Guarded configuration). A configuration is 𝐷-guarded when Cand ≠ INF

and

Proof sketch. At an opening, 𝐷 is between iterations, between its minimum update and owner read, in one occupiedowner suffix, in one empty-owner suffix, or in the cleanup that caused the opening. These cases respectively expose no obligation, one owner path, one owner path, one mutually exclusive candidate-cleanup/owner path, or no further read before return. See Appendix B (“One larger-key tail bypass”) for the program-counter analysis. □

𝜌 (Cand) ≤ 𝑑.

A maximal interval of guarded configurations is a 𝐷-guarded interval. Lemma 5 (Guard establishment). Every Cand.MinUpdate(𝐷) establishes the 𝐷-guard unless 𝐷 is already done. While the guard holds, no larger-key descriptor can become the value of Cand. 5

Table 2. Explicit charging for a fixed descriptor 𝐷. Victim-visible event

Charge

Guard opening Larger-key tenure inside a guard Larger-key obligation in an unguarded tail Smaller-key owner tenure Victim/residual tenure

done smaller-key descriptor ℎ ≤ 2𝑚 + 1 guarded interval ≤ℎ+1

Owner/bypass subtotal

preceding opening

𝑂 (𝑚 + 1). See Appendix B (“Management-step charging”) for the complete case analysis. □

Bound

Theorem 2 (Finite charge-set service). For every execution 𝛼, ordered service descriptor 𝐷, and charge set S𝐷 (𝛼), after 𝜎𝐷 and until response the invoking process performs at most 𝑂 (|S𝐷 | + 1) management steps and 𝑂 ((|S𝐷 | + 1) (𝑇 + 1))

≤ℎ local shared-memory steps. If initialization and key assignment use 𝑂 (1) shared-memory steps, the same asymptotic bounds hold for the full invocation.

its descriptor

≤𝑚

constant term

≤2

last four rows

≤ 5𝑚 + 5

Proof. Table 2 and Lemma 15 give 𝑂 (|S𝐷 | + 1) management steps and service calls. Each service costs at most 𝑇 , and the terminal suffix costs 𝑂 (𝑇 + 1). □ 6.1

Increasing-ticket instantiation

Lemma 16 (FAI charge set). For SeniorLock, Seniors(𝐷) is a charge set for 𝐷. Its size is 𝛽𝐷 ≤ 𝜅𝐷 − 1.

Lemma 11 (Larger-key bypass compression). Before 𝐷 becomes done, it incurs at most 4𝑚 + 3 larger-key bypasses, independent of how many larger-key calls are invoked.

Proof sketch. Increasing FAI prevents a call invoked after 𝜏𝐷 from obtaining a smaller ticket. A smaller-ticket call that returned before 𝜏𝐷 cannot publish again, and every delayed installation other than the current tenure expects an obsolete owner generation. Thus every chargeable smaller-ticket call is a senior of 𝐷. All such calls overlap Lock(𝐷) at 𝜏𝐷 , giving the cardinality bound. See Appendix B (“FAI senior cover”) for the residue argument. □

Proof. Let ℎ be the number of guard openings. Lemma 7 gives ℎ ≤ 2𝑚 + 1, including the initial done-candidate residue. The ℎ + 1 guarded intervals and ℎ tails each contribute at most one larger-key bypass, for (ℎ + 1) + ℎ ≤ 4𝑚 + 3. □ Lemma 12 (Bounded encountered tenures). Before 𝐷 becomes done, its requesting process helps 𝑂 (𝑚+1) distinct owner tenures.

Theorem 3 (Retrospective wait-freedom). For every call Lock(𝐷) and every asynchronous schedule, Lock(𝐷) returns after 𝑂 (𝛽𝐷 +1) lock-management steps and 𝑂 ((𝛽𝐷 +1) (𝑇 +1)) local shared-memory steps.

Lemma 13 (One local service per tenure). For each encountered tenure, the requester follows a matching HelpOwner path at most once and invokes service at most once within that path (zero times if done is already true).

Proof. Apply Theorem 2 to the senior set from Lemma 16, whose size is 𝛽𝐷 . The service procedure is 𝑥 .run(), with the 𝑇 -step contract from Section 2; descriptor initialization and the FAI consume 𝑂 (1) additional shared-memory steps. □

Lemma 14 (Terminal suffix). After 𝐷 first becomes done and before its request responds, its invoking process performs only 𝑂 (1) management steps and at most one service call.

Corollary 1 (Point-contention adaptivity). Every call Lock(𝐷) returns in 𝑂 (𝜅𝐷 ) lock-management steps and 𝑂 (𝜅𝐷 (𝑇 + 1)) local shared-memory steps.

Including one initially resident done candidate, Table 2 totals at most 7𝑚 + 6 charges and hence 𝑂 (𝑚 + 1). Lemma 15 (Management-step charging). The requester of 𝐷 performs 𝑂 (𝑚 + 1) management steps before 𝐷 is done.

Proof. By construction, 𝛽𝐷 + 1 ≤ 𝜅𝐷 .

Proof sketch. Partition 𝐷’s precompletion iterations by their Assist outcome. An occupied-owner path or owner-CAS failure is charged to the tenure that changed the observed owner; one tenure receives at most a failed installation and one subsequent owner path, which ends or releases it. An INF read is charged to its intervening opening, once before republication. A done-candidate path is charged to its maximal done episode; sequential 𝐷 attempts cleanup at most once per episode. Table 2 bounds all three charge sets by

□

Corollary 2 (Independence from later arrivals). If no smaller-ticket call is active when 𝐷 obtains its ticket, then 𝐷 becomes done and Lock(𝐷) returns in 𝑂 (𝑇 + 1) local shared-memory steps, independent of calls invoked after the ticket step. Corollary 3 (Lock-resident space). SeniorLock uses three lock-resident abstract base objects. Every operation additionally allocates a descriptor and idempotence log. 6

6.2 An effectful retrospective universal construction

7

Let O be a deterministic sequential object with state space 𝑄, initial state 𝑞 0 , and total transition function

This section states counterexamples for one-time publication and unversioned ownership; Appendix D gives the complete schedules.

𝛿 (𝑞, 𝑜𝑝) = (𝑞 ′, 𝑟 ).

7.1

Ablations: republication and versioning

One-time publication is not wait-free

Store a private shared representation 𝑅 of the current state, initially representing 𝑞 0 , and associate one SeniorLock instance 𝐿 with 𝑅. For an invocation of 𝑜𝑝, allocate a fresh descriptor 𝐷 and install a thunk 𝑓𝐷,𝑜𝑝 that executes the sequential code for 𝑜𝑝 against 𝑅 and returns its response. Define the concurrent implementation by

Consider the variant in which a request executes minimum update only once and then repeatedly calls Assist.

Invoke O (𝑜𝑝) = 𝐿.Lock(𝐷, 𝑓𝐷,𝑜𝑝 ).

Proof sketch. A delayed smaller-ticket publication removes 𝐷’s sole candidate token. Thereafter, start one larger-ticket call 𝑌𝑖 per round immediately before 𝐷 reads the owner, let 𝐷 complete it, and return it before starting 𝑌𝑖+1 . The schedule repeats at point contention two. □

Proposition 1 (Republication). The one-time-publication variant has an infinite execution with maximum point contention two in which a victim takes infinitely many steps and never finishes.

All invocations on this instance of O use the same 𝐿. This is a universal construction in the standard sense [19]; we call the resulting object SeniorObj. SeniorObj never copies 𝑅 into an atomic state transition, unlike a classical Herlihy-style universal construction.

The same schedule explains why a descriptor-local selected bit does not replace republication. After a stale read marks an absent 𝐷 selected, the bit records an obligation but imposes no order on later owner installations. In SeniorLock the owner CAS is the selection event, and every still-pending caller restores the shared ticket guard first.

Theorem 4 (Effectful retrospective universality). Let O be any deterministic sequential object for which every invocation can be packaged as a concurrently idempotent thunk 𝑓𝐷,𝑜𝑝 satisfying the uniform, helper-count-independent 𝑇 -step service contract of Section 2. One SeniorLock instance implements O linearizably and retrospective wait-free. For an invocation with descriptor 𝐷 and seniority 𝛽𝐷 , its invoking process performs 𝑂 (𝛽𝐷 +1)

7.2

An untagged owner admits quadratic bypass

Let Untagged-SeniorLock be Algorithm 1 with Owner ∈ {⊥} ∪ {𝐷 } and CAS from an untagged null pointer. All other lines, including the done check, are unchanged.

lock-management steps and 𝑂 ((𝛽𝐷 +1) (𝑇 +1))

Proposition 2 (Stale-cohort lower bound). For every 𝑞 ≥ 1, Untagged-SeniorLock has an execution with point contention at most 2𝑞 + 1 in which one victim performs Ω(𝑞 2 ) lock-management steps.

local shared-memory steps, independent of operations invoked after 𝐷 obtains its ticket. Proof sketch. By Theorem 1, completed logical thunk intervals are nonoverlapping, lie within their invocations, and respect real time. Concurrent idempotence replaces every interval’s physical runs by one run of the corresponding sequential operation, so interval order is a legal linearization of O with the recorded responses. Done pending calls can be completed with those responses; an unfinished tenure cannot be followed by a later logical interval, so all other pending calls can be omitted. Each target operation is one Lock(𝐷, 𝑓𝐷,𝑜𝑝 ) call, and Theorem 3 gives the claimed bounds with the same ticket, senior set, and 𝑇 . See Appendix C for the full safety and completion argument. □

Proof sketch. Use 𝑞 smaller-ticket calls to open the guard in 𝑞 phases and 𝑞 larger-ticket helpers to prepare an installation cohort before each republication of 𝐷. Without a generation, all remaining stale CAS operations install the same completed descriptor in turn. Phase 𝑖 contributes 𝑞 − 𝑖 + 1 installations, so the victim encounters 𝑞(𝑞 + 1) 𝑞 + (𝑞 − 1) + · · · + 1 = 2 tenures at point contention at most 2𝑞 + 1. □ Algorithm-specific tightness. For SeniorLock, let 𝑏 senior calls publish one at a time and schedule 𝐷 to run each 𝑇 -step thunk before its own. Then 𝛽𝐷 = 𝑏 and 𝐷 performs (𝑏 + 1)𝑇 local thunk steps, showing that the service-work term is asymptotically tight for SeniorLock.

The logging transformation of Ben-David, Blelloch, and Wei supplies concurrently idempotent thunks for ABA-free code whose shared accesses use the transformed primitives [12]; whenever the transformed operation has a uniform 𝑇 bound, it instantiates Theorem 4. Universality concerns operation semantics. Total space includes the target representation, live descriptors, and idempotence logs; Corollary 3 counts the lock-resident objects.

8

Implementation model and limitations

The theorem treats MinUpdate, FAI, and tagged CAS as linearizable base-object steps and assumes the representation conditions below. 7

Primitive and hardware. Arm LDUMIN, RISC-V AMOMIN, and CUDA atomicMin expose integer minimum RMWs on supported targets [5, 24, 26]. The C++26 interface may use a CAS loop [17], but Proposition 3 shows that substitution is not wait-free. The 𝑁 + 1-register CAS upper bound classifies register count, not retrospective running time.

9.1

Why the direct CAS loop is insufficient

The sequential effect of MinUpdate can be reproduced by repeatedly reading 𝑐 and returning if 𝑐 ≤ 𝑥. Otherwise it attempts CAS(𝑐, 𝑥) and retries after failure. The resulting operation is not waitfree.

Representation and reclamation. The abstract candidate is the lexicographic token (𝐷.ticket, 𝐷.id), equivalently an integer ticket plus an immutable ticket-to-descriptor registry. For at most 𝑀 calls, tickets index an 𝑂 (𝑀) registry and the owner pair uses 2⌈log2 (𝑀 + 1)⌉ bits. The unboundedexecution theorem assumes nonwrapping tickets and generations; bounded concurrent timestamps address bounded key spaces under unbounded arrivals [14, 21]. A delayed helper can retain a descriptor after both objects drop it, so longlived reuse needs reclamation metadata, for which hazard pointers [23] are one standard mechanism. Total memory also includes the registry, descriptors, thunk logs, and any reclamation metadata excluded by Corollary 3.

Proposition 3 (CAS-loop starvation). After replacing MinUpdate by this retry loop, Algorithm 1 has an execution with 𝛽𝐷 = 0 and maximum point contention two in which one invocation by 𝐷 takes infinitely many steps without finishing its first minimum update. Proof. In round 𝑖, let 𝐷 read a larger-ticket candidate 𝑌𝑖 and pause before CAS(𝑌𝑖 , 𝐷). Complete 𝑌𝑖 , including its exact reset of the candidate to INF; the CAS by 𝐷 then fails. Return 𝑌𝑖 , start a fresh larger-ticket call 𝑌𝑖+1 , let it publish, and repeat. Only 𝐷 and the current 𝑌𝑖 are active. All 𝑌𝑖 obtain their tickets after 𝐷, so 𝛽𝐷 = 0, but the retry loop of 𝐷 never returns. □

Memory ordering. In a release/acquire model, descriptors and done are release-published and acquire-read; owner installation is acquire-release and cleanup is release. Generation changes alone do not publish thunk effects.

Thus direct retry-loop substitution does not preserve waitfreedom. The next theorem gives a space lower bound for any wait-free black-box implementation.

Limits. The interface serializes one always-executed thunk and excludes multi-lock acquisition, abort, nesting, strict FCFS order, and physical ownership intervals; tickets order only published candidates.

To attribute the separation to minimum update, the reduction uses static locally finite keys instead of SeniorLock’s fetchand-increment object. For process 𝑝’s 𝑘th operation, fix the key

9

9.2

𝜌 (𝑝, 𝑘) = 𝜋 (𝑝, 𝑘) =

A conditional-RMW space separation

Because the time bound counts MinUpdate as one base step, this section characterizes the base-location cost of implementing resettable min-CAS from conditional RMW registers. A resettable min-CAS register stores either INF or a uniquely keyed token and supports Read(),

Locally finite keys

(𝑝 + 𝑘) (𝑝 + 𝑘 + 1) + 𝑘, 2

the computable Cantor injection; each identity (𝑝, 𝑘) is used once. For an operation 𝑋 , define 𝐿𝑋 = {𝑌 : 𝜌 (𝑌 ) < 𝜌 (𝑋 )}. This set contains future as well as present operations, but is finite: |𝐿𝑋 | ≤ 𝜌 (𝑋 ).

CAS(𝑥, 𝑦),

Corollary 4 (Locally finite keys). In an ordered service instance using the static keys above, operation 𝑋 finishes after

MinUpdate(𝑥) : 𝐶 ← min(𝐶, 𝑥).

𝑂 (|𝐿𝑋 | + 1)

Algorithm 1 uses CAS only for exact reset CAS(𝑥, INF). For fixed input 𝑥, MinUpdate(𝑥) changes every state larger than 𝑥. In contrast, a conditional RMW has, for fixed input, only one current value on which it changes the register. Fich, Hendler, and Shavit call a register supporting reads, writes, and such operations a read-write-conditional register; CAS is the canonical example [16]. Their model permits unbounded register values, as does this section. By black-box implementation we mean a standalone linearizable object: clients use only its interface, and its internal base registers are disjoint from client registers.

management steps and 𝑂 ((|𝐿𝑋 | + 1) (𝑇 + 1)) local sharedmemory steps of its invoking process. Proof. The set 𝐿𝑋 is a charge set by Definition 5, including smaller-key operations that arrive after 𝑋 . Apply Theorem 2. □ The FAI instance restricts the relevant smaller-key set to seniors. Static keys give up that adaptivity but retain waitfreedom. 8

Algorithm 2 A long-lived FAI counter from resettable minCAS. 1: procedure FAI 2: 𝑘𝑝 ← 𝑘𝑝 + 1; 𝑋 ← (𝜌 (𝑝, 𝑘𝑝 ), 𝑝, 𝑘𝑝 ) 3: while ¬Done(𝑋 ) do 4: Cand.MinUpdate(𝑋 ) 5: Assist 6: return Reply.Read() [𝑝].result

Proof sketch. The successful reply CAS for (𝑝, 𝑘) linearizes the operation and returns its owner generation. The sequencing invariant prevents a later invocation from making (𝑝, 𝑘) appear done or overwriting its result before response. Successive tenures therefore return 0, 1, 2, . . . in real-timerespecting order. Completion is constant-time by Lemma 17; locally finite keys and Corollary 4 give wait-freedom. □ 9.4

Fich–Hendler–Shavit Theorem 3.6 states that an 𝑁 -process wait-free implementation of a long-lived object in Visible(𝑁 ) from read-write-conditional registers uses at least ⌈𝑁 /2⌉ registers [16]. Their visible-write definition explicitly includes long-lived counters.

7: function Done(𝑋 = (_, 𝑝, 𝑘)) 8: 𝐴 ← Reply.Read() 9: return 𝐴[𝑝].seq ≥ 𝑘 10: procedure Complete(𝑋 = (_, 𝑝, 𝑘), 𝑔) 11: repeat 12: 𝐴 ← Reply.Read() 13: if 𝐴[𝑝].seq ≥ 𝑘 then 14: return 15: 16:

9.3

The separation

Theorem 6 (Conditional-RMW space separation). Let 𝑠 (𝑁 ) be the number of shared base locations used by a wait-free linearizable long-lived black-box resettable min-CAS implementation for 𝑁 processes using only read, write, and conditional RMW registers. Count read/write-only locations as conditional registers with unused operations. Then   𝑁 𝑠 (𝑁 ) + 2 ≥ , 2   𝑁 − 2 = Ω(𝑁 ). 𝑠 (𝑁 ) ≥ 2

𝐴′ ← 𝐴 with 𝐴′ [𝑝] ← (𝑘, 𝑔) until Reply.CAS(𝐴, 𝐴′ ) succeeds

A long-lived counter from three registers

Fix 𝑁 processes. In addition to one resettable min-CAS register Cand, use a tagged CAS register Owner, initially (⊥, 0), and one CAS register Reply. The latter stores the entire vector Reply [𝑝] = (seq, result) as one unbounded value; initially every sequence number is zero. Process 𝑝 keeps a private invocation number 𝑘𝑝 , initially zero. Process identifiers are never reused and each process has at most one outstanding FAI. Inductively, immediately before its 𝑘th invocation, Reply [𝑝].seq = 𝑘 − 1; operation 𝑘 +1 is not announced before operation 𝑘 responds. The Assist and HelpOwner procedures are those in Algorithm 1, after replacing every test of 𝑥 .done by Done(𝑥) and the call 𝑥 .run() by Complete(𝑥, 𝑔). Thus the counter client contains no FAI object.

The result holds even when every register stores an unbounded value. Proof. Substitution in Algorithm 2 gives a wait-free longlived counter using 𝑠 (𝑁 ) + 2 registers. It uses the same 𝑁 client processes and introduces no helper process. The visible-object lower bound of Fich, Hendler, and Shavit requires at least ⌈𝑁 /2⌉ read-write-conditional registers even with unbounded values [16]. □ 9.5

A matching CAS upper bound

For processes 0, . . . , 𝑁 −1, each with at most one outstanding operation, use 𝑁 single-writer registers Ann[𝑝], initially ⊥, and one CAS register

Lemma 17 (Bounded completion). Every call to Complete(𝑋, 𝑔) takes 𝑂 (1) shared-memory steps.

State = (𝐶, Reply [0..𝑁 − 1]), initially (INF, [(0, ⊥)] 𝑁 ). All registers hold unbounded values. Process 𝑝’s 𝑘th operation has key

Proof. No different tenure begins while (𝑋, 𝑔) is current. Every delayed old helper expects a reply vector preceding the monotone update that enabled its tenure’s release, so its CAS fails. Thus a CAS failure for unfinished 𝑋 means another helper completed 𝑋 ; one reread returns. Every successful reply CAS advances exactly one sequence field from 𝑘 − 1 to 𝑘, so the full vector never recurs. □

𝜌 𝑁 (𝑝, 𝑘) = 𝑁 (𝑘 − 1) + 𝑝. For this subsection, write 𝐿𝑋𝑁 = {𝑌 : 𝜌 𝑁 (𝑌 ) < 𝜌 𝑁 (𝑋 )}. Process 𝑝 forms 𝑋 = (𝑝, 𝑘, 𝜌 𝑁 (𝑝, 𝑘), 𝑜𝑝). It writes the immutable token 𝑋 to Ann[𝑝]. Each help attempt collects all announcements, reads State, selects the minimum-key entry one sequence beyond its recorded reply, applies its transition to 𝐶, and attempts one state CAS. The caller repeats until its reply appears; pseudocode and proof appear in Appendix E.

Theorem 5 (Counter client). One resettable min-CAS register and two CAS registers suffice for a deterministic wait-free linearizable long-lived FAI counter. The call with token 𝑋 takes 𝑂 (𝜌 (𝑋 ) + 1) abstract shared-memory steps. 9

Theorem 7 (Linear CAS upper bound). The construction is a wait-free linearizable long-lived resettable min-CAS from 𝑁 read-write registers and one CAS register; operation 𝑋 performs
𝑂 𝑁 (|𝐿𝑋𝑁 | + 𝑁 + 1)

reachable locations, and Owner, Reply contribute two. This contradicts Bédin et al. [10]. □ Resettable min-CAS is a restricted generalized compareand-swap (GCAS):

shared-memory steps.

MinUpdate(𝑥) = GCAS(>, 𝑥, 𝑥),

Proof sketch. Each successful State CAS applies one eligible announcement, advances one reply sequence, prevents duplicate application and logical ABA, and is the linearization point. After 𝑋 publishes, at most 𝑁 − 1 already-running collects omit it; every fresh collect that finds 𝑋 pending selects 𝑋 or an operation in 𝐿𝑋𝑁 . Thus distinct successful CAS operations cause at most |𝐿𝑋𝑁 | + 𝑁 retries, each costing 𝑁 + 𝑂 (1) accesses, before one final read observes completion. □

CAS(𝑎, 𝑏) = GCAS(=, 𝑎, 𝑏). Prior GCAS work uses FAI, repeated minimum-ticket announcement, and equality replacement to obtain an analogous 𝑂 (𝛽𝑜 +1) bound for atomic state transitions [18, Appendix B.2, Theorem B.2.15]. Its state CAS invalidates stale snapshots; SeniorLock uses an owner generation to preserve the bound across a multi-step thunk. For fixed 𝑁 , our result characterizes unbounded-register count. Adaptive infinitepopulation space and a CAS-derived SeniorLock time bound remain open.

Corollary 5 (Asymptotically tight fixed-population classification). Let 𝑠 min (𝑁 ) be the minimum register count for a wait-free linearizable long-lived resettable min-CAS from read-write-conditional registers with unbounded values. Then   𝑁 − 2 ≤ 𝑠 min (𝑁 ) ≤ 𝑁 + 1, 𝑠 min (𝑁 ) = Θ(𝑁 ). 2

10

Proof. Combine Theorems 6 and 7; a read-write register is a permitted special case of a read-write-conditional register. □ In the fixed-population black-box model with unbounded values, resettable min-CAS has Θ(𝑁 ) base-location complexity over read-write-conditional registers. This metric counts base locations rather than bits; CAS remains universal. 9.6

Comparison and related work

Generalized compare-and-swap provides the analogous fixed-senior bound for pure state transitions. We formulate this bound as an object-level property and extend it to bounded, concurrently idempotent multi-step thunks; Section 9 compares the primitive requirements. The cited adaptive universal constructions give point-contention bounds that may include operations arriving after key assignment [2, 15], and therefore do not imply Definition 3. Large-object constructions instead address state-copying costs [4]. Our separation uses the lower bounds of Fich, Hendler, and Shavit and of Bédin et al. [10, 16]. Unlike monotone registers and general reset transformations, the candidate combines minimum update with exact reset [3, 6]. SeniorLock adds a ticket guard and versioned owner to descriptor helping and idempotence [9, 12, 27]. Randomized wait-free locks give probabilistic contentiondependent bounds [1, 11]; SeniorLock gives a deterministic fixed-senior bound for one always-executed thunk.

Infinite arrivals and GCAS

The same client yields a consequence in the infinite-arrival model [22, 25]. Let process identifiers range over N, retain 𝜌 (𝑝, 𝑘) = 𝜋 (𝑝, 𝑘), and encode Reply as a finite sparse map in one flat, by-value unbounded CAS register. Map sequence entries increase monotonically and are never removed; tokens are the values (𝜌, 𝑝, 𝑘), not references to retained descriptors. Every finite execution stores a finite map, while the number of reachable locations remains three at the abstract level. Following Bédin et al., quiescent complexity after 𝑛 operations is the maximum number of locations reachable when exactly those operations have completed and none is pending [10]. It counts locations, not the bit length of one location’s value.

11

Conclusion

SeniorLock is a deterministic helpable thunk lock whose worst-case invoking-process bound is independent of calls invoked after its ticket step. A restored ticket guard and versioned owner give 𝑂 (𝛽𝐷 + 1) management steps under every asynchronous schedule. We formulate this guarantee as retrospective wait-freedom, a property defined for arbitrary concurrent objects. For deterministic sequential objects satisfying the uniform 𝑇 -step thunk contract, one SeniorLock instance gives an effectful retrospective universal construction with 𝑂 ((𝛽𝐷 + 1) (𝑇 + 1)) local shared-memory steps per operation. In the fixed-population unbounded-value blackbox model, resettable min-CAS has tight Θ(𝑁 ) read-writeconditional-register complexity. FAI supplies the increasing

Corollary 6 (Infinite-arrival separation). In the infinitearrival model, no wait-free linearizable implementation of a resettable min-CAS register from read, write, and CAS has constant quiescent complexity. Proof. Substitution into the sparse-map client gives a read/write/CAS counter with constant quiescent complexity: at outer quiescence every inner call has returned, the assumed implementation contributes a constant number of 10

tickets used to identify seniors, and the infinite-arrival result rules out constant read/write/CAS quiescent location complexity.

Release after completion. The only release is the final CAS in HelpOwner. It is executed only after observing the monotone done predicate, so tenure (𝑥, 𝑔) cannot end before 𝑥 is done.

Acknowledgments

Candidate responsibility. The cleanup CAS in Assist is reached only after reading 𝑥 done, and the reset in HelpOwner is likewise after service and a done test. Hence neither clears an active 𝑥. Minimum update only decreases the stored key, and an exact-token reset of a stale larger-key candidate cannot erase a smaller-key replacement.

Generative AI tools assisted only with language editing and formatting. The authors reviewed all output and take full responsibility for this paper. This appendix uses the notation, definitions, and algorithm numbers introduced above and gives the full proof details that Sections 2–9 abbreviate.

A

Safety details

A.1

Critical interleavings

One tenure per descriptor. Suppose 𝑥 is installed in generation 𝑔. Its tenure ends only after 𝑥 is done and advances the generation. An installation prepared before release expects a generation at most 𝑔 and fails afterward. An installation prepared afterward reads the owner before testing done and therefore observes the monotone true predicate instead of attempting CAS.

Stale candidate ownership. Let a helper read Cand = 𝑥, then let a descriptor 𝑦 with a smaller key replace 𝑥 before the owner CAS. The helper may still install 𝑥 in the same empty generation. Its cleanup compares the exact token 𝑥 and therefore cannot remove 𝑦; after 𝑥 completes and releases, 𝑦 remains the next obligation.

Detailed proof of safety. Every run starts after validation of an owner tenure. If that tenure ends before the helper’s next thunk step, release after completion implies that the descriptor is already done; concurrent idempotence makes the resumed run noneffectual. Thus every effectual thunk step belongs to the descriptor whose tenure was validated. A distinct tenure cannot begin until the previous descriptor has a finished run. Concurrent idempotence gives each descriptor one logical execution interval ending at its first finished run and makes redundant or later runs noneffectual, so distinct logical intervals do not overlap. A descriptor is not published before its lock invocation and its caller returns only after observing done. Its logical execution interval therefore lies within its call. Order completed calls by owner generation. If one call returns before another is invoked, the former logical interval has ended; the latter cannot begin effectual work before a later tenure. Generation order consequently respects real-time precedence and yields a legal serial thunk execution. □

Done-test/generation handshake. The installation path orders its steps as an empty-owner read in generation 𝑔, a false done read, and then owner CAS. If 𝑥 becomes done between the latter two steps, some tenure of 𝑥 must start and release before the owner is empty again, advancing the generation. The delayed CAS expecting 𝑔 fails. Moving the done read before the owner read would instead allow installation of a completed descriptor in the new empty generation. Physical late run. A helper can validate (𝑥, 𝑔) and pause while another helper completes 𝑥, releases 𝑔, and installs a later owner. No finite reread sequence closes the final instruction window before 𝑥 .run(). The observational concurrentidempotence contract makes every such post-completion physical step removable under every continuation. Reset before release and stale self-publication. After 𝑥 is done, cleanup may reset Cand = 𝑥 and pause before owner release. A new candidate token different from 𝑥 survives because all later cleanup compares against 𝑥, but it cannot install until the occupied owner is released; this is the unguarded tail. Separately, 𝑥’s requester can have one loop test already read as active when another helper finishes 𝑥. It may publish one stale done token, then observe done at the next loop test; it cannot publish a second. A.2

B

Finite charge-set progress details

Fix an execution 𝛼, victim 𝐷, key 𝑑 = 𝜌 (𝐷), and a charge set S𝐷 (𝛼). All events below occur in 𝐷’s pending suffix (which is infinite if 𝐷 never finishes), and 𝑚 = |S𝐷 (𝛼)|. Guard establishment. Minimum update leaves 𝐷 or a smaller-key descriptor in Cand. Larger-key updates preserve that value, and candidate CAS operations only replace an exact token by INF. Smaller-key chain compression. Every effective smallerkey publication strictly decreases the candidate key. The charge-set definition assigns its descriptor to S𝐷 , so a firsttime strict chain has length at most 𝑚. A repeated publication is already present or dominated by a smaller-key token and does not extend the chain. No point in the chain exposes a

Safety invariants

Generation uniqueness. All installations CAS the complete owner pair. Only one CAS can change (⊥, 𝑔), and the only transition back to an empty owner writes (⊥, 𝑔 + 1). Thus at most one descriptor is installed in generation 𝑔, and every delayed installation expecting (⊥, 𝑔) fails after release. 11

larger-key token, so the chain does not create another stale installation cohort.

publication starts the next guard; a different owner 𝐵 then current at guard start is that guard’s one bypass.

Opening the guard. The guard can be destroyed only by a successful Cand.CAS(𝑥, INF) after 𝑥 is done. If 𝑥 ≠ 𝐷, guardedness gives 𝜌 (𝑥) < 𝑑. Except for the done token already resident when 𝐷 receives its key, 𝑥 was initially resident and active or was published later, so the charge-set definition places it in S𝐷 . After completion, one successful cleanup CAS in Assist or HelpOwner removes 𝑥. Its requester can have at most one loop test already read as active and can therefore create at most one stale post-completion publication. Thus each charged descriptor opens the guard at most twice.

Larger-key bypass compression. Let ℎ be the number of openings before 𝐷 is done. The opening argument gives ℎ ≤ 2𝑚 + 1, including the initial done-candidate residue. There are at most ℎ + 1 guarded intervals and ℎ tails, each with one larger-key bypass, for at most (ℎ + 1) + ℎ ≤ 4𝑚 + 3 larger-key obligations visible to 𝐷. Tenures and local service. Every descriptor in S𝐷 owns at most one tenure, as does 𝐷. Every smaller-key tenure beginning after key assignment belongs to S𝐷 . Adding 𝑚 smaller-key tenures, at most 4𝑚 + 3 larger-key bypasses, 𝐷, and one initial owner yields at most 5𝑚 + 5 victim-visible charges. If owner revalidation fails, that tenure has ended permanently. If it succeeds, bounded service returns with done true and the helper attempts both cleanup CAS operations before its next loop, so the requester services a tenure at most once.

Done-candidate episodes. If 𝑥 is in Cand when it becomes done, that event begins the first episode. After removal, only the one stale requester iteration just described can reinsert it. Every failed cleanup CAS following a read of done 𝑥 is charged to one of these two maximal episodes. One larger-key bypass per guard. No larger-key descriptor becomes candidate while the guard holds. Every such installation was prepared from a candidate read before the guarded interval. If a larger-key owner is already installed, it is the one bypass. Otherwise all prepared installations that can still succeed expect the same empty generation 𝑔. Generation uniqueness permits one success; release advances to 𝑔+1, and the guard prevents preparation of another larger-key installation. The same argument applies after a smaller-key owner present at interval start: its reset either ends the interval or leaves a guarded candidate.

Terminal suffix. After 𝐷 becomes done, its sequential requester either observes done at its next loop test or finishes the one iteration whose test was already read. That suffix has constant management work and at most one service call. Management-step charging. Partition every precompletion iteration by its Assist outcome. If it reads an occupied owner, its revalidation either fails because the tenure ended or succeeds and bounded service plus cleanup ends that tenure before the requester can encounter it again. If an owner-installation CAS fails after an empty read, charge the iteration to the tenure that first changed that exact empty generation. The same tenure can receive this failed-installation charge and at most one subsequent occupied-owner charge, so tenure multiplicity is at most two. After 𝐷 publishes, a read of INF requires an intervening exact reset and is charged to that opening. The requester performs only one candidate read in the iteration and republishes at the next loop head, so an opening receives at most one such charge. If 𝐷 reads a done candidate, charge the iteration to that maximal done-candidate episode. Whether cleanup succeeds or fails because the candidate changes, that episode ends before 𝐷 can issue another cleanup, so its multiplicity is one. Smaller-key descriptors contribute at most 2𝑚 episodes and the initial token one. A larger-key done token read after an opening is the one tail obligation already charged to that opening, even if its tenure completed entirely while 𝐷 was paused. These cases exhaust the branches after Assist’s owner read. There are at most 2𝑚 + 1 openings and 5𝑚 + 5 owner/bypass charges, hence at most 7𝑚 + 6 charge objects. Each charge object receives only 𝑂 (1) iterations.

One larger-key tail bypass. Consider 𝐷’s program counter when the opening occurs. If 𝐷 is between iterations, its next arbitration access is minimum update, so the tail exposes nothing. If the opening occurs after 𝐷’s minimum update but before its owner read, the remaining iteration follows at most the one owner path selected by that read. If it previously read an occupied owner, only that one HelpOwner suffix remains; success services that tenure and failed revalidation returns immediately. If it read an empty owner in generation 𝑔, the remaining Assist suffix reads one candidate. It either returns on INF, performs one cleanup after a done read, or makes one owner CAS after an active read and follows at most that installed owner. These branches are exclusive. If 𝐷 itself opened the guard in cleanup, both Assist’s done branch and HelpOwner’s release suffix return without another candidate/owner read. Thus the suffix exposes exactly zero or one larger-key obligation. Arbitrarily many larger-key calls may finish while 𝐷 is paused; only the single owner or done-candidate state observed when 𝐷 resumes matters. If tenure 𝐻 first invalidates an empty pair read in the tail, 𝐻 remains the tail charge even when the CAS executes after a smaller-key 12

Together with the constant terminal suffix, this proves the management and service bounds.

If the first 𝑖 − 1 intervals implement the legal prefix ending in 𝑞𝑖 −1 , then no other logical target operation overlaps interval 𝑖. The single effectual run in that interval consequently implements 𝛿 (𝑞𝑖 −1, 𝑜𝑝𝑖 ) = (𝑞𝑖 , 𝑟𝑖 ) and records 𝑟𝑖 before publishing done. Thus interval order yields a legal sequential history of O with the responses returned by all retained invocations. Since the order also respects real time, it is a linearization. It remains to justify discarding the pending descriptors that are not done. A descriptor that has not begun an owner tenure has executed no target-state step. If an unfinished descriptor has begun a tenure, release after completion prevents that tenure from ending, so no later logical target interval can begin. Its partial physical execution is therefore a suffix after every retained operation; omitting the pending invocation from the completed abstract history does not change the legal sequential prefix above. If the descriptor later finishes, concurrent idempotence makes its full logical run one additional sequential transition, so the argument is also closed under continuations. For progress, a target-object invocation performs exactly the corresponding Lock(𝐷, 𝑓𝐷,𝑜𝑝 ) call. The main retrospective wait-freedom theorem applies with the same descriptor ticket, seniors, and𝑇 -step service contract, yielding 𝑂 (𝛽𝐷 +1) management steps and 𝑂 ((𝛽𝐷 + 1) (𝑇 + 1)) total local sharedmemory steps. Every target invocation after 𝐷’s ticket step obtains a larger FAI ticket, so it cannot enter 𝐷’s senior set or affect either bound. □

FAI senior cover. For SeniorLock, set 𝜌 (𝑥) = 𝑥 .ticket and 𝜎𝐷 = 𝜏𝐷 . Every unfinished smaller-ticket call at 𝜏𝐷 is a senior. Increasing FAI prevents a later smaller ticket; a returned call cannot publish again, and any delayed installation not already current at 𝜏𝐷 expects an obsolete generation. The one current owner tenure is the allowed initial residue. Thus Seniors(𝐷) is a charge set and has size 𝛽𝐷 ≤ 𝜅𝐷 − 1.

C

Effectful retrospective universality

We give the full safety, completion, and progress argument for the effectful retrospective universality theorem. Let O be a deterministic sequential object with state space 𝑄, initial state 𝑞 0 , and transition function 𝛿 (𝑞, 𝑜𝑝) = (𝑞 ′, 𝑟 ). Its state has a private shared representation 𝑅, and every operation is packaged as a fresh concurrently idempotent thunk satisfying the uniform, helper-count-independent 𝑇 -step service contract. All target-object invocations use one SeniorLock instance. Theorem 8 (Effectful retrospective universality, restated). The wrapper Invoke O (𝑜𝑝) = 𝐿.Lock(𝐷, 𝑓𝐷,𝑜𝑝 ) is linearizable and retrospective wait-free. An invocation with seniority 𝛽𝐷 performs 𝑂 (𝛽𝐷 + 1) lock-management steps and 𝑂 ((𝛽𝐷 + 1) (𝑇 + 1)) local shared-memory steps, independently of operations invoked after its ticket step.

D

Ablation schedules

Proof of the Republication proposition. Let a smaller-ticket call 𝐸 obtain a ticket and pause before publication. Victim 𝐷 obtains the next ticket, publishes once, and pauses. Publish 𝐸, let it become owner, and schedule 𝐷 to complete it. The exact reset removes 𝐸 while 𝐷’s prior token is already gone. For round 𝑖, start a larger-ticket call 𝑌𝑖 , publish and install it just before 𝐷 reads the owner, and let 𝐷 complete and release it. Return 𝑌𝑖 before starting 𝑌𝑖+1 . The variant never republishes 𝐷, so the schedule repeats forever with only 𝐷 and one other call active. □

Proof. Fix an arbitrary target-object history. Complete every pending invocation whose descriptor is done by appending its recorded response, and discard every other pending invocation. Call the resulting completed invocations retained. By lock safety, each retained descriptor has a logical thunk execution interval between its invocation and response. Logical intervals of distinct descriptors do not overlap, so they are totally ordered by time, and this order respects the realtime precedence of nonoverlapping invocations. For each interval, concurrent idempotence supplies a subsequence of the physical thunk steps that is indistinguishable under every continuation from one run of that thunk, while preserving all steps belonging to other descriptors. Because 𝑅 is private to the target implementation, replacing the physical runs, interval by interval, therefore leaves an execution in which exactly one copy of each retained sequential operation accesses the target state. Induct on the logical-interval order. The first retained thunk starts from the representation of 𝑞 0 and, by its sequential specification, changes it to 𝑞 1 and records response 𝑟 1 , where

Proof of the Stale-cohort lower bound. Use victim 𝐷, smallerticket calls 𝐸 1, . . . , 𝐸𝑞 , and larger-ticket helpers 𝐻 1, . . . , 𝐻𝑞 . All smaller-ticket calls obtain tickets and pause before 𝐷 receives its ticket. In phase 𝑖, publish one remaining 𝐸𝑖 , make it owner, and let 𝐷 complete it, opening the guard. Let ℎ𝑖 be the minimum remaining helper. Run every remaining helper through an empty-owner read, a read of Cand = ℎ𝑖 , and a false done read, pausing each before owner CAS. Then republish 𝐷. Resume the paused CAS operations one by one. The first installs ℎ𝑖 ; 𝐷 completes and releases it. With an untagged empty owner, every remaining stale CAS can reinstall the

𝛿 (𝑞 0, 𝑜𝑝 1 ) = (𝑞 1, 𝑟 1 ). 13

Algorithm 3 𝑁 +1-register resettable min-CAS upper bound.

same done descriptor and be cleared by 𝐷. Phase 𝑖 therefore contributes 𝑞 − 𝑖 + 1 tenures. Summing gives

1: procedure Invoke(𝑜𝑝)

𝑞(𝑞 + 1) 𝑞 + (𝑞 − 1) + · · · + 1 = . 2 There are at most 2𝑞 + 1 active calls. A generation permits only the first CAS in each phase and invalidates the rest on release. □

2: 3: 4: 5: 6: 7:

E

8: 9:

Primitive-separation details

This section gives the omitted proofs and pseudocode for the primitive-separation results.

10: 11:

Constant-time counter completion. While tenure (𝑋, 𝑔) is current, no distinct valid tenure begins. A delayed helper from an earlier tenure expects a reply vector preceding the successful update required before that tenure’s release. Reply sequence fields only increase, so that expected vector never returns. While 𝑋 is unfinished, every successful reply CAS therefore completes 𝑋 . If a helper’s CAS fails, one reread observes done. Each success strictly advances one process sequence from 𝑘 − 1 to 𝑘.

12: 13: 14: 15:

1}

𝑘𝑝 ← 𝑘𝑝 + 1; 𝑋 ← (𝑝, 𝑘𝑝 , 𝑁 (𝑘𝑝 − 1) + 𝑝, 𝑜𝑝) Ann[𝑝].Write(𝑋 ) loop 𝑆 ← State.Read() if 𝑆.Reply [𝑝].seq ≥ 𝑘𝑝 then return 𝑆.Reply [𝑝].result for 𝑞 ← 0 to 𝑁 − 1 do 𝐴[𝑞] ← Ann[𝑞].Read() 𝑆 ← State.Read() E ← {𝐴[𝑞] ≠ ⊥ : 𝐴[𝑞].seq = 𝑆.Reply [𝑞].seq +

if E ≠ ∅ then 𝑌 ← arg min𝑍 ∈ E 𝜌 𝑁 (𝑍 ) (𝐶 ′, 𝑣) ← Apply(𝑆.𝐶, 𝑌 .𝑜𝑝) 𝑆′ ← 𝑆 with 𝑆 ′ .𝐶 ′ 𝑆 .Reply [𝑌 .𝑝] ← (𝑌 .seq, 𝑣) 16: State.CAS(𝑆, 𝑆 ′ )

←

𝐶 ′ and

The packed state is (𝐶, Reply [0..𝑁 − 1]). Each successful state CAS applies one eligible operation to the preceding 𝐶 and advances its owner’s reply sequence by exactly one. It is the operation’s linearization point. Sequence monotonicity prevents duplicate application and logical ABA of the unbounded packed state even when 𝐶 cycles. A stale announcement is filtered if complete at the following state read; if it completes afterward, the state changes and the stale CAS fails. Thus the successful CAS chain is a legal sequential history and every completed operation linearizes between publication and response. Fix pending 𝑋 and its announcement write 𝑊𝑋 . At 𝑊𝑋 , each other sequential process has at most one help call that already read Ann[𝑋 .𝑝]. Each makes one CAS attempt, so at most 𝑁 − 1 successful transitions after 𝑊𝑋 can arise from 𝑋 -blind collects. Every new collect sees 𝑋 until completion. If its state read still sees 𝑋 pending, minimum-key choice selects 𝑋 or one of the finitely many operations in 𝐿𝑋𝑁 . Every successful CAS completes a distinct identity. Each victim CAS failure is paired with a distinct successful transition between its state read and CAS. Therefore the requester performs 𝑂 (|𝐿𝑋𝑁 | + 𝑁 ) iterations while pending, followed by one reply read, each using 𝑁 + 𝑂 (1) accesses. Bounded sequence wraparound and pointer reclamation are outside this abstract theorem. □

Proof of the Counter client theorem. Processes have permanent identifiers and one outstanding call. Inductively, Reply [𝑝].seq = 𝑘 − 1 when call 𝑘 starts, and call 𝑘 + 1 is not announced before call 𝑘 responds. The first successful reply CAS writing (𝑘, 𝑔) for process 𝑝 linearizes 𝑋 = (𝜌 (𝑝, 𝑘), 𝑝, 𝑘). Generation uniqueness assigns one token to each tenure and release follows completion. Starting at generation zero, consecutive tenures complete one operation and return 0, 1, 2, . . .. If a caller returns before release, no later operation completes until that release advances the generation, preserving real time. The sequencing invariant prevents a later call from making (𝑝, 𝑘) appear done or replacing its result before response. The done predicate is monotone, completion costs 𝑂 (1), and the locally finite smaller-key set has size at most 𝜌 (𝑋 ); the finite charge-set theorem gives wait-freedom. □ Proof of the Conditional-RMW space-separation theorem. Let 𝑠 (𝑁 ) count the fixed set of all shared base locations, including read/write-only locations. Assume an 𝑠 (𝑁 )register wait-free linearizable long-lived resettable min-CAS implementation using read/write/conditional-RMW registers. Substitute it into the counter client and retain fresh owner and reply registers. Composition gives an 𝑁 -process wait-free long-lived counter using 𝑠 (𝑁 ) + 2 read-writeconditional registers. It introduces no helper process, so the process parameter remains 𝑁 . The Fich–Hendler–Shavit visible-object theorem requires ⌈𝑁 /2⌉ such registers, even with unbounded values. Hence 𝑠 (𝑁 ) ≥ ⌈𝑁 /2⌉ − 2. □

Infinite arrivals. With permanent identifiers in N, encode replies as one flat by-value sparse map in an unbounded register. Entries are monotone and never removed; operation tokens contain (𝜌, 𝑝, 𝑘) values rather than retained descriptor references. A constant-quiescent-complexity read/write/CAS implementation of resettable min-CAS would then compose with the two-register client state. At

Proof of the Linear CAS upper-bound theorem. 14

outer quiescence all nested calls have returned, so reachable locations are exactly the implementation’s constant quiescent set plus owner and reply. This contradicts the cited infinite-arrival counter impossibility.

[15] Panagiota Fatourou and Nikolaos D. Kallimanis. 2011. A HighlyEfficient Wait-Free Universal Construction. In Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’11). Association for Computing Machinery, New York, NY, USA, 325–334. doi:10.1145/1989493.1989549 [16] Faith E. Fich, Danny Hendler, and Nir Shavit. 2004. On the Inherent Weakness of Conditional Synchronization Primitives. In Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC ’04). Association for Computing Machinery, New York, NY, USA, 80–87. doi:10.1145/1011767.1011780 [17] Al Grant, Bronek Kozicki, and Tim Northover. 2024. Atomic Minimum/Maximum. ISO C++ Working Group Paper P0493R5. https: //wg21.link/P0493R5 [18] Vassos Hadzilacos, Myles Thiessen, and Sam Toueg. 2026. Generalized Compare-and-Swap and Space-Efficient Universal Constructions for the Infinite-Arrival Model. In Proceedings of the 2026 ACM Symposium on Principles of Distributed Computing (PODC ’26). Association for Computing Machinery, New York, NY, USA, 467–477. Full version: arXiv:2605.19237. doi:10.1145/3796701.3815968 [19] Maurice Herlihy. 1991. Wait-Free Synchronization. ACM Transactions on Programming Languages and Systems 13, 1 (1991), 124–149. doi:10. 1145/114005.102808 [20] Maurice P. Herlihy and Jeannette M. Wing. 1990. Linearizability: A Correctness Condition for Concurrent Objects. ACM Transactions on Programming Languages and Systems 12, 3 (1990), 463–492. doi:10. 1145/78969.78972 [21] Amos Israeli and Ming Li. 1993. Bounded Time-Stamps. Distributed Computing 6, 4 (1993), 205–209. doi:10.1007/BF02242708 [22] Michael Merritt and Gadi Taubenfeld. 2013. Computing with Infinitely Many Processes. Information and Computation 233 (2013), 12–31. doi:10.1016/j.ic.2013.11.007 [23] Maged M. Michael. 2004. Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects. IEEE Transactions on Parallel and Distributed Systems 15, 6 (2004), 491–504. doi:10.1109/TPDS.2004.8 [24] NVIDIA Corporation. 2026. CUDA C++ Programming Guide: Atomic Functions. https://docs.nvidia.com/cuda/cuda-programming-guide/ 05-appendices/cpp-language-extensions.html [25] Matthieu Perrin, Achour Mostéfaoui, and Grégoire Bonin. 2020. Extending the Wait-Free Hierarchy to Multi-Threaded Systems. In Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing (PODC ’20). Association for Computing Machinery, New York, NY, USA, 21–30. doi:10.1145/3382734.3405723 [26] RISC-V International. 2024. The RISC-V Instruction Set Manual, Volume I: Unprivileged Architecture. https://docs.riscv.org/reference/ isa/v20240411/_attachments/riscv-unprivileged.pdf [27] John Turek, Dennis Shasha, and Sundeep Prakash. 1992. Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking. In Proceedings of the 11th ACM SIGACTSIGMOD-SIGART Symposium on Principles of Database Systems (PODS ’92). Association for Computing Machinery, New York, NY, USA, 212– 222. doi:10.1145/137097.137873

References [1] Kahbod Aeini, Dante Bencivenga, George Giakkoupis, and Philipp Woelfel. 2026. Simple and Efficient Randomized Wait-Free Locks. In Proceedings of the 2026 ACM Symposium on Principles of Distributed Computing (PODC ’26). Association for Computing Machinery, New York, NY, USA, 48–57. doi:10.1145/3796701.3815952 [2] Yehuda Afek, Dalia Dauber, and Dan Touitou. 1995. Wait-Free Made Fast. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC ’95). Association for Computing Machinery, New York, NY, USA, 538–547. doi:10.1145/225058.225271 [3] Zahra Aghazadeh, Wojciech M. Golab, and Philipp Woelfel. 2013. Brief Announcement: Resettable Objects and Efficient Memory Reclamation for Concurrent Algorithms. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC ’13). Association for Computing Machinery, New York, NY, USA, 322–324. doi:10.1145/ 2484239.2484286 [4] James H. Anderson and Mark Moir. 1999. Universal Constructions for Large Objects. IEEE Transactions on Parallel and Distributed Systems 10, 12 (1999), 1317–1332. doi:10.1109/71.819952 [5] Arm Limited. 2024. LDUMIN: Atomic Unsigned Minimum on Word or Doubleword in Memory. Arm A-profile A64 Instruction Set Architecture. https://developer.arm.com/documentation/ddi0602/202403/Base-Instructions/LDUMIN--LDUMINA--LDUMINAL-LDUMINL--Atomic-unsigned-minimum-on-word-or-doublewordin-memory[6] James Aspnes, Hagit Attiya, and Keren Censor-Hillel. 2012. Polylogarithmic Concurrent Data Structures from Monotone Circuits. J. ACM 59, 1 (2012), 2:1–2:24. doi:10.1145/2108242.2108244 [7] Hagit Attiya and Arie Fouren. 2003. Algorithms Adapting to Point Contention. J. ACM 50, 4 (2003), 444–468. doi:10.1145/792538.792541 [8] Hagit Attiya and Jennifer Welch. 2004. Distributed Computing: Fundamentals, Simulations, and Advanced Topics (second ed.). Wiley. [9] Greg Barnes. 1993. A Method for Implementing Lock-Free Shared Data Structures. In Proceedings of the Fifth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA ’93). Association for Computing Machinery, New York, NY, USA, 261–270. doi:10.1145/ 165231.165265 [10] Denis Bédin, François Lépine, Achour Mostéfaoui, Damien Perez, and Matthieu Perrin. 2021. Wait-Free CAS-Based Algorithms: The Burden of the Past. In 35th International Symposium on Distributed Computing (LIPIcs, Vol. 209). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 11:1–11:15. doi:10.4230/LIPIcs.DISC.2021.11 [11] Naama Ben-David and Guy E. Blelloch. 2022. Fast and Fair Randomized Wait-Free Locks. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (PODC ’22). Association for Computing Machinery, New York, NY, USA, 187–197. doi:10.1145/3519270.3538448 [12] Naama Ben-David, Guy E. Blelloch, and Yuanhao Wei. 2022. Lock-Free Locks Revisited. In Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP ’22). Association for Computing Machinery, New York, NY, USA, 278–293. doi:10.1145/3503221.3508433 [13] Keren Censor-Hillel, Erez Petrank, and Shahar Timnat. 2015. Help!. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC ’15). Association for Computing Machinery, New York, NY, USA, 241–250. doi:10.1145/2767386.2767415 [14] Danny Dolev and Nir Shavit. 1997. Bounded Concurrent TimeStamping. SIAM J. Comput. 26, 2 (1997), 418–455. doi:10.1137/ S0097539790192647 15