Self-stabilizing distributed algorithms for acyclic graphs

A self-stabilizing distributed system is a network of processors, which when started from an arbitrary and possibly illegal state, always returns to a legal state in a finite number of steps. Two self-stabilizing protocols for distributed systems are presented in this thesis. The first protocol topologically sorts the processors in a distributed system of directed acyclic graph (DAG) topology and uses this information to build a shortest path routing table in each node in the system to all accessible nodes from that node. The second protocol determines the rank of the individual processors in a distributed tree network based on the values possessed by them. Due to the self-stabilizing nature of these protocols the system can withstand transient errors and recover automatically from them.

Name thesis:degree_name

Master of Science (MS)

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

University of Nevada, Las Vegas

Year

1994

Author dc:creator

• Natarajan, Viruthagiri

Statement dc:rights

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

Language dc:language

English

Identifier

https://oasis.library.unlv.edu/rtds/386

OAI identifier oai:identifier

oai:oasis.library.unlv.edu:rtds-1385