A Concurrent List with Adaptive Bounds

Abstract

Few concurrent data structures adapt dynamically to access patterns, and those that do lack formal performance guarantees. This thesis introduces the first self-adjusting concurrent data structure with an adaptive bound analogous to those of optimal self-adjusting sequential structures. We present a lock-free move-to-front (MTF) list supporting a dynamic set of keys, where an operation op on a key k runs in an amortized number of steps proportional to the size of its working plus a contention term. The working set of op is the set of keys accessed since the last operation on key k, and contention is the number of operations that run concurrently with op. We further show that the list performs at most twice as much work as the best possible fixed list for a set of searches, up to contention. Finally, we prove that the number of nodes reachable from shared memory is bounded by the number of keys in the set plus contention.