On the time and space complexity of randomized test-and-set
On the time and space complexity of randomized test-and-set
复制标题
关于随机测试和设置的时间和空间复杂度
DOI：
10.1145/2332432.2332436
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Philipp Woelfel
中科院分区：
文献类型：
--
作者：
George Giakkoupis;Philipp Woelfel
研究了n进程异步共享存储模型中原子读写寄存器的随机化测试和设置(TAS)实现的时间和空间复杂性。我们提出了一种自适应TAS算法，其期望(个体)步长复杂度为O(log*k)，用于对抗不经意的对手，改进了以前O(Loglogn)的(非自适应)上界(Alistarh和Aspnes，2011)。我们还提出了一种改进的自适应RatRace TAS算法(Alistarh等人，2010)，它将空间复杂度从O(N3)提高到O(N)，同时针对自适应对手保持了对数预期步长复杂度。我们用Ω(Logn)下界来补充这个上界，该上界是任何具有不确定单终止性(这是比等待自由更弱的进展条件)的算法的空间复杂度的下界。在这项工作之前，并不知道TAS空间需求的非平凡下限。
We study the time and space complexity of randomized Test-And-Set (TAS) implementations from atomic read/write registers in asynchronous shared memory models with n processes. We present an adaptive TAS algorithm with an expected (individual) step complexity of O(log* k), for contention k, against the oblivious adversary, improving a previous (non-adaptive) upper bound of O(log log n) (Alistarh and Aspnes, 2011). We also present a modified version of the adaptive RatRace TAS algorithm (Alistarh et al., 2010), which improves the space complexity from O(n3) to O(n), while maintaining logarithmic expected step complexity against the adaptive adversary. We complement this upper bound with an Ω(log n) lower bound on the space complexity of any TAS algorithm that has the nondeterministic solo-termination property (which is a weaker progress condition than wait-freedom). No non-trivial lower bounds on the space requirements of TAS were known prior to this work.