<p>I've been reading a bit of the literature lately, and have found some rather interesting data-structures.</p>

<p>I have researched various different methods of getting update times down to $\mathcal{O}(1)$ worst-case update time [1-7].</p>

<p>Recently I begun looking into lock-free data-structures, to support efficient concurrent access.</p>

<p><strong>Have any of these worst-case $\mathcal{O}(1)$ update-time techniques been used in the implementation of lock-free data structures?</strong></p>

<p>I ask because; to me, they seem like the obvious practical extension of this "theoretical enhancement".</p>

<hr>

<ol>
<li><p><a href="http://www.sciencedirect.com/science/article/pii/0020019083900996" rel="nofollow noreferrer">Tarjan, Robert Endre. “Updating a Balanced Search Tree in O(1) Rotations.” Information Processing Letters 16, no. 5 (1983): 253 – 257.</a></p></li>
<li><p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.133.4630" rel="nofollow noreferrer">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.</a></p></li>
<li><p><a href="http://dx.doi.org/10.1007/BF00299635" rel="nofollow noreferrer">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.</a></p></li>
<li><p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9433" rel="nofollow noreferrer">Fleischer, Rudolf. A Simple Balanced Search Tree With O(1) Worst-Case Update Time</a></p></li>
<li><p><a href="http://dx.doi.org/10.1016/0020-0190%2894%2900115-4" rel="nofollow noreferrer">Dietz, Paul F, and Rajeev Raman. “A Constant Update Time Finger Search Tree.” Information Processing Letters 52, no. 3 (1994): 147 – 154.</a></p></li>
<li><p><a href="http://dl.acm.org/citation.cfm?id=998223.998229" rel="nofollow noreferrer">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.</a></p></li>
<li><p><a href="http://www.cs.au.dk/~gerth/papers/stoc02.pdf" rel="nofollow noreferrer">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.</a></p></li>
</ol>

<p>FYI: This is a reposting of <a href="https://cs.stackexchange.com/q/2680">Lock-free, constant update-time concurrent tree data-structures?</a></p>

CC BY-SA 3.0
2012-07-19T17:46:12.100Z
[Crossposted on cs.SE](http://cs.stackexchange.com/q/2680/98).
Raphael
CC BY-SA 3.0
2012-07-20T07:03:52.490Z
@Raphael: I mentioned on that question and in this question that it had been crossposted. JeffE recommended I crosspost.
A T
CC BY-SA 3.0
2012-07-20T12:09:22.183Z
Sorry, I did not see the remark at the end.
Raphael
CC BY-SA 3.0
2012-10-04T18:05:19.713Z
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.
vzn
<reference-request><ds.data-structures><time-complexity><tree><concurrency>
Lock-free, constant update-time concurrent tree data-structures?
A T
# Lock-free, constant update-time concurrent tree data-structures?

(Asked by: username_0 on 2012-07-19)

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.](http://www.sciencedirect.com/science/article/pii/0020019083900996)
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.](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.133.4630)
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.](http://dx.doi.org/10.1007/BF00299635)
4. [Fleischer, Rudolf. A Simple Balanced Search Tree With O(1) Worst-Case Update Time](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9433)
5. [Dietz, Paul F, and Rajeev Raman. “A Constant Update Time Finger Search Tree.” Information Processing Letters 52, no. 3 (1994): 147 – 154.](http://dx.doi.org/10.1016/0020-0190%2894%2900115-4)
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.](http://dl.acm.org/citation.cfm?id=998223.998229)
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.](http://www.cs.au.dk/~gerth/papers/stoc02.pdf)

FYI: This is a reposting of [Lock-free, constant update-time concurrent tree data-structures?](https://cs.stackexchange.com/q/2680)

**Tags:** reference-request, ds.data-structures, time-complexity, tree, concurrency

> **Comments:**
> **username_1**: [Crossposted on cs.SE](http://cs.stackexchange.com/q/2680/98).  
> **username_0**: @username_1: I mentioned on that question and in this question that it had been crossposted. JeffE recommended I crosspost.  
> **username_1**: Sorry, I did not see the remark at the end.  
> **username_2**: 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.  

---

## 0 answers

