Wait-Free Locks Should Not Fear Later Arrivals
Distributed, Parallel, and Cluster Computing
Summary
The authors explore a technique called helping, which lets processes finish others' stalled work to keep programs running smoothly. They identify a problem where a task can get stuck helping new requests endlessly, causing delays. To fix this, they create SeniorLock, a system that tracks how long a task has been waiting, ensuring it only spends time on requests active when it started, a property they call retrospective wait-freedom. They also build SeniorObj, which uses SeniorLock to safely make many types of operations run without unnecessary delays or copying data. This work improves the fairness and efficiency of shared-memory programs.
Authors
Tong Che
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 $O((β+1)(T+1))$ local shared-memory steps, where $T$ bounds one thunk's cost, independently of later invocations. We call this guarantee \emph{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.