Generalized Wake-Up: Amortized Shared Memory Lower Bounds for Linearizable Data Structures
share
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 = s_1,…,s_p, asks that at least n - i + 1 processes identify that at least s_i 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 Ω(∑_i = 1^n log s_i ) 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 Ω(log n) amortized lower bound on the complexity of implementing counters and 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 Ω(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 Ω(loglog(n ℓ/m)) amortized lower bound on the complexity of operations on a union-find object of size ℓ (when m operations are performed).
READ FULL TEXT