Fast Randomized Test-and-Set and Renaming
Fast Randomized Test-and-Set and Renaming
复制标题
快速随机测试和设置以及重命名
DOI：
10.1007/978-3-642-15763-9_9
复制
发表时间：
2010
影响因子：
0.5
通讯作者：
R. Guerraoui
中科院分区：
文献类型：
--
作者：
Dan Alistarh;H. Attiya;Seth Gilbert;A. Giurgiu;R. Guerraoui
大多数人认为重命名很容易：只需随机选择一个名称;如果多个进程选择了相同的名称，则重试。我们强调的问题时，试图实现这样一个计划，并揭示了新的光在异步环境中的随机重命名的读写复杂性。在我们的新观点的核心是一个随机测试和设置对象的自适应实现，每个操作具有高概率的多对数步骤复杂度。有趣的是，我们的实现是匿名的，因为它不需要进程标识符。在此基础上，我们提出了两个新的随机重命名算法。第一个确保了一个紧密的命名空间的n个名称使用O（n log 4 n）总步骤，具有很高的概率。这大大提高了以前已知的最佳命名空间优化算法的复杂性。第二个算法使用O（klog 4k/log 2（1 + e））总步骤实现大小为k（1 + e）的命名空间，两者都具有高概率，其中k是执行中的总争用。它是第一个自适应随机重命名算法，它通过提供更小的命名空间和降低步骤复杂度来改进现有的确定性解决方案。
Most people believe that renaming is easy: simply choose a name at random; if more than one process selects the same name, then try again. We highlight the issues that occur when trying to implement such a scheme and shed new light on the read-write complexity of randomized renaming in an asynchronous environment. At the heart of our new perspective stands an adaptive implementation of a randomized test-and-set object, that has poly-logarithmic step complexity per operation, with high probability. Interestingly, our implementation is anonymous, as it does not require process identifiers. Based on this implementation, we present two new randomized renaming algorithms. The first ensures a tight namespace of n names using O(n log4 n) total steps, with high probability. This significantly improves on the complexity of the best previously known namespace-optimal algorithms. The second algorithm achieves a namespace of size k(1 + e) using O(k log4 k/ log2(1 + e)) total steps, both with high probability, where k is the total contention in the execution. It is the first adaptive randomized renaming algorithm, and it improves on existing deterministic solutions by providing a smaller namespace, and by lowering step complexity.