I've been reading a bit of the literature lately, and have found some rather interesting data-structures.I have researched various different methods of getting update times down to $\mathcal{O}(1)$ worst-case update time [1-7].Recently I begun looking into lock-free data-structures, to support efficient concurrent access.Have any of these worst-case $\mathcal{O}(1)$ update-time techniques been used in the implementation of lock-free data structures?I ask because; to me, they seem like the obvious practical extension of this theoretical enhancement.Tarjan, Robert Endre. Updating a Balanced Search Tree in O(1) Rotations. Information Processing Letters 16, no. 5 (1983): 253  257.Driscoll, J R, N Sarnak, D D Sleator, and R E Tarjan. Making Data Structures Persistent. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, 109121. STOC  86. New York, NY, USA: ACM, 1986.Levcopoulos, C., and Mark H. Overmars. A Balanced Search Tree with O(1) Worst Case Update Time. Acta Inf. 26, no. 3 (November 1988): 269277.Fleischer, Rudolf. A Simple Balanced Search Tree With O(1) Worst-Case Update TimeDietz, Paul F, and Rajeev Raman. A Constant Update Time Finger Search Tree. Information Processing Letters 52, no. 3 (1994): 147  154.Lagogiannis, George, Christos Makris, Yannis Panagis, Spyros Sioutas, and Kostas Tsichlas. New Dynamic Balanced Search Trees with Worst-case Constant Update Time. J. Autom. Lang. Comb. 8, no. 4 (July 2003): 607632.Brodal, Gerth Stlting, George Lagogiannis, Christos Makris, Athanasios Tsakalidis, and Kostas Tsichlas. Optimal Finger Search Trees in the Pointer Machine. J. Comput. Syst. Sci. 67, no. 2 (September 2003): 381418.
Lock-free, constant update-time concurrent tree data-structures?
reference request;data structures;time complexity;concurrency;search trees