Lock-free, constant update-time concurrent tree data-structures?

Question

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".

---

1. Tarjan, Robert Endre. “Updating a Balanced Search Tree in O(1) Rotations.” Information Processing Letters 16, no. 5 (1983): 253 – 257.

2. 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, 109–121. STOC ’86. New York, NY, USA: ACM, 1986.

3. Levcopoulos, C., and Mark H. Overmars. “A Balanced Search Tree with O(1) Worst Case Update Time.” Acta Inf. 26, no. 3 (November 1988): 269–277.

4. Fleischer, Rudolf. A Simple Balanced Search Tree With O(1) Worst-Case Update Time

5. Dietz, Paul F, and Rajeev Raman. “A Constant Update Time Finger Search Tree.” Information Processing Letters 52, no. 3 (1994): 147 – 154.

6. 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): 607–632.

7. Brodal, Gerth Stølting, 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): 381–418.

Answer 1

$O(1)$ doesn't help in and of itself. In a lock-free data structure there needs to be a single atomic instance when your data structure appears to change. All the representation invariants need to be in force both immediately before and immediately after that atomic instant.

This means that if you are doing a modification to the data structure the important characteristic is that you can do all the mods on a private data structure and then swap in the modifications in a single atomic instruction.

Lock-freedom is usually easiest when your data structures are immutable (purely functional). You simply keep a global pointer to the current version of the data structure. Readers don't need to lock anything. Modifications to the data-structure are effected by swapping the global pointer to one immutable data structure to another.

For example: if you have a purely functional tree balanced tree you:

1. Record the current global pointer to the root of the tree.
2. Create a new tree that inserts or deletes a node. (This is logarithmic in time and space in the number of nodes currently in the tree, and involves creating new nodes from the modification point up to the root, and just pointing everything new at the old parts of the previous version of the data structure.)
3. Atomically compare and swap the global pointer to the root. (Note that this might fail if another modification has happened between the time you recorded the old root pointer and now. If this happens you go back to step 1 and try again. This is so-called "optimistic concurrency control.")

Note that the most important part is what I said above about needing to maintain representation invariants. It is usually not sufficient to have an algorithm that atomically makes a change in the middle of the tree. Why? For example: you might have a reader thread that is in the process of doing a preorder traversal of the tree. If you modify a node that is an ancestor of the node they are currently reading then you are going to invalidate preconditions that they thought they had enforced. The reader needs to be able to work with the data structure exactly as it was before you made your change, or exactly as it will be after you've made your change. Not something in between.

Edit: As @Raphael pointed out there are techniques for making mutable data structures lock-free. A proof by construction that this can always be done is: As long as you have a single global pointer to the "top" of your data structure, even if it is mutable you can always copy the entire data structure, make your mods to the copy, and then, using optimistic concurrency control, try to compare-and-swap the pointer to your newly minted data structure in for the original. The beauty of functional tree-based data structures is that they keep the cost of copying down at $O(log(N))$ of a size $O(N)$ data structure.