A Lock-Free Implementation of Union-Find

Implementing parallel systems is highly complex domain composed of many layers ranging from processor architecture to algorithm design. Motivation to implement such systems is to decrease needed time to complete various computations. Implementing parallel Union-Find might be useful because many parallel algorithms are based on this simple, yet powerful data structure. In this thesis we implement parallel Union-Find data structures in a Lock-Free and a Blocking manner, parallel algorithms for Strongly Connected Components graph decomposition which use Union-Find data structure. At the end of this thesis we discuss whether we were successful at implementing parallel data structures and algorithms and how much speedup do they bring.