# A Dynamic Distributed Deterministic Load-Balancer for Decentralized Hierarchical Infrastructures
## 2 Related Work  
Extensive work has been done to support search and update techniques in distributed data essential operations in decentralized networks. In general, decentralized systems can be classified into two broad categories: Distributed Hash Table (DHT)-based systems and tree-based systems. Examples of the former, which constitute the majority, include Chord, CAN, Pastry, Symphony, Tapestry [2], and P-Ring [3]. DHT-based systems generally support exact match queries well and use (successfully) probabilistic methods to distribute the workload among nodes equally. Since hashing destroys the ordering on keys, DHT-based systems typically do not possess the functionality to support straightforwardly range queries, or more complex queries based on data ordering (e.g., nearest-neighbour and string prefix queries). Some efforts towards addressing range queries have been made in [4; 5], getting however approximate answers and also making exact searching highly inefficient. Pagoda [6] achieves constant node degree but has polylogarithmic complexity for the majority of operations. SHELL [7] maintains large routing tables of \(O(\log^{2}N)\) space complexity, but achieves constant amortized cost for the majority of operations. Both are complicated hybrid structures and their practicality (especially concerning fault-tolerant operations) is questionable. P-Ring [3] is a fully distributed and fault-tolerant system that supports both exact match and range queries, achieving \(O(\log_{d}N+k)\) range search performance (\(d\) is the _order_ (Maximum fanout of the hierarchical structure on top of the ring. At the lowest level of the hierarchy, each node maintains a list of its first \(d\) successors in the ring.) of the ring and \(k\) is the answer size). It also provides load-balancing by maintaining a load imbalance factor of at most \(2+\epsilon\) of a stable system, for any given constant \(\epsilon>0\), and has a stabilization process for fixing inconsistencies caused by node failures and updates, achieving an \(O(d\cdot\log_{d}N)\) performance for load-balancing. FMapper [8] is a novel distributed read mapper employing asynchronous I/O and parallel computations between different compute elements of the core groups and uses dynamic task scheduling and asynchronous data transfers. However, this highly scalable structure supports optimal scheduling and doesn't investigate either range query, since it's a hashed-based system, nor the load balancing performance of the whole cluster. Tree-based systems are based on hierarchical structures. As a result, they support range queries more naturally and efficiently and a broader range of operations since they maintain the ordering of data. On the other hand, they lack the simplicity of DHT-based systems, and they do not always guarantee data locality and load balancing in the whole system. Important examples of such systems include Family Trees [2], BATON [9], BATON\({}^{*}\)[10], SPIS [11] and Skip List-based schemes like Skip Graphs (SG), NoN SG, SkipNet (SN), Deterministic SN, Bucket SG, Skip Webs, Rainbow Skip Graphs (RSG) and Strong RSG [2] that use randomized techniques to create and maintain the hierarchical structure. We should emphasize that w.r.t. load-balancing, the solutions provided in the literature are either heuristics or provide expected bounds under certain assumptions or amortized bounds but at the expense of increasing the memory size per node. In particular, in BATON [9], a decentralized overlay is provided with load-balancing based on data migration. However, their \(O(\log N)\) amortized bound (\(N\) is the number of nodes in the network) is valid only subject to a probabilistic assumption about the number of nodes taking part in the data migration process. Thus it is an amortized expected bound. Moreover, its successor BATON\({}^{*}\), exploits the advantages of higher _fanout_ (number of children per node), to achieve reduced search cost of \(O(\log_{m}N)\), where \(m\) is the _fanout_.