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?

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.

  • $\begingroup$ This is indeed the buzzword to search for. However, I think most work is for complexity, less so algorithm analysis. $\endgroup$
    – Raphael
    Jul 17 '17 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.