Design and analysis of distributed network algorithms in fixed and changing topology
Jong-Won Choe · 1992
A graph traversal technique is a certain pattern of 'visiting' nodes of a graph. Many special traversal techniques have been applied to solve graph related problems. For example, the depth first search technique has been used for finding strongly connected components of a directed graph or biconnected components of a general graph. These two tasks have important applications in computer networks. Strongly connected components can be used in order to detect directed cycles in communication paths, which may lead to deadlock. Biconnected components may be used to check whether the failure of one node may or may not disconnect the network. A resilient algorithm in changing topology is a distributed algorithm that can function correctly in spite of changing network conditions. In this thesis, we present two different resilient distributed depth first search algorithms and analyze their message and time complexities. To improve the efficiency of the existing distributed depth first search algorithms in fixed topology, we present a more efficient distributed depth first search algorithm using the concept of 'unvisited node set'. Finally, we present a distributed algorithm for minimum weight directed spanning tree in changing topology, which is based on the Humblet's algorithm in fixed topology.