Award Date


Degree Type


Degree Name

Master of Science (MS)


Computer Science

First Committee Member

Ajoy Kumar Datta

Number of Pages



The Pivot Interval Routing (PIR) scheme [EGP98] divides the nodes in the network into pivots and clients of the pivots. A pivot acts as a center for the partition of the network formed by its clients. Each node can send messages directly only to a small subset of vertices in its nearby vicinity or to the pivots; An algorithm is called self-stabilizing [Dij74] if, starting from an arbitrary initial state, it is guaranteed to reach a correct state in finite time and with no exterior help. In this thesis, we present a self-stabilizing PIR algorithm. The algorithm starts with no knowledge of the network architecture and, eventually, each node builds its own routing table of size O(n1/2log3/2 n + Deltaupsilon, log n) bits with a total of O(n3/2 log3/2 n) bits. The stabilization time of the algorithm is O&parl0;dn1+logn &parr0; time units, where n is the number of nodes and d is the diameter of the network. (Abstract shortened by UMI.).


General; Interval; Networks; Routing; Scheme; Self; Stabilizing

Controlled Subject

Computer science

File Format


File Size

1945.6 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