Non-blocking Algorithms

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

1. Start with the implementation of the set using simple linked list.
   1. Download a template fromhttps://gitlab.fel.cvut.cz/cuchymar/nonblock-basic-template.git
   2. Design a representation of the node (AtomicReference).
   3. Implement the add(int value) method for the case that all threads only writes to the list (no deletes)
   4. Implement the delete(int value) method.
   5. Implement the delete(int value) method correctly with marking of the deleted node beforehand and with other threads helping with the delete if they find any marked node. You will have to modify the Node class so it is able to work with the marks (AtomicMarkableReference). 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.
   6. 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, start with the contains method which just goes through the list and tries to find the value. It does not need to change anything in the skip list.
   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
3. Upload the source code of NonblockSkipListSet to BRUTE. There is no automatic evaluation and the code will be evaluated during the seminars.