Date of Award

2006

Publication Type

Master Thesis

Degree Name

M.Sc.

Department

Computer Science

Keywords

Computer Science.

Rights

info:eu-repo/semantics/openAccess

Abstract

The notion of self-stabilization was first proposed by Dijkstra [37, 38].A system is self-stabilizing if, starting at any state, possibly illegitimate, it eventually converges to a legitimate state in finite time. In this thesis, we are proposing a self-stabilizing algorithm for 3-edge-connectivity of an asynchronous distributed model of computation. This is the first ever self-stabilizing algorithm in the literature for detecting the 3-edge-connected components. It is applicable on a depth-first tree of the network. The result is kept 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. Assuming that the depth-first search algorithm has stabilized, the system with n processors requires O( n2) moves to determine all the 3-edge-connected components in a way such that, for each component, the information is available at one processor only. Stabilization of this phase is followed by another phase of O(n2) moves which, in the legitimate state, lets all other processors detect their respective components. (Abstract shortened by UMI.)Dept. of Computer Science. Paper copy at Leddy Library: Theses & Major Papers - Basement, West Bldg. / Call Number: Thesis2006 .S25. Source: Masters Abstracts International, Volume: 45-01, page: 0364. Thesis (M.Sc.)--University of Windsor (Canada), 2006.

Download

Share

COinS