BSF:2014424:Time-Message Tradeoffs in Distributed Algorithms

University Of Houston, Houston TX

Investigators

Abstract

Distributed algorithms underlie the efficient operation of large-scale communication networks, e.g., distributed shortest paths algorithms are used for routing in the Internet. Two fundamental performance measures of distributed algorithms 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. This project investigates how distributed algorithms can be designed to work well under both measures simultaneously. This may have significant implications in many emerging applications, especially in the context of large-scale distributed communication networks and distributed processing of large-scale data. The project studies time-message tradeoffs in distributed algorithms for various specific fundamental problems, such as leader election, shortest paths, minimum spanning tree construction, and random walks. These are fundamental primitives in distributed computing where optimizing both time and messages simultaneously has so far been elusive. Specific goals of the project are to: (1) design distributed algorithms that are optimal with respect to the other measure when given a particular value of one measure; (2) obtain lower bounds on the complexity of one measure while fixing the other measure; (3) obtain tradeoff relationships that characterizes the dependence of one measure on the other; and (4) obtain efficient distributed algorithms that operate on large-scale graphs. This research will yield efficient and scalable distributed algorithms with provable performance guarantees. This project could potentially impact algorithm design in real-world distributed networks and distributed computations over large-scale data. The project trains students and postdoctoral fellows to tackle research problems in distributed algorithms.