Communication issues in distributed computing
Alon Orlitsky · 1987
A random variable (X,Y) is distributed over 0,...,n-1 x 0,...,n-1 and a function f is defined over the same domain. Two persons, P(,x) knowing X and P(,y) knowing Y, wan to determine f(X,Y). How many bits of information do they need to exchange? Two extremes of this question are considered: boolean functions and functions that are one-to-one. They are discussed in the parts on communication complexity and on sharing related information, respectively. In communication complexity we investigate: (1) two ways of counting the number of bits: worst case and expected value (assuming that (X,Y) is uniformly distributed); (2) two accuracy requirements: error free and (epsilon)-error; (3) two types of protocols: deterministic and randomized. There are eight combinations of these alternatives, each called a complexity measure, but only five are distinct. Let (VBAR)1(,f)(VBAR) denote the number of inputs (x,y) such that f(x,y) = 1. For any s between n and n('2)/2, we prove tight bounds on all five complexity measures of most functions with (VBAR)1(,f)(VBAR) = s and show that they separate into one of two classes: (1) log n class. The worst-case error-free deterministic and the worst-case error-free randomized complexities of most functions with (VBAR)1(,f)(VBAR) = s are log n + O(1) bits. (2) log s/n class. The average error-free deterministic, the average (epsilon)-error randomized, and the worst-case (epsilon)-error randomized complexities of most functions with (VBAR)1(,f)(VBAR) = s are log s/n + O(log log n) bits. As s decreases, the difference in complexities between measures in the two classes increases, becoming exponential for s (LESSTHEQ) n log n. However, for most functions (VBAR)1(,f)(VBAR) (DBLTURN) n('2)/2 and the classes coincide. The most interesting members of the two classes are the error-free deterministic complexities: worst case is in the log n class while average is in the log s/n class. In sharing related information we assume, without loss of generality, that f(X,Y) = (X,Y). Determining f(X,Y) is equivalent to sharing X and Y. Let p(x,y) be the underlying probability distribution of (X,Y). We show that H(X(VBAR)Y) + H(Y(VBAR)X) bits must be transmitted and H(X,Y) + 2 bits suffice. These bounds are not tight but are the best expressible in terms of entropies. To get tighter bounds, we restrict attention to subclasses of probability distributions. We show that if p(x,y) > 0 for all (x,y) than at least H(X,Y) bits must be transmitted (almost the upper bound) and, more interestingly, if p(x,y) is uniform over its support set then the lower bound can almost be achieved.