# A Dynamic Distributed Deterministic Load-Balancer for Decentralized Hierarchical Infrastructures
## 5 The \(D^{3}\)-Tree
### Node Joins and Departures  
#### 5.2.1 Handling Node Updates  
When a node \(z\) makes a join request (Algorithm 1) to \(v\), \(v\) forwards the request to an adjacent leaf \(u\). If \(v\) is a binary node, the request is forwarded to the left adjacent node, w.r.t. the in-order traversal, which is definitely a leaf (unless \(v\) is a leaf itself). In case \(v\) is a bucket node, the request is forwarded to the bucket representative, which is a leaf. Then, node \(z\) is added to the doubly linked list of the bucket represented by \(u\). In node joins, we make the simplification that the new node is clear of elements.  
```
0: initialNode
1:if initialNode is BucketNode then
2: initialNode.Representative.Join(newNode);
3:elseif initialNode is InternalBinaryNode then
4: initialNode.LeftInOrderAdjacent.Join(newNode);
5:elseif initialNode is Leaf then
6: mostLoadedNode = initialNode.FindMostLoaded();
7: mostLoadedNode = AcceptAsAdjacent(newNode);
8: SplitData(mostLoadedNode, newNode);
9:endif
```  
**Algorithm 1**Join (Node newNode)  
It could be entered anywhere in the bucket, such as the first, the last, or an intermediate node, but we prefer to place it after the most loaded node of the bucket. Thus, the load is shared, and the new node stores half of the elements of the most loaded node. Finally, the left and right adjacents of the newly inserted node update their links to the previous and next node, and \(z\) creates new links to those nodes.  
When a node \(v\) leaves the network, it is replaced by an existing node, to preserve the in-order adjacency. All navigation data are copied from the departing node \(v\) to the replacement node, along with the elements of \(v\). If \(v\) is an internal binary node, then it is replaced by its right adjacent node, which is a leaf and which in turn is replaced by the first node \(z\) in its bucket. On the other hand, if \(v\) is a leaf, it is directly replaced by \(z\).  
If the departing node belongs to a bucket, no replacement occurs, but simply all stored elements of \(v\) are copied to the previous node of \(v\) (or to the next node if the last does not exist). Then \(v\) is free to depart.  
After a node join or departure, the modified weight-based mechanism is activated and updates the sizes by \(\pm 1\) on the path from leaf \(u\) to the root (Algorithm 2), as long as the defined Invariants 1 or 2 do not hold. When the first node \(w\) is accessed for which Invariants 1 and 2 hold, the nodes in the subtree of its child \(q\) in the path, have their sizes recomputed (Algorithm 3).  
```
1:currentNode = leaf;
2:while currentNode.Father \(\
eq\) null do
3:if operation == NodeJoin then
4: currentNode.Father.Size\(++\);
5:else if operation == NodeDeparture then
6: currentNode.Father.Size\(--\);
7:endif
8: /* if Invariant 1 OR Invariant 2 do not hold */
9:if currentNode.Father.Size \(\leq\) minSize OR currentNode.Father.Size \(\geq\) maxSize then
10: currentNode = currentNode.Father;
11:else
12:return currentNode;
13:endif
14:endwhile
15:return Root;
```  
**Algorithm 2** UpdateVirtualSize (BinaryNode leaf, NodeUpdate operation)  
```
1:if node is Leaf then
2: node.Size = node.Bucket.Size;
3:else
4: node.LeftChild.ComputeSizeInSubtree();
5: node.RightChild.ComputeSizeInSubtree();
6: node.Size = node.LeftChild.Size + node.RightChild.Size;
7: node.minSize = (1 - \(e_{h}\)) * node.Size;
8: node.maxSize = (1 + \(e_{h}\)) * node.Size;
9:endif
```  
**Algorithm 3** ComputeSizeInSubtree ()  
Afterwards, the mechanism traverses the path from leaf \(u\) to the root, in order to find the first node (if such a node exists) for which Invariant 4 is violated (Algorithm 4) and performs a redistribution in its subtree.