Message lower bounds via efficient network synchronization

作     者：Pandurangan, Gopal Peleg, David Scquizzato, Michele 

作者机构：Univ Houston Dept Comp Sci Houston TX 77204 USA Weizmann Inst Sci Dept Comp Sci & Appl Math IL-76100 Rehovot Israel Univ Padua Dept Math I-35121 Padua Italy 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2020年第810卷

页      面：82-95页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Foundation (NSF) [CCF-1527867, CCF-1540512, IIS-1633720, CCF-BSF-1717075] US-Israel Binational Science Foundation (BSF) BSF-NSF grant 

主　　题：Distributed algorithms Synchronous message-passing Communication complexity Lower bounds Synchronizers 

摘      要：We present a uniform approach to derive message-time tradeoffs and message lower bounds for synchronous distributed computations using results from communication complexity theory. Since the models used in the classical theory of communication complexity are inherently asynchronous, lower bounds do not directly apply in a synchronous setting. To address this issue, we show a general result called Synchronous Simulation Theorem (SST) which allows to obtain message lower bounds for synchronous distributed computations by leveraging lower bounds on communication complexity. The SST is a by-product of a new efficient synchronizer for complete networks, called sigma, which has simulation overheads that are only logarithmic in the number of synchronous rounds with respect to both time and message complexity, even in networks with limited bandwidth. Synchronizer sigma is particularly efficient in simulating synchronous algorithms which employ silence, a situation that occurs when in some round no processor sends any message. In particular, a curious property of this synchronizer, which sets it apart from its predecessors, is that it is time-compressing, and hence in some cases it may result in a simulation that is faster than the original execution. While the SST gives near-optimal message lower bounds up to large values of the number of allowed synchronous rounds r (usually polynomial in the size of the input), it fails to provide meaningful bounds when the synchronous algorithm to be simulated may comprise a very large number of rounds. To complement the bounds provided by the SST, we then derive message lower bounds for the synchronous message-passing model that are unconditional, that is, independent of r, by establishing novel lower bounds for multi-party synchronous communication complexity. We apply our approach to show (almost) tight message-time tradeoffs and message lower bounds for several fundamental problems in the synchronous message-passing model of distribu