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?