Colloquium Details
A Sampler of Self-Stabilizing Algorithms
| Author: | Stephen Hedetniemi Clemson University |
|---|---|
| Date: | May 03, 2010 |
| Time: | 15:30 |
| Location: | 120 Deschutes Hall |
| Host: | Art Farley |
Abstract
A network algorithm is an algorithm that runs on a network, each site executing the same program, represented as a set of guarded commands or rules of the form: if (condition) then (action). A network algorithm self-stabilizes if, after a finite amount of time, all boolean conditions become false across the network. Of interest are self-stabilizing algorithms that create a desired state of the network, starting from an arbitrary state. We will survey a number of self-stabilizing algorithms, discussing proof methods, complexity issues, and open problems.