TY - JOUR

T1 - The communication complexity for decentralized evaluation of functions

AU - Yuan, Shyan-Ming

PY - 1990/8/7

Y1 - 1990/8/7

N2 - 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.

AB - 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.

KW - bit complexity

KW - Decentralized algorithms

KW - message complexity

UR - http://www.scopus.com/inward/record.url?scp=0025702471&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(90)90021-O

DO - 10.1016/0020-0190(90)90021-O

M3 - Article

AN - SCOPUS:0025702471

VL - 35

SP - 177

EP - 182

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 4

ER -