Is the normal union/find algorithm thread safe without any extra work?

Question

The standard union/find or Disjoint-set data structure has very good running times (effectively O(1)) for single threaded cases. However what is it's validity/performance under multi-threaded cases? I think that it is totally valid even without locking or any atomic operations aside from atomic pointer sized writes.

Does anyone see any problems with the following logic?

First I will assume that pointer sized writes are atomic. From that, it's not hard to argue that you can safely run the find function in several threads as the only updates that will occur are all sets to the same value. If you allow the find function to return the answer that was true when it was called (as opposed to when it returned) it's not hard to argue that many finds and a single union can be run at the same time; the argument for the finds doesn't change and the union only updates roots and the finds never update roots.

As for the remaining case (several unions), I think that works as well but I'm not so sure of it.

BTW: I'm not requiring that the solution be just as efficient as the single threaded version. (In order to avoid locks/atomic, I'm also willing to discard globally coherent state.)

---

edit: taking another look, the many-union cases doesn't work because if the side that is not the new root is unioned with something else (also not as a root) then you could cut it off of other side of the second union.

A = find(a)  // union 1
B = find(b)  // union 1
----
X = find(x)  //   union 2 (x == a) -> (X == A) -> (X.par aliases A.par)
Y = find(y)  //   union 2
X.par = Y    //   union 2
----
A.par = B    // union 1

this can be sidestepped with a CAS:

while(!CAS(A == A.par, B)) A = find(A); 

Answer 1

The type of synchronization which you can use for this structure is similar with the Readers-writers problem. The performance will depend on how many unions will be executed because then the find operation will be stopped.

I'm not sure that you can run many finds and a single union in the same time because the last case from an union operation is not atomic.

Answer 2

A little late but for future reference. With atomic operations, you can build a disjoint set data structure. The invariant is that each set is represented by its smallest member, which allows avoiding loops due to race conditions.

// atomic_compare_and_exchange(unsigned int *data, unsigned int new_value, unsigned int comparator)


// "The result used to be the root of v once"
static unsigned int GetSet(volatile unsigned int *H_RESTRICT set, const unsigned int v)
{
  unsigned int next;
  unsigned int root = v;
  unsigned int prev = v;

  while (root != (next = set[root]))
  {
    /* Update set[prev] to point to next instead of root.
      * If it was updated by some other thread in the meantime, or if this
      * is the first step (where set[prev]==next, not root), ignore. */
    atomic_compare_and_exchange(set + prev, next, root);

    prev = root;
    root = next;
  }

  /* Update the path to the root */

  return root;
}

// FALSE == "They used not to be in the same set"
// TRUE == "They are in the same set, and will be forever"
static HBOOL IsInSameSet(volatile unsigned int *H_RESTRICT set, unsigned int v1, unsigned int v2)
{
  do
  {
    v1 = GetSet(set, v1);
    v2 = GetSet(set, v2);
  } while (set[v1] != v1 || set[v2] != v2);

  return v1 == v2;
}

static void Union(volatile unsigned int *H_RESTRICT set, unsigned int v1, unsigned int v2)
{
  unsigned int result;

  do
  {
    v1 = GetSet(set, v1);
    v2 = GetSet(set, v2);
    if (v1 == v2)
    {
      /* Already same set. This cannot be changed by a parallel operation. */
      break;
    }
    if (v1 < v2)
    {
      /* Make sure we connect the larger to the smaller set. This also avoids
       * cyclic reconnections in case of race conditions. */
      unsigned int tmp = v1;
      v1 = v2;
      v2 = tmp;
    }

    /* Make v1 point to v2 */
    result = atomic_compare_and_exchange(set + v1, v2, v1);
  } while (result != v1);
}