Book chapter
Building Self-stabilizing Overlay Networks with the Transitive Closure Framework
Stabilization, Safety, and Security of Distributed Systems, pp.62-76
Lecture Notes in Computer Science, Springer Berlin Heidelberg
2011
DOI: 10.1007/978-3-642-24550-3_7
Abstract
Overlay networks are expected to operate in hostile environments, where node and link failures are commonplace. One way to make overlay networks robust is to design self-stabilizing overlay networks, i.e., overlay networks that can handle node and link failures without any external supervision. In this paper, we first describe a simple framework, which we call the Transitive Closure Framework (TCF), for the self-stabilizing construction of an extensive class of overlay networks. Like previous self-stabilizing overlay networks, TCF permits node degrees to grow to Ω(n), independent of the maximum degree of the target overlay network. However, TCF has several advantages over previous work in this area: (i) it is a “framework” and can be used for the construction of a variety of overlay networks, not just a particular network, (ii) it runs in an optimal number of rounds for a variety of overlay networks, and (iii) it can easily be composed with other non-self-stabilizing protocols that can recover from specific bad initial states in a memory-efficient fashion. We demonstrate the power of our framework by deriving from TCF a simple self-stabilizing protocol for constructing Skip+ graphs (Jacob et al., PODC 2009) which presents optimal convergence time from any configuration, and requires only a O(1) factor of extra memory for handling node Joins.
Details
- Title: Subtitle
- Building Self-stabilizing Overlay Networks with the Transitive Closure Framework
- Creators
- Andrew Berns - University of IowaSukumar Ghosh - Department of Computer Science, The University of Iowa, Iowa City, USASriram V. Pemmaraju - Department of Computer Science, The University of Iowa, Iowa City, USA
- Resource Type
- Book chapter
- Publication Details
- Stabilization, Safety, and Security of Distributed Systems, pp.62-76
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/978-3-642-24550-3_7
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 2011
- Academic Unit
- Computer Science
- Record Identifier
- 9984259426002771
Metrics
2 Record Views