#NumberTR-PDS-2004-001

#Title
Self-Stabilizing Spanning Tree Algorithm With a New Design Methodology

#Author
Vijay K. Garg
Anurag Agarwal

#Abstract
  Maintaining spanning trees in a distributed fashion is central to many
  networking applications. In this paper, we propose a self-stabilizing
  algorithm for maintaining a spanning tree in a distributed fashion for a
  completely connected topology. Our algorithm requires a node to process O(1)
  messages on average in one cycle as compared to previous algorithms which need
  to process messages from every neighbor, resulting in O(n) work in a
  completely connected topology. Our algorithm also stabilizes faster than the
  previous approaches. Our approach demonstrates a new methodology which uses
  the idea of core and non-core states for developing
  self-stabilizing algorithms. The algorithm is also useful in security related
  applications due to its unique design.

#Bib
@techreport{TR-PDS-2004-001,
  author =   "Vijay K. Garg and Anurag Agarwal",
  title =   "Self-Stabilizing Spanning Tree Algorithm with a new design methodology",
  instituition = "The University of Texas at Austin",
  year =   "2004",
  number =  "TR-PDS-2004-001",
  note =  "available via ftp or WWW at maple.ece.utexas.edu
    as technical report TR-PDS-2004-001"
}