The communication complexity for decentralized evaluation of functions

Shyan-Ming Yuan*

*此作品的通信作者

研究成果: Article同行評審

2 引文 斯高帕斯(Scopus)

摘要

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.

原文English
頁(從 - 到)177-182
頁數6
期刊Information Processing Letters
35
發行號4
DOIs
出版狀態Published - 7 8月 1990

指紋

深入研究「The communication complexity for decentralized evaluation of functions」主題。共同形成了獨特的指紋。

引用此