Title: A Self-Stabilizing Algorithm For 3-Edge-Connectivity

Speaker: Abu Sayeed Saifullah

Time: 3:00PM - 4:00 PM, Nov 17, 2006

Place: CSE 404

ABSTRACT:

The notion of self-stabilization was first proposed by Dijkstra. A system is self-stabilizing if, starting at any state, possibly illegitimate, it eventually converges to a legitimate state in finite time. The adoption of self-stabilization as an approach to fault-tolerant behavior has received considerable research interest over the last decade. In this seminar, we propose a self-stabilizing algorithm for 3-edge-connectivity of an asynchronous distributed model of computation. The algorithm is applicable on a depth-first tree of the network. The result is available in a distributed fashion in the sense that, upon stabilization of the system, each processor knows all other processors that are 3-edge-connected to it. Until now, this is the only protocol to compute all the 3-edge-connected components in the context of self-stabilization. The algorithm stabilizes in two phases: each phase requires O(h) rounds assuming that the preceding phase has stabilized, where h is the height of the depth-first tree. For a system with n processors, the space complexity is O(nh log d) bits per processor, where d is an upper bound on the degree of a processor.