Generalized Wake-Up: Amortized Shared Memory Lower Bounds for Linearizable Data Structures

In this work, we define the generalized wake-up problem, GWU(s), for a shared memory asynchronous system with n processes. Informally, the problem, which is parametrized by an increasing sequence s = s1,ldots,sp, asks that at least n - i + 1 processes identify that at least si other processes have "woken up" and taken at least one step for each 1 ≤ i ≤ n. We prove that any solution to GWU(s) that uses read/write/compare-and-swap variables requires at least Omegaleft(sumi = 1n log si right) steps to solve. The generalized wake-up lower bound serves as a technique for proving lower bounds on the amortized complexities of operations on many linearizable concurrent data types through reductions. We illustrate this with several examples: (1) We show an Omega(log n) amortized lower bound on the complexity of implementing counters and em fetch-and-increment objects which match the complexities of the algorithms given by Jayanti and Ellen & Woelfel; the lower bound even extends to a significantly relaxed version of the object. (2) We show an Omega(log n) amortized lower bound on the complexity of the pop, dequeue, and deleteMin operations of a concurrent stack, queue, and priority queue respectively that hold even if the data type definitions are significantly relaxed; (3) In another paper, we have shown an Omega(loglog(n ℓ/m)) amortized lower bound on the complexity of operations on a union-find object of size ℓ (when m operations are performed).