A lock-free algorithm for union-find with deletion

The classical union-find algorithm is the basis for many graph algorithms and for dealing with equality. The easiest way to implement concurrent objects is by means of classical software solutions, but this leads to blocking when the process that holds exclusive access to the object is delayed or stops functioning. Thus we require our solutions to the data structure problem have the lock-free property. In this paper, we present an efficient lock-free algorithm for union-find with deletion, which promises more robust performance and reliability than conventional lock-based implementations.