Что такое ABA-проблема в алгоритмах на CAS?

Для счётчиков это безобидно, но в структурах данных со ссылками может быть фатально: узел удалили, память переиспользовали, и ссылка снова указывает на тот же адрес — CAS решит, что ничего не произошло, и порушит структуру. Штатное решение в Java — AtomicStampedReference, где вместе со ссылкой хранится версия-метка, увеличивающаяся при каждом изменении; сравнение идёт по паре, поэтому возврат к прежнему значению обнаруживается. Есть и AtomicMarkableReference с одним булевым флагом для более простых случаев. Полезно упомянуть, что сам CAS реализован аппаратной инструкцией процессора и лежит в основе всех атомарных классов и большей части java.util.concurrent.