Skip to main navigation Skip to search Skip to main content

Some complexity questions related to distributive computing

  • Andrew Chi Chih Yao

Research output: Contribution to journalConference articlepeer-review

1048 Scopus citations

Abstract

Let M = [0,1,2,m-1], N = [0,1, 2,n-1], and f:M X N-[0,1] a Boolean-valued function. We will be interested in the following problem and its related questions. Let i 6 M,.;' S/V be integers known only to two persons Pi and Pi, respectively. For P( and Pi to determine cooperatively the value f(i, j), they send information to each other alternately, one bit at a time, according to some algorithm. The quantity of interest, which measures the information exchange necessary for computing/, is the minimum number of bits exchanged in any algorithm. For example, if f(i, j) == (t-f-j) mod 2, then 1 bit of information (conveying whether i is odd) sent from Pi to Pi will enable P2 to determine f[i, j), and this is clearly the best possible.

Original languageEnglish
Pages (from-to)209-213
Number of pages5
JournalProceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 30 Apr 1979
Event11th Annual ACM Symposium on Theory of Computing, STOC 1979 - Atlanta, United States
Duration: 30 Apr 19792 May 1979

Fingerprint

Dive into the research topics of 'Some complexity questions related to distributive computing'. Together they form a unique fingerprint.

Cite this