Multiparty Equality Function Computation in Networks with Point-to-Point Links
ILLINOIS UNIV AT URBANA-CHAMPAIGN
Pagination or Media Count:
In this report, we study the communication complexity problem of the multiparty equality function, under the point-to-point communication model. We demonstrate that traditional techniques generalized from two-party communication complexity problem are not sufficient to obtain tight bounds under the point-to-point communication model. We then introduce techniques to transform any MEQ-AD protocol into a equivalent partially ordered iid protocol. These techniques significantly reduce the space of MEQ-AD protocols to study. We then study the MEQ-AD3,6 problem and introduce an optimal protocol that achieves CsubAD3, 6. This protocol is then used as building blocks for construction of efficient protocols for MEQ-AD3,6h and MEQ-AD3,2k. The problem of finding the communication complexity of the MEQ problem for general values of n and M is still open.
- Operations Research
- Computer Programming and Software
- Computer Systems