File ConcurrentUnionFind.h

↰ Parent directory (ADS/concurrent)

The union-find that many threads change at once, beyond the book [see File UnionFind.h for the sequential ones]: the n elements 0 , … , n - 1 in a forest of parents, a root being its own parent, each parent an atomic word changed only by compare-and-swap, with no lock.

Definition (ADS/concurrent/ConcurrentUnionFind.h)

Detailed Description

  • find( x ) climbs to the root by splitting: each element on the way is given, by a compare-and-swap that may fail with no harm, the parent of its parent, so that the paths halve their lengths as they are walked (the splitting of Jayanti and Tarjan, the concurrent form of the path splitting analysed by Tarjan and van Leeuwen);

  • unite( x , y ) finds the two roots and hooks the larger under the smaller by a compare-and-swap on the parent of the larger, which fails, and is tried again from the roots found anew, only if another thread hooked that root first. Since a root is hooked only under a smaller element, no cycle can form, and the root of a tree is its least element: the labels root( x ) are canonical, the same for every order of the operations (the linking by index of Jayanti and Tarjan with the identity as the order);

  • compress( x ) points x to its root, and parent( x ) reads its parent, so that after the compression of all the elements, with no union running, parent( x ) is the label of the set of x;

  • sameSet( x , y ) is true if x and y were in the same set at a moment of the call, false if they were not at a moment of the call (a root found for x that is still a root after the root of y is found). The operations are linearizable. On one thread, the linking by index with the splitting takes :math:` O( m log_{2 + m / n} n ) ` steps for m operations on n elements (Tarjan and van Leeuwen); the randomized linking of Jayanti and Tarjan, which hooks by a random order instead of the indices, bounds the expected work on p threads by :math:` O( m ( alpha( n ,

m / ( n p ) ) + log( n p / m + 1 ) ) ) `, at the price of labels that are not the least elements.

The contracts [see File Contract.h]: the elements are in [ 0 , n ), n < 2^31; size() and the construction are not concurrent with the other operations. S. V. Jayanti, R. E. Tarjan, Concurrent disjoint set union, Distributed Computing 34(6), 413-436, 2021, doi:10.1007/s00446-020-00388-x

    1. Tarjan, J. van Leeuwen, Worst-case analysis of set union algorithms, Journal of the ACM 31(2), 245-281, 1984, doi:10.1145/62.2160

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes