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.

FYI: This is a reposting of Lock-free, constant update-time concurrent tree data-structures?

  • $\begingroup$ Crossposted on cs.SE. $\endgroup$
    – Raphael
    Commented Jul 19, 2012 at 17:46
  • $\begingroup$ @Raphael: I mentioned on that question and in this question that it had been crossposted. JeffE recommended I crosspost. $\endgroup$
    – A T
    Commented Jul 20, 2012 at 7:03
  • $\begingroup$ Sorry, I did not see the remark at the end. $\endgroup$
    – Raphael
    Commented Jul 20, 2012 at 12:09
  • $\begingroup$ can you elaborate on what you mean by "lock free"? it is possible for a datastructure to minimize locking by locking subelements instead of the entire datastructure. $\endgroup$
    – vzn
    Commented Oct 4, 2012 at 18:05


Your Answer

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