Finding Patterns in Lock-Free Algorithms

Lock-free algorithms are an approach to concurrent programming wherethreads access shared state without mutual exclusion. Writing correctcomplex lock-free programs can come with great difficulties. The typesystem Capable aims to aid the programmer in writing concurrentsoftware, such as lock-free algorithms. This thesis presents ananalysis of the current state of Capable and how applicable it is tomodern lock-free data structures. It also presents common patternsfound in various lock-free data structures, which can be reused whenwriting new lock-free data structures