Building self-stabilizing overlay networks with the transitive closure framework

Andrew Berns; Sukumar Ghosh; Sriram V. Pemmaraju

doi:10.1016/j.tcs.2013.02.021

Back

Building self-stabilizing overlay networks with the transitive closure framework

Journal article

Open access

Peer reviewed

Building self-stabilizing overlay networks with the transitive closure framework

Andrew Berns, Sukumar Ghosh and Sriram V. Pemmaraju

Theoretical computer science, Vol.512, pp.2-14

11/11/2013

DOI: 10.1016/j.tcs.2013.02.021

Files and links (1)

url

https://doi.org/10.1016/j.tcs.2013.02.021View

Published (Version of record) Open Access

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 algorithms for overlay networks, TCF permits intermediate node degrees to grow to Omega(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 (e.g. LINEAR, SKIP+), 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 [R. Jacob, A. Richa, C. Scheideler, S. Schmid, H. Taubig, A distributed polylogarithmic time algorithm for self-stabilizing skip graphs, in: PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computing, ACM, New York, NY, USA, 2009, pp. 131-1401 that guarantees optimal convergence time from any configuration. (C) 2013 Elsevier B.V. All rights reserved.

Computer Science

Computer Science, Theory & Methods

Science & Technology

Technology

Details

Title: Subtitle: Building self-stabilizing overlay networks with the transitive closure framework
Creators: Andrew Berns - University of Iowa
Sukumar Ghosh - University of Iowa
Sriram V. Pemmaraju - University of Iowa
Resource Type: Journal article
Publication Details: Theoretical computer science, Vol.512, pp.2-14
DOI: 10.1016/j.tcs.2013.02.021
ISSN: 0304-3975
eISSN: 1879-2294
Publisher: Elsevier
Number of pages: 13
Language: English
Date published: 11/11/2013
Academic Unit: Computer Science
Record Identifier: 9984259427102771

Metrics

27 Record Views

13 Times Cited - Web of Science