Some complexity questions related to distributive computing(Preliminary Report)

ABSTRACT

Let M &equil; {0, 1, 2, ..., m—1} , N &equil; {0, 1, 2,..., n—1} , and f:M × N → {0, 1} a Boolean-valued function. We will be interested in the following problem and its related questions. Let i &egr; M, j &egr; N be integers known only to two persons P1 and P2, respectively. For P1 and P2 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 f, is the minimum number of bits exchanged in any algorithm. For example, if f(i, j) &equil; (i + j) mod 2. then 1 bit of information (conveying whether i is odd) sent from P1 to P2 will enable P2 to determine f(i, j), and this is clearly the best possible. The above problem is a variation of a model of Abelson [1] concerning information transfer in distributive computions.

REFERENCES

• 1: H. Abelson, Lower Bounds on Information Transfer in Distributed Computations, Proc. IEEE 19-th Annual Symp. on Foundations of Computer Science, Ann Arbor, 1978, pp. 151-158.
• 2: M. O. Rabin, Probabilistic Algorithms, in Algorithms and Complexity: Recent Results and New Directions, edited by J F. Traub, Academic Press, 1976, pp. 21-40.
• 3: M. O. Rabin and A. C. Yao, in preparation.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory