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.

  • 2
    $\begingroup$ Please consider adding links to the papers as a courtesy to people who want to investigate your issue. $\endgroup$
    – Raphael
    Jul 17, 2012 at 14:26
  • 3
    $\begingroup$ Okay, added in links to respective articles. $\endgroup$
    – A T
    Jul 18, 2012 at 5:21
  • 1
    $\begingroup$ I suggest reposting at cstheory.SE (with a link back here) if you don't get a useful response soon. $\endgroup$
    – JeffE
    Jul 18, 2012 at 14:59
  • 1
    $\begingroup$ Thanks for the suggestion. I have reposted: Lock-free, constant update-time concurrent tree data-structures? $\endgroup$
    – A T
    Jul 19, 2012 at 15:56
  • $\begingroup$ 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. $\endgroup$
    – Reza
    Feb 1, 2013 at 1:44

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

  • $\begingroup$ 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. $\endgroup$
    – Raphael
    May 14, 2013 at 7:20
  • $\begingroup$ 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. $\endgroup$ May 14, 2013 at 12:42
  • $\begingroup$ By "active waiting" I mean something like while ( !P ) { noOp(); } doWork(); where noOp may be a sleep or similar. $\endgroup$
    – Raphael
    May 15, 2013 at 19:32
  • $\begingroup$ 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. $\endgroup$
    – hengxin
    Dec 15, 2013 at 9:37
  • 1
    $\begingroup$ @Raphael: Two differences between optimistic compare-and-swap and other kinds of "active waiting" are that a thread never has to wait for other thread to affirmatively "do" anything, and a thread can only get delayed if some other thread has made progress. The term "active waiting" is applied, I think, more often to situations where those guarantees do not hold. $\endgroup$
    – supercat
    Mar 27, 2014 at 23:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.