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

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

• Please consider adding links to the papers as a courtesy to people who want to investigate your issue. – Raphael Jul 17 '12 at 14:26
• Okay, added in links to respective articles. – A T Jul 18 '12 at 5:21
• I suggest reposting at cstheory.SE (with a link back here) if you don't get a useful response soon. – JeffE Jul 18 '12 at 14:59
• Thanks for the suggestion. I have reposted: Lock-free, constant update-time concurrent tree data-structures? – A T Jul 19 '12 at 15:56
• I used the Practical lock-free data structures library before. They have some support of lock-free tree data structures. Maybe the have what you are looking for. – Reza Feb 1 '13 at 1:44

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

• I think active waiting techniques, e.g. with compare-and-swap, are usually called "lock free" so there are some ways out, even in the mutable setting. – Raphael May 14 '13 at 7:20
• I'm not familiar with the term active waiting (and Google isn't helping). (If you are talking about the work of Kogan and Petrank, that's showing how to turn lock-free algorithms into wait-free.) I added an edit about how you can deal with mutability for lock-freedom in general. – Wandering Logic May 14 '13 at 12:42
• By "active waiting" I mean something like while ( !P ) { noOp(); } doWork(); where noOp may be a sleep or similar. – Raphael May 15 '13 at 19:32
• In the Edit part, you mentioned the technique for making mutable data structures lock-free. As indicated, we copy the entire data structure, make mods to the copy, and then use the CAS primitive. However, how to make the Copy step atomic? It seems to be another difficult problem of atomic snapshot. – hengxin Dec 15 '13 at 9:37
• @hengxin: think of the CAS primitive as a "publish" operator. Before the data structure is published only the thread doing the modifications has access to it. After the data structure is published it is immutable. The copy step does not need to be atomic because the only thing a thread could be copying is a published version, which is immutable. If two threads simultaneously try to mutate, they both copy the same immutable data structure, modify their local copies, and then one of the CAS operations succeeds and the other one fails. The one that fails needs to recopy and update. – Wandering Logic Dec 15 '13 at 12:55