CCF-BSF: AF:Small: Time-Message Tradeoffs in Distributed Algorithms

University Of Houston, Houston TX

Investigators

Abstract

Real-world distributed communication networks such as the Internet, peer-to-peer networks, ad hoc wireless and sensor networks as well as data center networks used for large-scale data processing are an integral part of today's digital society. Distributed/decentralized algorithms underlie the efficient operation of these networks, e.g., distributed shortest paths algorithms are used for routing in the Internet, and distributed graph algorithms are used for finding communities in social networks. Hence, designing and analyzing efficient distributed algorithms is an important research task which will lead to faster and more resource-efficient performance in real-world networks. To address the more realistic situations, this project will aim to design distributed algorithms which simultaneously optimize the (1) running time and (2) number of messages. This research will help in the design of efficient and scalable distributed algorithms with provable performance guarantees. It can impact algorithm design in peer-to-peer and ad hoc wireless sensor networks, and distributed processing of large-scale data. The PI plans to develop a new course and a textbook on distributed network algorithms that is closely related to the research proposed above. University of Houston is a designated Hispanic serving public Tier 1 research institution and the PI will make efforts to involve minority and underrepresented students in research. Two fundamental performance measures of a distributed algorithm that determine its efficiency are the running time and the number of messages used by the algorithm. Research in the last three decades has focused to a large extent on optimizing either one of the two measures separately, typically at the cost of the other. However, in many real-world applications, it is important to design distributed algorithms that simultaneously optimize both the measures. This project will investigate how distributed algorithms can be designed that work well under both measures. Furthermore, it will study the precise relationship between the two measures, in particular, how one can trade off one measure with respect to the other measure. This project will study time-message tradeoffs in distributed algorithms for various fundamental problems, including leader election, minimum spanning tree, shortest paths, and random walks. Specific goals of the project are: (1) Given a bound on one measure, design distributed algorithms that are optimal with respect to the other measure; (2) Obtain lower bounds on the complexity of one measure while fixing the other measure; (3) Obtain tradeoff relationships that characterize the dependence of one measure on the other. (4) Obtain efficient distributed algorithms that operate on large-scale graphs.