Award Date


Degree Type


Degree Name

Master of Science (MS)


Computer Science

First Committee Member

Ajoy Kumar Datta

Number of Pages



Network orientation is the problem of assigning different labels to the edges at each processor, in a globally consistent manner. A self-stabilizing protocol guarantees that the system will arrive at a legitimate state in finite time, irrespective of the initial state of the system. Two deterministic distributed network orientation protocols on arbitrary rooted, asynchronous networks are proposed in this work. Both protocols set up a chordal sense of direction in the network. The protocols are self-stabilizing, meaning that starting from an arbitrary state, the protocols are guaranteed to reach a state in which every processor has a valid node label and every link has a valid edge label. The first protocol assumes an underlying depth-first token circulation protocol; it orients the network as the token is passed among the nodes and stabilizes in O(n) steps after the token circulation stabilizes, where n is the number of processors in the network. The second protocol is designed on an underlying spanning tree protocol and stabilizes in O(h) time, after the spanning tree is constructed, where h is the height of the spanning tree. Although the second protocol assumes the existence of a spanning tree of the rooted network, it orients all edges--both tree and non-tree edges--of the network.


Algorithms; Arbitrary; Networks; Networks; Orientation; Rooted; Self; Stabilizing

Controlled Subject

Computer science

File Format


File Size

1136.64 KB

Degree Grantor

University of Nevada, Las Vegas




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 and include clear identification of the work, preferably with URL.


IN COPYRIGHT. For more information about this rights statement, please visit