# A Dynamic Distributed Deterministic Load-Balancer for Decentralized Hierarchical Infrastructures
## 3 Our Contribution  
In this work, we focus on hierarchical tree-based overlay networks that directly support range and more complex queries. We introduce a promising deterministic decentralized structure for distributed data, called \(D^{3}\)-Tree. \(D^{3}\)-Tree is an extension of \(D^{2}\)-Tree [15] that adopts all of its strengths and extends it in two respects: it introduces an enhanced fault-tolerant mechanism, and it can answer efficiently search queries when massive node failures occur. \(D^{3}\)-Tree achieves the same deterministic \(O(\log N)\) worst-case bound as \(D^{2}\)-Tree for the search operations and \(O(\log N)\) amortized bounds for update and load-balancing operations, using an efficient deterministic weight-based load-balancing mechanism, which is general enough to be applied to other hierarchical tree-based structures. Moreover, \(D^{3}\)-Tree answers search queries in \(O(\log N)\) amortized cost under massive node failures. Note that all previous structures provided only empirical evidence of their capability to deal with massive node failures; no previous structure provided a theoretical guarantee for searching in such a case. Our second contribution is an implementation of the \(D^{3}\)-Tree and a subsequent comparative experimental evaluation (cf. Section 7) with its main competitors BATON, BATON\({}^{*}\), and P-Ring. Our experimental study verified the theoretical results (as well as those of the \(D^{2}\)-Tree) and showed that \(D^{3}\)-Tree outperforms other state-of-the-art hierarchical tree-based structures. Furthermore, our experiments demonstrated that \(D^{3}\)-Tree has a significantly small redistribution rate (structure redistributions after node joins/departures), while element load-balancing is rarely necessary. We also investigated the structure's fault tolerance in case of massive node failures and showed that it achieves a significant success rate in element queries. Afterwards, by incorporating this novel balancing scheme into ART (Autonomous Range Tree), the state-of-the-art hierarchical distributed structure presented in [17], we go one step further to achieve sub-logarithmic complexity and propose the ART\({}^{+}\) structure. The outer level of ART\({}^{+}\) is built by grouping clusters of nodes, whose communication cost of query and update operations is \(O(\log_{b}^{2}\log N)\) hops, where the base \(b\) is a double-exponentially power of two and \(N\) is the total number of nodes. Moreover, ART\({}^{+}\) is a fully dynamic and fault-tolerant structure, which supports the join/leave node operations in \(O(\log\log N)\) expected w.h.p number of hops and performs load-balancing in \(O(\log\log N)\) amortized cost. Each cluster node of ART\({}^{+}\) is organized as a \(D^{3}\)-Tree. A comparison of the state-of-the-art decentralized structures with our contribution is given in Table 1.  
As noted earlier, preliminary parts of this work were presented in [18; 19]. In this work, we further contribute, providing additional technical details regarding the key operations of D\({}^{3}\)-Tree; node and element updates, load-balancing, search queries without/with massive node failures. We also provide the proof for Lemma 2 about the amortized search cost in case of massive node failures. Moreover, we include a thorough presentation of the redistribution, load-balancing and extension-contraction operations, omitted in our previously published work. We have also included 11 algorithms in pseudo-code, to clarify the algorithmic process of the most significant operations of our structure. The evaluation of D\({}^{3}\)-Tree is further extended, including additional experiments for (a) the operations of node and element updates, taking into account different values of specific invariants of D\({}^{3}\)-Tree (described in Section 4), and (b) the detailed behaviour of D\({}^{3}\)-Tree in case of massive node failures. The corresponding section also includes a brief presentation of the graphical interface of the D\({}^{3}\)-Tree simulator.