×

The range of topological effects on communication. (English) Zbl 1440.68011

Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part II. Berlin: Springer. Lect. Notes Comput. Sci. 9135, 540-551 (2015).
Summary: We continue the study of communication cost of computing functions when inputs are distributed among \(k\) processors, each of which is located at one vertex of a network/graph called a terminal. Every other node of the network also has a processor, with no input. The communication is point-to-point and the cost is the total number of bits exchanged by the protocol, in the worst case, on all edges.
The authors et al. [“Topology matters in communication”, in: Proceedings of the 55th annual IEEE symposium on foundations of computer science, FOCS’14. Los Alamitos, CA: IEEE Computer Society. 631–640 (2014; doi:10.1109/FOCS.2014.73)] recently initiated the study of the effect of topology of the network on the total communication cost using tools from \(L_1\) embeddings. Their techniques provided tight bounds for simple functions like Element-Distinctness (ED), which depend on the 1-median of the graph. This work addresses two other kinds of natural functions. We show that for a large class of natural functions like Set-Disjointness the communication cost is essentially \(n\) times the cost of the optimal Steiner tree connecting the terminals. Further, we show for natural composed functions like \(\mathrm{ED} \circ \mathrm{XOR}\) and \(\mathrm{XOR} \circ \mathrm{ED}\), the naive protocols suggested by their definition is optimal for general networks. Interestingly, the bounds for these functions depend on more involved topological parameters that are a combination of Steiner tree and 1-median costs.
To obtain our results, we use some new tools in addition to ones used in [loc. cit.] These include (i) viewing the communication constraints via a linear program; (ii) using tools from the theory of tree embeddings to prove topology sensitive direct sum results that handle the case of composed functions and (iii) representing the communication constraints of certain problems as a family of collection of multiway cuts, where each multiway cut simulates the hardness of computing the function on the star topology.
For the entire collection see [Zbl 1316.68013].

MSC:

68M10 Network design and communication in computer systems
68M12 Network protocols
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Awerbuch, B., Azar, Y.: Buy-at-bulk network design. In: 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, October 19-22, Miami Beach, Florida, USA, pp. 542-547 (1997). doi:10.1109/SFCS.1997.646143
[2] Balcan, M.F., Blum, A., Fine, S., Mansour, Y.: Distributed learning, communication complexity and privacy. In: COLT, pp. 26.1-26.22 (2012)
[3] Barak, B., Braverman, M., Chen, X., Rao, A.: How to compress interactive communication. SIAM J. Comput. 42(3), 1327-1363 (2013). doi:10.1137/100811969 · Zbl 1272.68138
[4] Beame, P., Koutris, P., Suciu, D.: Communication steps for parallel query processing. In: PODS, pp. 273-284 (2013) · Zbl 1426.68074
[5] Bourgain, J., On lipschitz embedding of finite metric spaces in hilbert space, Israel J. Math., 52, 1-2, 46-52 (1995) · Zbl 0657.46013
[6] Braverman, M., Ellen, F., Oshman, R., Pitassi, T., Vaikuntanathan, V.: A tight bound for set disjointness in the message-passing model. In: 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 668-677 (2013). doi:10.1109/FOCS.2013.77
[7] Chattopadhyay, A., Mukhopadhyay, S.: Tribes is hard in the message-passing model. In: STACS, pp. 224-237 (2015) · Zbl 1356.68060
[8] Chattopadhyay, A., Rudra, A.: The Range of Topological Effects on Communication. ArXiv e-prints (April 2015) · Zbl 1440.68011
[9] Chattopadhyay, A., Radhakrishnan, J., Rudra, A.: Topology matters in communication. In: FOCS, pp. 631-640 (2014)
[10] Cormode, G.: The continuous distributed monitoring model. SIGMOD Rec. 42(1), 5-14 (2013). doi:10.1145/2481528.2481530
[11] Dolev, D., Feder, T.: Multiparty communication complexity. In: FOCS, pp. 428-433 (1989)
[12] Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In: PODC, pp. 367-376 (2014) · Zbl 1321.68381
[13] Duris, P.; Rolim, J., Lower bounds on the multiparty communication complexity, J. Comput. Syst. Sci., 56, 1, 90-95 (1998) · Zbl 0917.94024 · doi:10.1006/jcss.1997.1547
[14] Goldreich, O.; Goldreich, O., Three XOR-Lemmas — an exposition, Studies in Complexity and Cryptography, 248-272 (2011), Heidelberg: Springer, Heidelberg · Zbl 1343.68112
[15] Goldreich, O.; Nisan, N.; Wigderson, A.; Goldreich, O., On yao’s XOR-Lemma, Studies in Complexity and Cryptography, 273-301 (2011), Heidelberg: Springer, Heidelberg · Zbl 1304.68074
[16] Huang, Z., Radunovic, B., Vojnovic, M., Zhang, Q.: Communication complexity of approximate maximum matching in distributed graph data. In: 32nd Symposium on Theoretical Aspects of Computer Science (STACS), pp. 460-473 (2015) · Zbl 1355.68100
[17] Karchmer, M.; Raz, R.; Wigderson, A., Super-logarithmic depth lower bounds via the direct sum in communication complexity, Computational Complexity, 5, 3-4, 191-204 (1995) · Zbl 0851.68034 · doi:10.1007/BF01206317
[18] Karloff, H.J., Suri, S., Vassilvitskii, S.: A model of computation for mapreduce. In: SODA, pp. 938-948 (2010) · Zbl 1288.68247
[19] Kowshik, H.; Kumar, P., Optimal function computation in directed and undirected graphs, IEEE Transcations on Information Theory, 58, 6, 3407-3418 (2012) · Zbl 1365.05113 · doi:10.1109/TIT.2012.2188883
[20] Li, Y., Sun, X., Wang, C., Woodruff, D.P.: On the communication complexity of linear algebraic problems in the message passing model. In: Kuhn, F. (ed.) DISC 2014. LNCS, vol. 8784, pp. 499-513. Springer, Heidelberg (2014). doi:10.1007/978-3-662-45174-8_34
[21] Linial, N.; London, E.; Rabinovich, Y., The geometry of graphs and some of its algorithmic applications, Combinatorica, 15, 2, 215-245 (1995) · Zbl 0827.05021 · doi:10.1007/BF01200757
[22] Nešetřil, J., Milková, E., Nešetřilová, H.: Otakar Boru̇vka on minimum spanning tree problem translation of both the 1926 papers, comments, history. Discrete Mathematics 233(13), 3-36 (2001). http://www.sciencedirect.com/science/article/pii/S0012365X00002247; czech and Slovak 2 · Zbl 0999.01019
[23] Phillips, J.M., Verbin, E., Zhang, Q.: Lower bounds for number-in-hand multiparty communication complexity, made easy. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 486-501 (2012). http://portal.acm.org/citation.cfm?id=2095158&CFID=63838676&CFTOKEN=79617016 · Zbl 1422.68090
[24] Raz, R.; McKenzie, P., Separation of the monotone \(\text{NC}\) hierarchy, Combinatorica, 19, 3, 403-435 (1999) · Zbl 0977.68037 · doi:10.1007/s004930050062
[25] Sherstov, A., Separating \(\text{AC}^0\) from depth-2 majority circuits, SIAM J. Comput., 38, 6, 2113-2129 (2009) · Zbl 1188.68149 · doi:10.1137/08071421X
[26] Shi, Y.; Zhu, Y., Quantum communication complexity of block-composed functions, Qunatum Computation and Information, 9, 5, 444-460 (2009) · Zbl 1172.81320
[27] Tiwari, P., Lower bounds on communication complexity in distributed computer networks, J. ACM, 34, 4, 921-938 (1987) · Zbl 0629.68024 · doi:10.1145/31846.32978
[28] Valiant, LG, A bridging model for parallel computation, Commun. ACM, 33, 8, 103-111 (1990) · doi:10.1145/79173.79181
[29] Vazirani, VV, Approximation Algorithms (2001), New York: Springer-Verlag New York Inc., New York
[30] Woodruff, D., Zhang, Q.: Tight bounds for distributed functional monitoring. In: STOC, pp. 941-960 (2012) · Zbl 1286.68025
[31] Woodruff, DP; Zhang, Q.; Afek, Y., When distributed computation is communication expensive, Distributed Computing, 16-30 (2013), Heidelberg: Springer, Heidelberg · Zbl 1423.68077 · doi:10.1007/978-3-642-41527-2_2
[32] Woodruff, D., Zhang, Q.: An optimal lower bound for distinct elements in the message passing model. In: SODA, pp. 718-733 (2014) · Zbl 1422.68096
[33] Yao, A.C.C.: Some complexity questions related to distributed computing. In: 11th ACM Symposium on Theory of Computing (STOC), pp. 209-213 (1979)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.