A practical study of self-stabilization for prefix-tree based overlay networks

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 (a.k.a., tries), 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 simula- tion 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.