News Archives

Self-stabilizing Algorithms on Tree Networks

December 2, 2004

Date: Thursday December 2, 2004
Time: 11am-12:15pm
Location: Woodward 149

Prof. Fredrik Manne <nfmann@sandia.gov>

Department of Informatics University of Bergen, Bergen, Norway and Sandia National Labs. Albuquerque, NM A distributed system can be modeled as an undirected graph $G=(V,E)$, where $V$ is the set of $n$ systems, or nodes, and $E$ is the set of links, or edges, interconnecting the systems together. In the self-stabilizing algorithmic paradigm, the nodes are the computational units and each node can only see its neighbors and itself, yet the system of simultaneously running algorithms must converge to a global state satisfying some desired property. This is similar to what one might experience in for instance an ad hoc network. Problems that are typically straight-forward to solve using a sequential algorithm often require far more clever approaches in the self-stabilizing paradigm. The advantage of self-stabilizing algorithms is that even if the underlying structure of the graph should change through a fault or if the graph is dynamic in nature, the algorithm will converge to a new legal solution when the underlying graph structure stabilizes. In this presentation we will give an introduction to self-stabilizing algorithms. We will also look at some new results on developing more efficient self-stabilizing algorithms for tree networks.