Skip to Main content Skip to Navigation
Reports

Self-Stabilizing Balancing Algorithm for Containment-Based Trees

Abstract : 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. Re- cently, it has been shown that their distributed implementations can be fault-resilient. However, this robustness is achieved at the cost of un-balancing the structure. While the structure remains correct in terms of searchability, its performance can be significantly decreased. In this paper, we propose a distributed self-stabilizing algorithm to balance containment-based trees.
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-00765005
Contributor : Anissa Lamani <>
Submitted on : Thursday, December 13, 2012 - 11:22:50 PM
Last modification on : Tuesday, January 14, 2020 - 1:08:02 PM
Long-term archiving on: : Thursday, March 14, 2013 - 3:55:18 AM

Files

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00765005, version 1
  • ARXIV : 1212.3418

Citation

Evangelos Bampas, Anissa Lamani, Franck Petit, Mathieu Valero. Self-Stabilizing Balancing Algorithm for Containment-Based Trees. [Technical Report] 2012. ⟨hal-00765005⟩

Share

Metrics

Record views

527

Files downloads

470