TR-195: The Expressiveness of Silence: Optimal Algorithms for Synchronous Communication of Information

Abstract

We establish a lower bound on the trade-off between time and bit complexity for two-party communication in synchronous networks. We prove that the bound is tight by presenting a protocol whose bit-time complexity matches the one expressed by the lower bound. The proposed algorithm is globally optimal (i.e., not only in the average and worst case). Similar results are derived when transmissions are subject to corruptions. Applications of the results to transforming an asynchronous distributed algorithm into a synchronous one are discussed.