Multiparty equality function computation in networks with point-to-point links

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