论文标题
通用唤醒：可线化数据结构的摊销共享存储器下限
Generalized Wake-Up: Amortized Shared Memory Lower Bounds for Linearizable Data Structures
论文作者
论文摘要
在这项工作中，我们为具有$ n $流程的共享内存异步系统定义了广义的唤醒问题，即$ GWU（S）$。从非正式的角度来看，该问题是由增加的序列$ s = s_1，\ ldots，s_p $进行参数的，要求至少$ n -i + 1 $流程确定至少其他流程“醒了”，并且至少对每个$ 1 \ le i \ le i i \ le i \ le n $ persection of tem opt o。我们证明，使用读取/写入/比较swap变量的$ GWU（s）$的任何解决方案都需要至少$ω\ left（\ sum_ {i = 1}^n \ log s_i \ right）$ sptep。 通用的唤醒下限是一种技术，可以通过减少来证明许多可线化的并发数据类型的操作摊销复杂性的下限。我们用几个示例说明了这一点：（1）我们显示了$ω（\ log n）$摊销的下界，对实现计数器的复杂性和{\ em fetth-and-increment}对象，该对象与Jayanti和Ellen＆Woelfel给出的算法的复杂性相匹配；下边界甚至延伸到对象的明显放松版本。 （2）我们在POP，DECLEEUE和DELETEMIN操作的复杂性上显示了$ω（\ log n）$摊销的下限，即使数据类型定义显着放松，也可以分别保持同时堆栈，队列和优先队列的同时堆栈，队列和优先队列； （3）在另一篇论文中，我们显示了$ω（\ log \ log \ log（n \ ell/m））$ amortized在size $ \ ell $（执行$ m $ aperations y时）对Union-Find对象的操作的复杂性上的下降。
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,\ldots,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 \le i \le n$. We prove that any solution to $GWU(s)$ that uses read/write/compare-and-swap variables requires at least $Ω\left(\sum_{i = 1}^n \log s_i \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 $Ω(\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 $Ω(\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 $Ω(\log\log(n \ell/m))$ amortized lower bound on the complexity of operations on a union-find object of size $\ell$ (when $m$ operations are performed).
