Award Date


Degree Type


Degree Name

Master of Science in Computer Science


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



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.


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


Computer Sciences

File Format


Degree Grantor

University of Nevada, Las Vegas




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