English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We develop and analyze concurrent algorithms for the disjoint set union(union-find) problem in the shared memory, asynchronous multiprocessor model ofcomputation, with CAS (compare and swap) or DCAS (double compare and swap) asthe synchronization primitive. We give a deterministic bounded wait-freealgorithm 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$ operationssolved by $p$ processes, where $\alpha$ is a functional inverse of Ackermann'sfunction. We give two randomized algorithms that use only CAS and have the samework bound in expectation. The analysis of the second randomized algorithm isvalid even if the scheduler is adversarial. Our DCAS and randomized algorithmstake $O(\log n)$ steps per operation, worst-case for the DCAS algorithm,high-probability for the randomized algorithms. Our work and step bounds growonly logarithmically with $p$, making our algorithms truly scalable. We provethat for a class of symmetric algorithms that includes ours, no better step orwork bound is possible.

Concurrent Disjoint Set Union