Enhancing Fault Tolerance of Distributed R-Tree

Distributed R-trees (DR-trees) are appealing infrastructures for implementing range queries, content based filtering or k-NN structures since they inherit the features of R-trees such as logarithmic height, bounded number of neighbors and balanced shape. However, they are crash-sensitivite since each single crash can potentially break the tree structure connectivity. In this article, we present a fault tolerant approach which exploits replication of non leaf nodes ensuring the tree connectivity in presence of crashes. Our contribution is twofold. First, we enhance the connectivity without modifying the R-tree structure. Second, via extensive simulations we prove that our approach drastically reduces the cost of both message traffic and stabilization time when compared to the original approach proposed in where all nodes of a disconnected subtree are reinserted. Finally, our approach can be easily extended to other crash-sensitive structures.