# A Dynamic Distributed Deterministic Load-Balancer for Decentralized Hierarchical Infrastructures
## 5 The \(D^{3}\)-Tree
### Single Queries with Node Failures  
The problem of searching an element in a network where several nodes have fallen introduces some very intriguing aspects. It can be considered two-dimensional since the search must be successful and cost-effective. A successful search for element \(a\) refers to locating the target node \(z\) for which \(a\in[x_{z},x_{z}^{\prime}]\). An unsuccessful search refers to the cases where (i) \(z\) is unreachable and (ii) there is a path to \(z\), but the search algorithm couldn't follow it to locate \(z\), due to failures of intermediate nodes. Unfortunately, the \(D^{3}\)-Tree predecessor doesn't provide a search algorithm in case of node failures since it doesn't sufficiently confront the structure's fault tolerance. In the following, we present the key features of our search algorithm, mainly through examples, due to the complexity of its implementation. The search procedure is similar to the simple search described in Section 5.3. One difference in horizontal search lies in the fact that if the most distant right adjacent of \(v\) is unreachable, \(v\) keeps contacting its right adjacent nodes by decreasing the step by 1, until it finds node \(q\) which is reachable. If all right adjacents are unreachable, \(v\) contacts its left adjacents, afterwards it tries to contact its children, its father and as a last chance, when all other nodes have failed, it contacts its left/right in-order adjacents and its left/rightmost leaf. Contacting children, in-order adjacents and leaves means changing the search level. In case \(x_{q}^{\prime}<a\) the search continues to the right using the most distant right adjacent of \(q\), otherwise the search continues to the left and \(q\) contacts its most distant left adjacent \(p\) which is in the right of \(v\). If \(p\) is unreachable, \(q\) doesn't decrease the travelling step by 1, but directly contacts its nearest left adjacent (at step = 0) and asks it to search to the left. This improvement reduces the number of messages meant to fail because of the exponential positions of nodes in routing tables and the nature of binary horizontal search. For example, in Figure 2, search starts from \(v_{0}\) and \(v_{8}\) contacts \(v_{7}\) since \(v_{4}\) has fallen. No node contacts \(v_{4}\) from then on, and the number of messages is reduced by 2. A vertical search to locate \(z\) is always initiated between two siblings \(u\) and \(w\), which are both active, or one of them is unreachable, as shown in Figure 3 where the left sibling \(u\) is active and \(w\), the right one, is unreachable. In both cases, first, we search into the subtree of the active sibling. Next, we contact the common ancestor, and then, if the other sibling is unreachable, the active sibling tries to reach its corresponding child (right child for left sibling and left child for right sibling). When the child is found, the search is forwarded to its subtree. Figure 2: Example of binary horizontal search with node failures. We assume (w.l.o.g.) that the left sibling \(u\) is active and \(w\), the right one, is unreachable, as shown in Figure 3. First \(u\) contacts its rightmost leaf \(y\) of its subtree. If \(y\) is reachable and \(x_{y}>a\) or if \(y\) is unreachable, then an ordinary top-down search from node \(u\) is initiated to find \(z\). If a node in the searching path is unreachable, a mechanism described below is activated to contact its children. Otherwise, if \(x_{y}^{\prime}<a\), node \(z\) is in the bucket of \(y\), or in its right in-order adjacent (this is also the common ancestor of \(u\) and \(w\)), or in the left subtree of \(w\). In general, when node \(u\) wants to contact the left (right) child of unreachable node \(w\), the contact is accomplished through the routing table of its own left (right) child. If its child is unreachable, (Figure 3), then \(u\) contacts its father \(u_{f}\) and \(u_{f}\) contacts the father of \(w\), \(w_{f}\), using Lemma 1(i).