Self-Stabilizing Balancing Algorithm for Containment-Based Trees

Download Now Date Added: Dec 2012
Format: PDF

Containment-based trees encompass various handy structures such as B+-trees, R-trees and M-trees. They are widely used to build data indexes, range-queryable overlays, publish/subscribe systems both in centralized and distributed contexts. In addition to their versatility, their balanced shape ensures an overall satisfactory performance. Recently, it has been shown that their distributed implementations can be fault-resilient. However, this robustness is achieved at the cost of unbalancing the structure. While the structure remains correct in terms of search ability, its performance can be significantly decreased. In this paper, the authors propose a distributed self-stabilizing algorithm to balance containment-based trees.