Distributed Computing and Communication Complexity
Trevor Alexander Brown · 2014
In these notes, we study the intersection of communication complexity and distributed computing. To understand why distributed computing researchers care about communication complexity tools and results, we briey turn our attention to distributed computing. In traditional distributed computing models, local computation is free, and communication between parties is expensive. Typical complexity measures include the number of messages sent (message complexity), the total number of bits sent (bit complexity), and the total number of rounds of computation in synchronous models (round complexity). Communication complexity is interested in these same complexity measures, and the most common communication complexity models are very similar (in some cases identical) to distributed computing models. In part, this is because communication complexity emerged from the study of distributed computing, and early interest in its models was driven by applications in distributed computing. For example, number-on-forehead models, wherein each player can see only the inputs of other players, were initially considered unrealistic (and less interesting) because they did not coincide with distributed computing models. In contrast, number-in-hand models, wherein each player sees only her own input, can be applied immediately to distributed computing problems, and have been studied extensively.