title: Is the normal union/find algorithm thread safe without any extra work?
body: <p>The standard <a href="http://en.wikipedia.org/wiki/Disjoint-set_data_structure" rel="nofollow noreferrer">union/find or Disjoint-set</a> data structure has very good running times (effectively <code>O(1)</code>) for single threaded cases. However what is it's validity/performance under multi-threaded cases? I <em>think</em> that it is totally valid even without locking or any atomic operations aside from atomic pointer sized writes.</p>
  <p>Does anyone see any problems with the following logic?</p>
  <blockquote>
  <p>First I will assume that pointer sized writes are atomic. From that, it's not hard to argue that you can safely run the <code>find</code> function in several threads as the only updates that will occur are all sets to the same value. If you allow the <code>find</code> 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 <code>find</code>s and a single <code>union</code> can be run at the same time; the argument for the <code>find</code>s doesn't change and the <code>union</code> only updates roots and the <code>find</code>s never update roots.</p>
  <p>As for the remaining case (several <code>union</code>s), I think that works as well but I'm not so sure of it.</p>
  </blockquote>
  <p>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.)</p>
  <hr />
  <p><em>edit:</em> 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.</p>
  <pre><code>A = find(a)  // union 1
  B = find(b)  // union 1
  ----
  X = find(x)  //   union 2 (x == a) -&gt; (X == A) -&gt; (X.par aliases A.par)
  Y = find(y)  //   union 2
  X.par = Y    //   union 2
  ----
  A.par = B    // union 1
  </code></pre>
  <p>this can be sidestepped with a <a href="http://en.wikipedia.org/wiki/Compare-and-swap" rel="nofollow noreferrer">CAS</a>:</p>
  <pre><code>while(!CAS(A == A.par, B)) A = find(A); 
  </code></pre>