Wait-Free Updates and Range Search Using Uruv
Authors: Gaurav Bhardwaj, Bapi Chatterjee, Abhay Jain, Sathya Peri
Description: CRUD operations, along with range queries make a highly useful abstract data type (ADT), employed by many dynamic analytics tasks. Despite its wide applications, to our knowledge, no fully wait-free data structure is known to support this ADT. In this paper, we introduce Uruv, a proactive linearizable and practical wait-free concurrent data structure that implements the ADT mentioned above. Structurally, Uruv installs a balanced search index on the nodes of a linked list. Uruv is the first wait-free and proactive solution for concurrent Btree. Experiments show that Uruv significantly outperforms previously proposed lock-free Btrees for dictionary operations and a recently proposed lock-free method to implement the ADT mentioned above.