# A Dynamic Distributed Deterministic Load-Balancer for Decentralized Hierarchical Infrastructures
## 5 The \(D^{3}\)-Tree
### Element Insertions and Deletions
#### 5.4.2 Load Balancing  
The load-balancing mechanism guarantees that if there are \(w(v)\) elements in total in the subtree of \(v\) of size \(|v|\) (total number of nodes in the subtree of \(v\) including \(v\)), then after load-balancing each node stores either \(\left\lfloor\frac{w(v)}{|v|}\right\rfloor\) or \(\left\lfloor\frac{w(v)}{|v|}\right\rfloor+1\) elements. The load-balancing cost is \(O(\log N)\), which is verified through experiments. The load-balancing in the subtree of \(v\) is carried out as follows (Algorithm 11). We assume that \(v\) has \(|v|\) nodes in its subtree. A bottom-up computation of the weights in all nodes of the subtree is performed, in order to determine the weight \(w(v)\) of \(v\). Then, the first \(k\) nodes will contain \(\left\lfloor\frac{w(v)}{|v|}\right\rfloor+1\) elements after load-balancing, where \(k=w(v)\bmod|v|\). The remaining \(|v|-k\) nodes will contain \(\left\lfloor\frac{w(v)}{|v|}\right\rfloor\) elements. The redistribution starts from the rightmost node \(w\) of the rightmost bucket \(b\) and it is performed in an in-order fashion. ```
0: BinaryNode node
1: node.ComputeSizeInSubtree();
2: node.ComputeWeightInSubtree();
3: newNodeDensity = node.Weight / node.Size;
4: leftMostLeaf = node.LeftMostLeaf;
5: currentNode = node.RightMostLeaf;
6:whilecurrentNode \(\
eq\) leftMostLeaf do
7: destinationNode = node.FindDestinationNode();
8:if currentNode.Elements \(>\) newNodeDensity then
9: elementsToMove = currentNode.Elements \(-\) newNodeDensity;
10: SplitElements(currentNode, destinationNode, elementsToMove);
11:elseif currentNode.Elements \(<\) newNodeDensity then
12: elementsToMove = newNodeDensity \(-\) currentNode.Elements;
13: tempDestNode = destinationNode;
14:while tempDestNode \(\
eq\) leftMostLeaf AND availableElements \(<\) elementsToMove do
15: availableElements += tempDestNode.Elements;
16: tempDestNode = tempDestNode.FindDestinationNode();
17:endwhile
18: tempElementsToMove = tempDestNode.Elements \(-\) (totalElementsAvailable \(-\) elementsToMove);
19: tempSourceNode = tempDestNode.FindSourceNode();
20:while tempDestNode \(\
eq\) currentNode do
21: SplitElements(tempDestNode, tempSourceNode, tempElementsToMove);
22: tempDestNode = tempSourceNode;
23: tempElementsToMove = tempDestNode.Elements;
24: tempSourceNode = tempSourceNode.FindSourceNode();
25:endwhile
26:endif
27: currentNode = destinationNode;
28:endwhile
```  
**Algorithm 11** Search(LoadBalanceSubtree())
We assume that \(w\) has \(m\) extra elements which must be transferred to other nodes. Hence, node \(w\) has a link to node \(w^{\prime}\) in which the \(m\) additional elements should be inserted. To locate node \(w^{\prime}\), we take into consideration the following cases: (i) if \(w\) is a bucket node, \(w^{\prime}\) is its left node, unless \(w\) is the first node of the bucket and then \(w^{\prime}\) is the bucket representative, (ii) if \(w\) is a leaf, then \(w^{\prime}\) is the left in-order adjacent of \(w\) and (iii) if \(w\) is an internal binary node, then its left in-order adjacent is a leaf, and \(w^{\prime}\) is the last node of its bucket. Having located \(w^{\prime}\), the first \(m\) extra elements of \(w\) are removed from \(w\) and are added to the end of the element queue of \(w^{\prime}\), to preserve the indexing structure of the tree. Then, the ranges of \(w\) and \(w^{\prime}\) are updated, respectively. The case where \(m\) elements must be transferred to node \(w\) from node \(w^{\prime}\) is completely symmetric. In general, the last \(m\) elements of \(w^{\prime}\) are removed from \(w^{\prime}\) and are inserted in the first \(m\) places in the element queue of \(w\). The intriguing part is when \(w^{\prime}\) contains less elements than the \(m\) elements that \(w\) needs. In this case, _dest_ travels towards the leftmost node of the subtree, following the in-order traversal, until \(m\leq\sum_{i=1}^{s}e(u_{i})\), where \(e(u_{i})\) is the number of elements of the \(i-th\) node on the left.