论文标题
并发脱节设置联盟
Concurrent Disjoint Set Union
论文作者
论文摘要
我们开发和分析了共享内存中的分离集合（联合获取）问题的并发算法，同步的计算模型，使用CAS（比较和交换）或DCA（双重比较和交换）作为同步原始化。 We give a deterministic bounded wait-free algorithm that uses DCAS and has a total work bound of $O(m \cdot (\log(np/m + 1) + α(n, m/(np)))$ for a problem with $n$ elements and $m$ operations solved by $p$ processes, where $α$ is a functional inverse of Ackermann's function. We give two randomized algorithms that use CAS仅具有相同的工作，即使调度程序是对手的，对第二个随机算法的分析也是有效的。真正的可扩展性。
We develop and analyze concurrent algorithms for the disjoint set union (union-find) problem in the shared memory, asynchronous multiprocessor model of computation, with CAS (compare and swap) or DCAS (double compare and swap) as the synchronization primitive. We give a deterministic bounded wait-free algorithm that uses DCAS and has a total work bound of $O(m \cdot (\log(np/m + 1) + α(n, m/(np)))$ for a problem with $n$ elements and $m$ operations solved by $p$ processes, where $α$ is a functional inverse of Ackermann's function. We give two randomized algorithms that use only CAS and have the same work bound in expectation. The analysis of the second randomized algorithm is valid even if the scheduler is adversarial. Our DCAS and randomized algorithms take $O(\log n)$ steps per operation, worst-case for the DCAS algorithm, high-probability for the randomized algorithms. Our work and step bounds grow only logarithmically with $p$, making our algorithms truly scalable. We prove that for a class of symmetric algorithms that includes ours, no better step or work bound is possible.
