Award Date

8-1-2015

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Ajoy Datta

Second Committee Member

Lawrence Larmore

Third Committee Member

Yoohwan Kim

Fourth Committee Member

Emma Regentova

Fifth Committee Member

Kathryn H. Korgan

Number of Pages

42

Abstract

Constructing BFS trees rooted at each node of a network helps solve many problems. Reliable communication to other nodes is easily managed and metrics such as the network diameter, shortest path between any two nodes, the center, the radius, and others can be easily computed. A traditional way to form a BFS tree from each node is for all nodes to construct their trees in parallel. While this is the fastest way to accomplish this task, it also requires a large amount of network traffic. In this thesis, we present a way to use a token passing algorithm to form a BFS tree from each node in the network within a desired network traffic limit. We will analyze how the algorithm works on several network topologies and determine the amount of tokens necessary to form BFS trees from each node as quickly as possible without stressing the network more than a desirable limit.

Keywords

All Pairs Shortest Path; APSP; BFS Trees; Distributed Computing; Leader Election; Network Diameter

Disciplines

Computer Sciences

File Format

pdf

Degree Grantor

University of Nevada, Las Vegas

Language

English

Rights

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

Download


Share

COinS