  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) + \alpha(n, m/(np)))$ for a problem with $n$ elements and $m$ operations
solved by $p$ processes, where $\alpha$ 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.
