A self-stabilizing interval routing scheme in general networks
type: CreativeWork
description: 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.).
abstract: 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.).
author: Bein, Doina
language: English
date published: 2001-01-01T08:00:00Z
date modified: 2026-07-24T05:25:18Z
provider: University of Nevada - Las Vegas
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: University of Nevada, Las Vegas

PropertyValue
property ID: DOI
value: 10.25669/s6w4-emmp