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

现实世界的分布式通信网络，如互联网、点对点网络、自组织无线和传感器网络以及用于大规模数据处理的数据中心网络，是当今数字社会不可或缺的一部分。分布式/去中心化算法是这些网络高效运行的基础，例如，分布式最短路径算法用于互联网中的路由，分布式图算法用于社交网络中寻找社区。因此，设计和分析高效的分布式算法是一项重要的研究任务，它将在现实世界的网络中实现更快、更节约资源的性能。为了解决更现实的情况，本项目将致力于设计分布式算法，同时优化(1)运行时间和(2)消息数量。该研究将有助于设计具有可证明性能保证的高效可扩展分布式算法。它可以影响点对点和自组织无线传感器网络的算法设计，以及大规模数据的分布式处理。PI计划开发与上述研究密切相关的分布式网络算法的新课程和教科书。休斯顿大学是指定的西班牙裔服务公共一级研究机构，PI将努力让少数族裔和代表性不足的学生参与研究。决定分布式算法效率的两个基本性能指标是运行时间和算法使用的消息数量。过去三十年的研究在很大程度上集中在分别优化这两种措施中的任何一种，通常是以牺牲另一种措施为代价的。然而，在许多实际应用中，重要的是设计同时优化这两种度量的分布式算法。该项目将研究如何设计分布式算法，使其在这两种方法下都能很好地工作。此外，它将研究两种措施之间的确切关系，特别是如何权衡一种措施相对于另一种措施。该项目将研究分布式算法中各种基本问题的时间-消息权衡，包括领导者选举，最小生成树，最短路径和随机行走。该项目的具体目标是：(1)给定一个度量的界限，设计相对于另一个度量最优的分布式算法；(2)在固定另一测度的同时，求得一测度复杂度的下界；(3)获得衡量一个测度对另一个测度依赖的权衡关系。(4)获得在大规模图上运行的高效分布式算法。

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.