# A Dynamic Distributed Deterministic Load-Balancer for Decentralized Hierarchical Infrastructures
## 5 The \(D^{3}\)-Tree
### Node Joins and Departures
#### 5.2.3 Extension-Contraction  
Throughout joins and departures of nodes, the size of buckets can increase undesirably or can decrease so much that some buckets may become empty. Either situations violate the \(D^{3}\)-Tree principle for bucket size \(|b|\):  
\[a_{1}\log N\leq|b|\leq a_{2}\log N \tag{1}\]  
where \(0<a_{1}\leq a_{2}\). ```
1:BinaryNode node
2:node.ComputeSizeInSubtree();
3:newBucketSize = node.Size /2\({}^{h}\);
4:leftMostLeaf = node.LeftMostLeaf;
5:currentNode = node.RightMostLeaf;
6:while currentNode \(\
eq\) leftMostLeaf do
7: currentBucket = currentNode.Bucket;
8: destinationBucket = currentNode.LeftAdjacents[0].Bucket;
9:if currentBucket.Size \(>\) newBucketSize then
10: nodesToMove = currentBucket.Size \(-\) newBucketSize;
11:for i=0; i \(<\) nodesToMove; i++ do
12: Replace(currentNode, currentBucket.FirstNode)
13: Replace(currentNode.LeftAdjacent, currentBucket.Representative);
14: destinationBucket.InsertLast(currentNode.LeftAdjacent);
15: UpdateAllLinks();
16:endfor
17:elseif currentBucket.Size \(<\) newBucketSize then
18: nodesToMove = newBucketSize \(-\) currentBucket.Size;
19: tempDestNode = currentNode.LeftAdjacents[0];
20:while tempDestNode \(\
eq\) leftMostLeaf AND availableNodes \(<\) nodesToMove do
21: availableNodes += tempDestNode.Size;
22: tempDestNode = tempDestNode.LeftAdjacents[0];
23:endwhile
24: tempNodesToMove = tempDestNode.Size \(-\) (totalNodesAvailable \(-\) nodesToMove);
25:while tempDestNode \(\
eq\) currentNode do
26: /*... similar to previous case...*/
27: /* go back to the right, moving nodes */
28:endwhile
29:endif
30: currentNode = currentNode.LeftAdjacents[0];
31:endwhile
```  
**Algorithm 5** RedistributeSubtree()  
The structure guarantees that (1) is always true, by employing two operations on the PBT, _extension_ and _contraction_ (Figure 1). These operations are activated when a redistribution occurs at the root of the PBT and they add one level to the PBT when \(|b|>a_{2}\log N\) or delete one level from the PBT when \(|b|<a_{1}\log N\). The extension (Algorithm 6) is carried out as follows: the last level of the PBT is affected and a new level of leaves, as well as, a new set of buckets are created, using nodes from the old buckets. In particular, each leaf \(u\) and its bucket \(B\) with nodes \(b_{1},b_{2},...,b_{s}\) are replaced by a 2-level binary subtree \(T_{2}\) preserving, at the same time, the in-order adjacency. Thus, the left leaf of \(T_{2}\) is the old leaf \(u\), the root of \(T_{2}\) is the \(i-th\) node of \(b\), where \(i=\left\lceil\frac{|b|}{2}\right\rceil\), the bucket \(B_{1}\) of \(u\) contains nodes \(b_{1},...,b_{i-1}\), the right leaf of \(T_{2}\) is the \((i+1)-th\) node of \(b\) and its bucket \(B_{2}\) contains the remaining nodes of old bucket \(B\), \(b_{i+2},...,b_{s}\). During the process, all in-order adjacency links and father-child links are updated. After the extension has been carried out, leaves and nodes in height \(h=1\) reconstruct their routing tables and all binary nodes update the link to the rightmost leaf of their subtree (the leftmost leaf is not affected). ```
0: BinaryNode Root
1: currentLeaf = Root.LeftMostLeaf;
2:while currentLeaf \(\
eq\) null do
3: grandFather = currentLeaf.Father;
4: oldBucket = currentLeaf.Bucket;
5: i = \(\left\lceil\frac{oldBucket.Size}{2}\right\rceil\);
6: B1 = oldBucket.RemoveNodes(i);
7: newFather = oldBucket.RemoveFirstNode();
8: rightLeaf = oldBucket.RemoveFirstNode();
9: B2 = oldBucket.RemoveRemainingNodes();
10: grandFather.ReplaceChild(currentLeaf,newFather);
11: newFather.SetChildren(currentLeaf, rightLeaf);
12: UpdateInOrderAdjacencyLinks();
13: currentLeaf = currentLeaf.RightAdjacents[0];
14:endwhile
15: UpdateAllLinks();
16: Root.ComputeSizeInSubtree();
```  
**Algorithm 6** PerformExtension()  
The contraction (Algorithm 7) is carried out as follows: the last level of the PBT is deleted and every pair of adjacent buckets is merged into one bucket.