Multiparty Equality Function Computation in Networks with Point-to-Point Links
Multiparty Equality Function Computation in Networks with Point-to-Point Links
复制标题
点对点链路网络中的多方等式函数计算
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
N. Vaidya
中科院分区：
文献类型：
--
作者：
Guanfeng Liang;N. Vaidya
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) log2 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 log2 6 bits). This result is then generalized for large values of n and K.
