The communication complexity for decentralized evaluation of functions

Shyan-Ming Yuan*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)177-182
Number of pages6
JournalInformation Processing Letters
Volume35
Issue number4
DOIs
StatePublished - 7 Aug 1990

Keywords

  • bit complexity
  • Decentralized algorithms
  • message complexity

Fingerprint Dive into the research topics of 'The communication complexity for decentralized evaluation of functions'. Together they form a unique fingerprint.

Cite this