A Lock-free Binary Trie

A binary trie is a sequential data structure for a dynamic set on the universe \0, , u-1\ supporting Search with O (1) worst-case step complexity, and Insert, Delete, and Predecessor operations with O (u) worst-case step complexity. We give a wait-free implementation of a relaxed binary trie, using read, write, CAS, and (u) -bit AND operations. It supports all operations with the same worst-case step complexity as the sequential binary trie. However, Predecessor operations may not return a key when there are concurrent update operations. We use this as a component of a lock-free, linearizable implementation of a binary trie. It supports Search with O (1) worst-case step complexity and Insert, Delete and Predecessor with O (c² + u) amortized step complexity, where c is a measure of the contention. A lock-free binary trie is challenging to implement as compared to many other lock-free data structures because Insert and Delete operations perform a non-constant number of modifications to the binary trie in the worst-case to ensure the correctness of Predecessor operations.