Recent News
Making waves: Undergraduate combines computer science skills, love of water for summer internship
April 9, 2024
Inaugural School of Engineering Teaching Innovation Fellows selected
February 2, 2024
UNM computer scientist wins NSF CAREER Award to optimize supercomputer performance
February 1, 2024
Hand and Machine Lab’s Experimental Clay Exhibition closing celebration Nov. 17
November 15, 2023
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.