Master of Science in Computer Science
First Committee Member
Second Committee Member
Third Committee Member
Fourth Committee Member
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
Spencer, Michael, "Constructing BFS Trees Using Tokens To Balance Speed and Network Traffic" (2015). UNLV Theses, Dissertations, Professional Papers, and Capstones. 2500.