Theory of message complexity analysis of distributed systems

Question

Inspired by this post, I thought it would be a good idea to ask an analogous question in the context of distributed systems -

While most of us are familiar with the notion of Time Complexity as a measure of efficiency of algorithms, In the world of distributed systems, another important measure of efficiency plays a preeminent role namely that of Message Complexity.

Specifically, when working in terms of the graph network model(i.e., algorithm instances executing on each node of a network pursuant of a network-level goal), it is the total number of bits of information that are cumulatively sent through each edge/connection of the system over the course of execution of the distributed system. My question is as follows:

• What are the usual techniques applied to calculating/bounding the message complexity cost of distributed algorithms?
• What is the generalised structure/theory behind these techniques?

Answer 1

S. Arora, B. Barak, Computational Complexity Modern Approach, Chapter 13 is a good introductory resource to this topic:

Communication complexity concerns the following scenario. There are two players with unlimited computational power, each of whom holds an $n$ bit input, say $x$ and $y$. Neither knows the other’s input, and they wish to collaboratively compute $f(x, y)$ where the function $f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}$ is known to both. Furthermore, they had foreseen this situation (e.g., one of the parties could be a spacecraft and the other could be the base station on earth), so they had already — before they knew their inputs $x, y$ — agreed upon a protocol for communication. The cost of this protocol is the number of bits communicated by the players for the worst-case choice of inputs $x, y$.

This chapter also covers lower bound methods: the fooling set method, the tiling method, the rank method, the discrepancy method. It gives also a brief overview of other communication models: randomized protocols, nondeterministic protocols, average case protocols, and asymmetric communication. At the end of the chapter it provides detailed reference to papers relating this topic.