A Practical Study of Self-Stabilization for Prefix-Tree Based Overlay Networks

Vlad Acretoaie 1 Eddy Caron 1, 2 Cédric Tedeschi 3
1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous 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
Abstract : Service discovery is crucial in the development of fully decentralized computational grids. Among the significant amount of work produced by the convergence of peer-to-peer (P2P) systems and grids, a new kind of overlay networks, based on prefix trees, has emerged. In particular, the Distributed Lexicographic Placement Table (DLPT) approach is a decentralized and dynamic service discovery service. Fault-tolerance within the DLPT approach is achieved through best-effort policies relying on formal self-stabilization results. Self-stabilization means that the tree can become transiently inconsistent, but is guaranteed to autonomously converge to a correct topology after arbitrary crashes, in a finite time. However, during convergence, the tree may not be able to process queries correctly. In this paper, we present some simulation results having several objectives. First, we investigate the interest of self-stabilization for such architectures. Second, we explore, still based on simulation, a simple Time-To-Live policy to avoid useless processing during convergence time.
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/inria-00474376
Contributor : Cédric Tedeschi <>
Submitted on : Monday, April 19, 2010 - 6:40:07 PM
Last modification on : Friday, November 16, 2018 - 1:38:11 AM
Long-term archiving on : Tuesday, September 28, 2010 - 12:05:25 PM

Files

RR-7252.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00474376, version 1

Citation

Vlad Acretoaie, Eddy Caron, Cédric Tedeschi. A Practical Study of Self-Stabilization for Prefix-Tree Based Overlay Networks. [Research Report] RR-7252, INRIA. 2010, pp.15. ⟨inria-00474376⟩

Share

Metrics

Record views

643

Files downloads

253