Some complexity questions related to distributive computing(Preliminary Report)

ABSTRACT

Let M = {0, 1, 2, ..., m—1} , N = {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 ε M, j ε N be integers known only to two persons P₁ and P₂, respectively. For P₁ and P₂ 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) = (i + j) mod 2. then 1 bit of information (conveying whether i is odd) sent from P₁ to P₂ will enable P₂ 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. 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. 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. 3.M. O. Rabin and A. C. Yao, in preparation.

Index Terms

• Mathematics of computing

  • Probability and statistics

    • Probabilistic algorithms

    • Probabilistic reasoning algorithms

      • Markov-chain Monte Carlo methods

      • Sequential Monte Carlo methods

• Theory of computation

  • Models of computation

    • Concurrency

      • Parallel computing models