Multiparty Equality Function Computation in Networks with Point-to-Point Links

摘要

In this paper, we study the problem of computing the multiparty equality (MEQ) function: n ≥ 2 nodes, each of which is given an input value from {1, • • •, K}, determine if their inputs are all identical, under the point-to-point communication model. The MEQ function equals to 1 if and only if all n inputs are identical, and 0 otherwise. The communication complexity of the MEQ problem is defined as the minimum number of bits communicated in the worst case. It is easy to show that (n- 1) log_2 K bits is an upper bound, by constructing a simple algorithm with that cost. In this paper, we demonstrate that communication cost strictly lower than this upper bound can be achieved. We show this by constructing a static protocol that solves the MEQ problem for n = 3, K = 6, of which the communication cost is strictly lower than the above upper bound (2 log_2 6 bits). This result is then generalized for large values of n and K.