# A Dynamic Distributed Deterministic Load-Balancer for Decentralized Hierarchical Infrastructures
## 4 A Weight-Based Load-Balancer  
In this section, we describe a weight-based load-balancing mechanism that is an efficient solution for element updates in hierarchical tree-based structures. All definitions used in this section and throughout this paper, have been compiled in Table 2. The main idea of this mechanism is the almost equal distribution of elements among nodes by making use of _weights_, a metric that shows how uneven is the load among nodes. When the load is uneven, a data migration process is initiated to distribute the elements equally. The method has two steps; (a) first, it provides an efficient and local update of weight information in a tree when elements are added or removed at the leaves, using _virtual weights_, and (b) it provides an efficient load-balancing mechanism which is activated when necessary. \begin{table}
\begin{tabular}{l c c c c c} \hline \hline
**Structures** & **Search** & \multicolumn{2}{c}{**Search with**} & \multicolumn{1}{c}{**Node/Element Updates**} & \multicolumn{1}{c}{**Max. Size of**} \\  & & **Massive Failures** & \multicolumn{1}{c}{**(Update Rout. Tables/**Routing Table**} \\  & & **Theor.** & **Exp.** & **Load-Balancing** & \\ \hline P-Ring & \(O(\log_{d}N)\) & — & Yes & \(\widetilde{O}(d\cdot\log_{d}N)\) & \(O(\log N)\) \\ BATON & \(O(\log N)\) & — & Yes & \(\widetilde{O}(\log N)\) & \(O(\log N)\) \\ BATON\({}^{*}\) & \(O(\log_{m}N)\) & — & Yes & \(\widetilde{O}(m\cdot\log_{m}N)\) & \(O(m\cdot\log_{m}N)\) \\ \(D^{2}\)-Tree & \(O(\log N)\) & — & No & \(\widetilde{O}(\log N)\) & \(O(\log N)\) \\ \(D^{3}\)-**Tree** & \(O(\log N)\) & \(\widetilde{O}(\log N)\) & Yes & \(\widetilde{O}(\log N)\) & \(O(\log N)\) \\ ART & \(\widehat{O}(\log_{b}^{2}\log N)\) & — & Yes & \(\widetilde{O}(m\cdot\log_{m}\log N)\) & \(O(N^{1/4}/\log^{c}N)\) \\
**ART\({}^{+}\)** & \(\widehat{O}(\log_{b}^{2}\log N)\) & \(\widetilde{O}(\log_{b}^{2}\log N)\) & Yes & \(\widetilde{O}(\log\log N)\) & \(O(N^{1/4}/\log^{c}N)\) \\ \hline \hline \end{tabular}  
* \(N\): number of nodes, \(N\): number of cluster nodes, \(d\): order of ring, \(m\): fanout, \(c>0\), \(b\): double-exponentially power of 2, \(\widehat{O}\): expected bound, \(\widehat{O}\): amortized bound, \(\overline{O}\) expected amortized bound.  
\end{table} 
Table 1: Comparison of P-Ring, BATON, BATON\({}^{*}\), \(D^{2}\)-Tree, \(D^{3}\)-Tree, ART and ART\({}^{+}\). More specifically, when an element is added/removed to/from a leaf \(u\) in a tree structure \(\mathcal{T}\), the weights on the path from \(u\) to the root must be updated. This is a costly operation, when it is performed on every element update. Instead of updating weights every time, a new metric is defined, _virtual weight_\(W(v)\). Assume that node \(v\) lies at height \(h\) and its children are \(v_{1},v_{2},\ldots,v_{s}\) at height \(h-1\). \(W(v)\) of \(v\) is defined as the weight stored in node \(v\). In particular, for node \(v\) the following invariants are maintained:  
**Invariant 1**. : \(W(v)>e(v)+(1-\varepsilon_{h})\big{(}\sum_{i=1}^{s}W(v_{i})\big{)}\). **Invariant 2**. : \(W(v)<e(v)+(1+\epsilon^{\prime}_{h})\big{(}\sum_{i=1}^{s}W(v_{i})\big{)}\). where \(\varepsilon_{h}=\epsilon^{\prime}_{h}=\frac{1}{h^{2}}\). The constants \(\varepsilon_{h}\) and \(\epsilon^{\prime}_{h}\) are chosen such that for all nodes the virtual weight will be within a constant factor \(c>1\) of the real weight, i.e., \(\frac{1}{c}\cdot w(v)<W(v)<c\cdot w(v)\). When an update takes place at leaf \(u\), the mechanism traverses the path from \(u\) to the root updating the weights by \(\pm 1\), until node \(z\) is found for which Invariants 1 and 2 hold. Let \(v\) be its child for which either Invariant 1 or 2 does not hold on this path. All weights on the path from \(u\) to \(v\) are recomputed; for each node \(z\) on this path, its weight information is updated by taking the sum of the weights of its children plus the number of elements that \(z\) carries.