The communication complexity for decentralized evaluation of functions

Decentralized algorithms can be characterized by successive rounds of message interchanges. In each round, all nodes exchange information and carry out computations. The computations at each node in round i are based on the information available at that node after the communication phase of round i. Therefore, the complexity of the communication requirement is a major determining factor of the performance of a decentralized algorithm. In this paper, we study the communication complexity for decentralized evaluation of functions. We show that for any decentralized algorithm of evaluating a function the number of messages required is at least kN(⌊N ^{1 k}⌋-1), where N is the number of nodes in the system and k is the number of rounds of message interchanges. In addition, we classify the functions into three types including fully reducible, partially reducible, and irreducible. We than show that for fully reducible functions the number of bits required for decentralized evaluation is at least kN(⌊N ^{1 k}⌋-1 )(B+ H), where B is the number of bits required for representing the initial value of each node and H is the number of bits required for the header and tailer of each message. For irreducible functions, the number of bits required for decentralized evaluation is at least N(N-1)B+kN(⌊N ^{1 k}⌋-1)H.