Self-Stabilizing Prefix Tree Based Overlay Networks

Eddy Caron 1 Ajoy K. Datta 2 Cédric Tedeschi 3 Franck Petit 4
1 AVALON - Algorithms and Software Architectures for Distributed and HPC Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
3 MYRIADS - Design and Implementation of Autonomous Distributed Systems
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
4 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : In this paper, we focus on making tries self-stabilizing over such platforms, and propose a self-stabilizing maintenance algorithm for a prefix tree using a message passing model. The proof of self-stabilization is provided, and simulation results are given, to better capture its performances. Still based on simulations, we provide evidences that the protocol, beyond its capacity to repair the structure, can significantly improve the system’s availability, even when the system is not yet stabilized.
Complete list of metadatas
Contributor : Franck Petit <>
Submitted on : Thursday, July 21, 2016 - 9:50:52 AM
Last modification on : Monday, August 12, 2019 - 12:16:02 PM



Eddy Caron, Ajoy K. Datta, Cédric Tedeschi, Franck Petit. Self-Stabilizing Prefix Tree Based Overlay Networks. International Journal of Foundations of Computer Science, World Scientific Publishing, 2016, 27 (5), pp.607-630. ⟨10.1142/S0129054116500192⟩. ⟨hal-01347457⟩



Record views