Abstract
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 (2log2 6 bits). This result is then generalized for large values of n and K.
This research is supported in part by Army Research Office grant W-911-NF-0710287 and National Science Foundation award 1059540. Any opinions, findings, and conclusions or recommendations expressed here are those of the authors and do not necessarily reflect the views of the funding agencies or the U.S. government.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. In: STOC (1996)
Bar-yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D.: An information statistics approach to data stream and communication complexity. In: IEEE FOCS, pp. 209–218 (2002)
Chakrabarti, A., Khot, S., Sun, X.: Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In: IEEE CCC (2003)
Chandra, A.K., Merrick, I., Furst, L., Lipton, R.J.: Multi-party protocols. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pp. 94–99 (1983)
Dinitz, Y., Moran, S., Rajsbaum, S.: Exact communication costs for consensus and leader in a tree. J. of Discrete Algorithms 1, 167–183 (2003)
Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (2006)
Kushilevitz, E., Weinreb, E.: The communication complexity of set-disjointness with small sets and 0-1 intersection. In: IEEE FOCS (2009)
Lamport, L., Shostak, R., Pease, M.: The byzantine generals problem. ACM Trans. on Programming Languages and Systems (1982)
Liang, G., Vaidya, N.: Complexity of multi-valued byzantine agreement. Technical Report, CSL, UIUC (June 2010), http://arxiv.org/abs/1006.2422
Liang, G., Vaidya, N.: Multiparty equality function computation in networks with point-to-point links. Technical Report, CSL, UIUC (2010)
Pătraşcu, M., Williams, R.: On the possibility of faster sat algorithms. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’10, pp. 1065–1075, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics (2010)
Yao, A.C.-C.: Some complexity questions related to distributive computing(preliminary report). In: STOC 1979: Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, pp. 209–213. ACM, New York (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Liang, G., Vaidya, N. (2011). Multiparty Equality Function Computation in Networks with Point-to-Point Links. In: Kosowski, A., Yamashita, M. (eds) Structural Information and Communication Complexity. SIROCCO 2011. Lecture Notes in Computer Science, vol 6796. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22212-2_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-22212-2_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22211-5
Online ISBN: 978-3-642-22212-2
eBook Packages: Computer ScienceComputer Science (R0)