Thread: Problem with snapshot in lock-free set

I wrote a lock-free set. It was a lab assignment.
The teacher said that there is a problem in the implementation of snapshot. It is necessary to give an example of how to achieve this effect.
He said that I need to find an option when two elements always exist in turn in the list, and the snapshot says that they were never in the list

I've already lost all hope of coming up with an example

My code:

public class Node<T extends Comparable<T>> {
    private final T value;
    private final AtomicMarkableReference<Node<T>> nextNode;
 
    public Node(final T value, final AtomicMarkableReference<Node<T>> nextNode) {
        this.value = value;
        this.nextNode = nextNode;
    }
 
    public Node(final T value) {
        this(value, new AtomicMarkableReference<>(null, false));
    }
 
    public T getValue() {
        return value;
    }
 
    public AtomicMarkableReference<Node<T>> getNextNode() {
        return nextNode;
    }
}
 
public class SetImpl<T extends Comparable<T>> {
    private final AtomicMarkableReference<Node<T>> head;
 
    public SetImpl() {
        this.head = new AtomicMarkableReference<>(new Node<>(null), false);
    }
 
    public boolean add(final T value) {
        final var newNode = new Node<>(value);
 
        while (true) {
            final var nodePosition = findNode(value);
 
            if (nodePosition.getRight() != null) {
                return false;
            }
 
            if (nodePosition.getLeft().getNextNode().compareAndSet(null, newNode, false, false)) {
                return true;
            }
        }
    }
 
    public boolean remove(final T value) {
        while (true) {
            final var nodePosition = findNode(value);
 
            if (nodePosition.getRight() == null) {
                return false;
            }
 
            final var nextNode = nodePosition.getRight().getNextNode().getReference();
            if (nodePosition.getRight().getNextNode().compareAndSet(nextNode, nextNode, false, true)) {
                nodePosition.getLeft().getNextNode().compareAndSet(nodePosition.getRight(), nextNode, false, false);
                return true;
            }
        }
    }
 
    public boolean contains(final T value) {
        return findNode(value).getRight() != null;
    }
 
    public boolean isEmpty() {
        return makeSnapshot().isEmpty();
    }
 
    private Pair<Node<T>, Node<T>> findNode(final T value) {
        Node<T> previousNode;
        Node<T> currentNode;
 
        for (
            previousNode = head.getReference(), currentNode = previousNode.getNextNode().getReference();
            currentNode != null;
            previousNode = currentNode, currentNode = currentNode.getNextNode().getReference()
        ) {
            if (currentNode.getNextNode().isMarked()) {
                boolean marked = previousNode.getNextNode().isMarked();
                previousNode.getNextNode().compareAndSet(currentNode, currentNode.getNextNode().getReference(), marked, marked);
            }
 
            if (!currentNode.getNextNode().isMarked() && value.equals(currentNode.getValue())) {
                return new ImmutablePair<>(previousNode, currentNode);
            }
        }
 
        return new ImmutablePair<>(previousNode, null);
    }
 
    private Collection<T> makeSnapshot() {
        List<Node<T>> nodesV1;
        List<Node<T>> nodesV2;
 
        do {
            nodesV1 = getCurrentNodes();
            nodesV2 = getCurrentNodes();
        } while (!nodesV1.equals(nodesV2));
 
        return nodesV1.stream().map(Node::getValue).collect(Collectors.toList());
    }
 
    private List<Node<T>> getCurrentNodes() {
        final List<Node<T>> result = new ArrayList<>();
 
        for (
            Node<T> node = head.getReference().getNextNode().getReference();
            node != null;
            node = node.getNextNode().getReference()
        ) {
            if (!node.getNextNode().isMarked()) {
                result.add(node);
            }
        }
 
        return result;
    }
}

Originally Posted by Norm

Is there some output that you can post to show what you are asking about?
Be sure to add some comments where the problem is that describe the problem.

The problem is not permanent.
it consists in the mismatch of the internal state and the state of the snapshot
And if I understand correctly, one of the elements is always in the list