𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A superstabilizing spanning tree protocol for a link failure

✍ Scribed by Yoshiaki Katayama; Toshiyuki Hasegawa; Naohisa Takahashi

Publisher
John Wiley and Sons
Year
2007
Tongue
English
Weight
302 KB
Volume
38
Category
Article
ISSN
0882-1666

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A self‐stabilizing protocol is a distributed protocol that can eventually solve the problem (reach a legitimate configuration) even when started from an arbitrary initial (global) configuration. These protocols do not make any assumptions about the initial state, and so can tolerate any transient failures that may occur during the execution of the protocol. Superstabilizing protocols offer an even higher degree of fault tolerance over the superior fault tolerance of self‐stabilizing protocols. A superstabilizing protocol is a self‐stabilizing protocol that has a β€œpassage predicate” that is guaranteed to be satisfied by all of the network configurations that appear during the execution of the protocol from when a failure occurs in a legitimate configuration until restabilization. This paper proposes a superstabilizing protocol for constructing a spanning tree that is tolerant of any single arbitrary link failure. Β© 2007 Wiley Periodicals, Inc. Syst Comp Jpn, 38(14): 41–51, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.20656

πŸ“œ SIMILAR VOLUMES

Cost allocation for a spanning tree
Cost allocation for a spanning tree
✍ A. Claus; D. J. Kleitman πŸ“‚ Article πŸ“… 1973 πŸ› John Wiley and Sons 🌐 English βš– 770 KB

## Abstract The problem of allocating cost in a spanning tree network is considered. A number of possible schemes are surveyed, and critically analyzed. Methods are suggested that are preferred given different emphases among the criteria for such a function.

A Faster Algorithm for the Inverse Spann
A Faster Algorithm for the Inverse Spanning Tree Problem
✍ Ravindra K. Ahuja; James B. Orlin πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 149 KB

In this paper, we consider the inverse spanning tree problem. Given an undi-0 Ε½ 0 0 . rected graph G s N , A with n nodes, m arcs, an arc cost vector c, and a spanning tree T 0 , the inverse spanning tree problem is to perturb the arc cost vector c to a vector d so that T 0 is a minimum spanning tre