Award Date

1-1-2006

Degree Type

Thesis

Degree Name

Master of Science (MS)

Department

Computer Science

First Committee Member

Ajoy K. Datta

Number of Pages

57

Abstract

A self-stabilizing system has the ability to recover from an arbitrary (possibly faulty) state to a normal state without any manual intervention. A self-stabilizing algorithm does not require any initialization. Starting from an arbitrary state, it is guaranteed to satisfy its specification in finite number of steps; We propose a self-stabilizing distributed sorting algorithm on an oriented linear network with n nodes. Each node holds some initial value(s) drawn from an arbitrary set. We assume that we start with at most k items in the network. Each node has a local memory whose space is restricted to O(k * L ) where L is the maximum number of bits to store one item. A node may collect more than one value during the process of sorting. The stabilizing time for sorting is O(n) rounds where a round is the duration for all the enabled processes to execute at least one enabled step. We claim that our algorithm is self-stabilizing for the following reasons:;If any node starts in a faulty state (meaning its value is not sorted with respect to its neighbors), the algorithm guarantees that the node will reach the legitimate state (where a legitimate state is a state in which the values are in sorted order) in a finite amount of time, and will remain in the legitimate state until another fault occurs. Each node repeatedly communicates with its neighbors to check if the values of its neighbors are sorted with respect to its own value. If the values are not in order, either the node or one of its neighbors will eventually be enabled to execute so that in finite amount of time the values will be sorted.

Keywords

Linear; Networks; Self; Sorting; Stabilizing

Controlled Subject

Computer science

File Format

pdf

File Size

1484.8 KB

Degree Grantor

University of Nevada, Las Vegas

Language

English

Permissions

If you are the rightful copyright holder of this dissertation or thesis and wish to have the full text removed from Digital Scholarship@UNLV, please submit a request to digitalscholarship@unlv.edu and include clear identification of the work, preferably with URL.

Rights

IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Download


COinS