Designing efficient algorithms for distributed systems

摘要

Search for efficient algorithms for distributed systems has become an important area of computer science. This research is driven by the need to efficiently process and communicate information generated by the system. In distributed systems, topological information plays an important role in the design of fast algorithms for problems such as routing, broadcasting, and sorting. The central focus of this dissertation is the design and analysis of distributed algorithms for determining topological information in asynchronous communication networks. Specifically, we present distributed algorithms for two generic problems: distributed graph problems and network traversal problems.;Network location and network recognition are two important graph problems in distributed systems. We present unified algorithms for locating centers and medians of asynchronous communication networks. Also, we present both the centralized and decentralized versions of the algorithm. Furthermore, this is the first decentralized algorithm reported in the literature. These results are further extended to weighted networks. In addition, the unified algorithm can also be used to determine other topological parameters such as the diameter, and centroids of distributed networks.;Efficient algorithms for problems such as finding shortest paths, centers, and sorting could be designed if the network topology is known a priori. Towards this end, we solve an open problem of recognizing mesh (grid) structures. We formulate both centralized and decentralized algorithms for recognizing mesh networks. The time and message complexities of the algorithm are O($nsp{1.6}$) and O(e+nlogn), respectively, where n is the number of nodes and e is the number of edges of the graph underlying the network.;Network traversal is a fundamental activity in a distributed system and it has been widely studied in the literature. We present efficient distributed algorithms for depth first traversal of an asynchronous communication network and show the usefulness of this algorithm in deriving efficient solutions to the problems related to network learning.;Finally, we discuss application of some of these algorithms in distributed sensor networks.