The hyperring: a low-congestion deterministic data structure for distributed environments
Baruch Awerbuch, Christian Scheideler · 2004
Abstract In this paper we study the problem of designing searchableconcurrent data structures with performance guarantees that can be used in a distributed environment where dataelements are stored in a dynamically changing set of nodes. Searchable data structures are data structures that providethree basic operations: Insert, Delete, and Search. In addition to searching for an exact match, we demand thatfor a data structure to be called "searchable", Search also has to be able to search for the closest successor or predecessorof a data item. Such a property has a tremendous advantage over just exact match, because it would allow to implementmany data base applications. We are interested in finding a searchable concurrentdata structure that has (1) a low degree, (2) requires a small amount of work for Insert and Delete operations, and(3) is able to handle concurrent search requests with low congestion and dilation.We present the first deterministic concurrent data structure, called Hyperring, that can fulfill all of these objectivesin a polylogarithmic way. In fact, the Hyperring has a degree of O(log n), requires O(log3 n) work for Insert and Deleteoperations, and can handle concurrent search requests to random destinations, one request per node, with congestionand dilation O(log n) w.h.p. Most of the previous solutions for distributed environments are not searchable (in our sense) but only provide exact lookup, and those that are searchable do not have proofs about the congestion caused by concurrent search requests. 1 Introduction A searchable data structure has to provide three basicoperations: Insert(d), Delete(name), and Search(name). Insert(d) inserts a data item d with some name intothe structure,