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

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

• – Raphael Jul 19 '12 at 17:46
• @Raphael: I mentioned on that question and in this question that it had been crossposted. JeffE recommended I crosspost. – A T Jul 20 '12 at 7:03
• Sorry, I did not see the remark at the end. – Raphael Jul 20 '12 at 12:09
• 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 Oct 4 '12 at 18:05