здесь имеется библиотека таких структур и публикации, описывающие их.
Надеюсь кому-то будет интересно.

P.S. не уверен правда с топиком для сообщения , но в свете недавних тем про распараллеливание это можно взять как один из возможных подходов.

Здравствуйте, Курилка, Вы писали:

К>здесь имеется библиотека таких структур и публикации, описывающие их.
К>Надеюсь кому-то будет интересно.

Lock-free library (including object-based STM)
A set of lock-free programming abstractions and search structures. Includes an object-based software transactional memory, multi-word compare-and-swap, and a range of search structures (skip lists, binary search trees, red-black trees).

lock-free-lib.tar.gz

Ознакомление с внутренностями показало, что:
a) лицензия GPL;
b) Unix-овая, использует примитивы из pthread;
c) судя по Makefile поддерживает архитектуры: SPARC, INTEL (надо полагать x86), PPC, IA64, MIPS, ALPHA

может быть эта информация будет полезна тем, кто захочет с ходу в каком-нибудь коммерческом проекте применить.