ну это даже по состоянию на 2010 год было неправдой, было несколько статей с их реализацией через DCAS, и статья Sundell-Tsigas 2008 года через ванильные касы: http://www.cse.chalmers.se/~tsigas/papers/Lock-Free-Deques-Doubly-Lists-JPDC.pdf

с тех пор еще несколько статей вышло, например
https://arxiv.org/abs/1408.1935 Shafiei, "Non-Blocking Doubly-Linked Lists with Good Amortized Complexity"

а, я понял откуда там взялось это утверждение - они процитировали статью Саттера из 2008 года, на которую в конце дали ссылку: https://www.drdobbs.com/cpp/lock-free-code-a-false-sense-of-security/210600279

Я не знаю "про еще несколько статей", но статья Sundell-Tsigas это лажа. Мы сами лично на ней нажглись, до сих пор страдаем. JDK тоже мучается. Мы недавно у них нашим новым инструментом для model-checking-а нашли очередную багу (и это при том, что они его уже до нас пытались латать пару раз): https://gist.github.com/ndkoval/56ff3b83d2d39e0afd3a08900e1499d4

да, в статье Шафьей говорится о потенциальных проблемах у Санделл-Цигаса

но это всё конкретно про двусвязные списки, для дек есть и другие реализации, Чейз-Лева например

погодите, а вы про стандартный жвмовский ConcurrentLinkedDeque?

Про него, родного. Очень жаль, но он никогда не был линеаризуем и несколько попыток его починить так ни к чему и не привели. Как только наши ребята допилили lincheck, чтобы он умел model-checking делать (раньше только стресс-тестирование умел), то там сразу и бага нашлась.

так там вроде не Санделл-Цигас, а вариация на тему Майкла-Скотта

Теперь никто не поймет. Но есть мнение что эффективный линеаризуемый lock-free deque (если не применять универсальную конструкцию и другие дескрипторы) вообще не написать. Мы не видели. Если кто видел - шлите код. Мы с радостью найдем там багу (ребятам надо для статьи побольше такого материала).

Статьи за код не катят. Там в каждой первой такой статье лажа. Обычными тестами такая лажа не находится.

Что значит lock-free в вашем случае? Наличие CAS считается как lock-free реализация?

У Tsigas-Sundell тоже «доказательство» есть. Но оно не помогает.

Что без CAS его нельзя написать я умею доказыать. И со студентов своих это доказательство требую.

(Конечно на CAS-ax)

Там даже с CAS есть проблемка с ABA. Обычно решается через тегирование

У меня высокоуровневый взгляд. Имеется в виду при наличии GC. Если у вас еще GC нет и надо еще уметь понимать когда память можно физически освободить, ты вы его точно никогда не отладите.

(однако, вместо GC можно воткнуть любую универсальную стратегию, хоть те же hazard pointers, хоть сейчас уже вроде и не модно, ибо медленно)

/извините за продолжение оффтопика/, но мы вывели империческое правило, что если у вас concurrent алгоритм в котором нетривиальное число CAS-ов и у вас нет механически проверенного доказательства его корректности, то вряд ли он корректен. У нас тут ребята делали новый быстрый алгоритм семафора (а это уж намного более простая штука чем deqeue). Несколько экспертов думало и изучало алгоритм, тестов написано вагон. Начали док-во на Coq прикручивать, так сразу нашли несколько багов.