Non-blocking Algorithms

Your task is to implement a concurrent set of integers implemented as a skip list without using locks.

Presentation in PDF

1. Start with the implementation of the set using simple linked list (not mandatory, but recommended).
   1. Download a template fromhttps://gitlab.fel.cvut.cz/cuchymar/nonblock-basic-template.git
   2. Implement the delete(int value) method with marking of the deleted node beforehand (logical deletion) and with other threads helping with the physical deletion if they find any marked node. Implement a helper method find(int value), which traverses the list until it finds the correct position of the value and deletes the marked nodes during the traversal. Implement add(int value) method.
   3. Implement wait-free contains(int value) method. The method is read-only.
2. Generalize the previous algorithm to a skip list. Use the template from https://gitlab.fel.cvut.cz/cuchymar/nonblock-skiplist-template.git
   1. To clarify how the skip list works, we recommend to start with the contains method which just goes through the list and tries to find the value (without calling find method). It does not need to change anything in the skip list. This point is not mandatory.
   2. Try to generalize the method find(), to look not only for one predecessor and one successor of the searched value but for the predecessors on all the levels.
   3. Implement add and delete methods
   4. Testing is an important part of implementation of any algorithm therefore your task is also to create tests. Unfortunatelly, testing of concurrent structures is difficult.
      • Start with testing of only single-thread behaviour (very easy).
      • Try to desing some tests that checks the functionality in a multi-threaded environment. Check if invariants are satisfied - e.g. the ordering. Because of the unpredictable thread scheduling, the tests must be run multiple times to test it at least to some extent.
      • You have to be able to demonstrate that the algoritm is working correctly.
3. Upload the source code of NonblockSkipListSet to https://cw.felk.cvut.cz/brute/teacher/course/991. There is no automatic evaluation and the code will be evaluated manually during the seminars.