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 language | English |
|---|---|
| Pages (from-to) | 209-213 |
| Number of pages | 5 |
| Journal | Proceedings of the Annual ACM Symposium on Theory of Computing |
| DOIs | |
| State | Published - 30 Apr 1979 |
| Event | 11th Annual ACM Symposium on Theory of Computing, STOC 1979 - Atlanta, United States Duration: 30 Apr 1979 → 2 May 1979 |
Fingerprint
Dive into the research topics of 'Some complexity questions related to distributive computing'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver