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

arXiv: https://arxiv.org/abs/2207.07561 · HTML: https://mlsanity.com/paper/2207.07561/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jul 2022.

## Built on by (most cited first, 1 of 1)

- [On the First Computer Science Research Paper in an Indian Language and the Future of Science in Indian Languages](https://mlsanity.com/paper/2604.03265/) (2026)

## Abstract (arXiv)

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).