Lock-Free Ziptrees: Towards a self-balancing lock-free binary search tree

Abstract

In this paper we investigate how to implement lock-free binary search tree based on the ziptree invented by [1]. We prove linearisability [2] for insertion operations. The techniques used in this paper are motivated by Harris [3] and [4] in their lock-free linked list implementations.