{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:15:52Z","timestamp":1759637752350},"publisher-location":"Cham","reference-count":38,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319483139"},{"type":"electronic","value":"9783319483146"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-48314-6_6","type":"book-chapter","created":{"date-parts":[[2016,11,3]],"date-time":"2016-11-03T11:01:04Z","timestamp":1478170864000},"page":"75-91","source":"Crossref","is-referenced-by-count":7,"title":["Message Lower Bounds via Efficient Network Synchronization"],"prefix":"10.1007","author":[{"given":"Gopal","family":"Pandurangan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michele","family":"Scquizzato","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,11,4]]},"reference":[{"issue":"2","key":"6_CR1","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1137\/0220023","volume":"20","author":"Y Afek","year":"1991","unstructured":"Afek, Y., Gafni, E.: Time and message bounds for election in synchronous and asynchronous complete networks. SIAM J. Comput. 20(2), 376\u2013394 (1991)","journal-title":"SIAM J. Comput."},{"key":"6_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/978-3-662-43951-7_34","volume-title":"Automata, Languages, and Programming","author":"C Avin","year":"2014","unstructured":"Avin, C., Borokhovich, M., Lotker, Z., Peleg, D.: Distributed computing on core-periphery networks: axiom-based design. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8573, pp. 399\u2013410. Springer, Heidelberg (2014). doi: 10.1007\/978-3-662-43951-7_34"},{"issue":"4","key":"6_CR3","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1145\/4221.4227","volume":"32","author":"B Awerbuch","year":"1985","unstructured":"Awerbuch, B.: Complexity of network synchronization. J. ACM 32(4), 804\u2013823 (1985)","journal-title":"J. ACM"},{"issue":"2","key":"6_CR4","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1145\/77600.77618","volume":"37","author":"B Awerbuch","year":"1990","unstructured":"Awerbuch, B., Goldreich, O., Peleg, D., Vainish, R.: A trade-off between information and communication in broadcast protocols. J. ACM 37(2), 238\u2013256 (1990)","journal-title":"J. ACM"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Peleg, D.: Network synchronization with polylogarithmic overhead. In: Proceedings of the 31st Annual Symposium on Foundations of Computer Science (FOCS), pp. 514\u2013522 (1990)","DOI":"10.1109\/FSCS.1990.89572"},{"issue":"5","key":"6_CR6","doi-asserted-by":"crossref","first-page":"1235","DOI":"10.1137\/11085178X","volume":"41","author":"AD Sarma","year":"2012","unstructured":"Sarma, A.D., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. SIAM J. Comput. 41(5), 1235\u20131265 (2012)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"6_CR7","doi-asserted-by":"crossref","first-page":"889","DOI":"10.1137\/0221052","volume":"21","author":"D Dolev","year":"1992","unstructured":"Dolev, D., Feder, T.: Determinism vs. nondeterminism in multiparty communication complexity. SIAM J. Comput. 21(5), 889\u2013895 (1992)","journal-title":"SIAM J. Comput."},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In: Proceedings of the 33rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 367\u2013376 (2014)","DOI":"10.1145\/2611462.2611493"},{"issue":"2","key":"6_CR9","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1137\/S0097539704441058","volume":"36","author":"M Elkin","year":"2006","unstructured":"Elkin, M.: An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem. SIAM J. Comput. 36(2), 433\u2013456 (2006)","journal-title":"SIAM J. Comput."},{"key":"6_CR10","unstructured":"Ellen, F., Oshman, R., Pitassi, T., Vaikuntanathan, V.: Brief announcement: private channel models in multi-party communication complexity. In: Proceedings of the 27th International Symposium on Distributed Computing (DISC), pp. 575\u2013576 (2013)"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Frischknecht, S., Holzer, S., Wattenhofer, R.: Networks cannot compute their diameter in sublinear time. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1150\u20131162 (2012)","DOI":"10.1137\/1.9781611973099.91"},{"issue":"1","key":"6_CR12","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/357195.357200","volume":"5","author":"RG Gallager","year":"1983","unstructured":"Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. 5(1), 66\u201377 (1983)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Hegeman, J.W., Pandurangan, G., Pemmaraju, S.V., Sardeshmukh, V.B., Scquizzato, M.: Toward optimal bounds in the congested clique: graph connectivity and MST. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC), pp. 91\u2013100 (2015)","DOI":"10.1145\/2767386.2767434"},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Williams, R.: Communication complexity with synchronized clocks. In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity (CCC), pp. 259\u2013269 (2010)","DOI":"10.1109\/CCC.2010.32"},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Klauck, H., Nanongkai, D., Pandurangan, G., Robinson, P.: Distributed computation of large-scale graph problems. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 391\u2013410 (2015)","DOI":"10.1137\/1.9781611973730.28"},{"issue":"2","key":"6_CR16","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1007\/s00224-013-9479-7","volume":"53","author":"L Kor","year":"2013","unstructured":"Kor, L., Korman, A., Peleg, D.: Tight bounds for distributed minimum-weight spanning tree verification. Theor. Comput. Syst. 53(2), 318\u2013340 (2013)","journal-title":"Theor. Comput. Syst."},{"issue":"2","key":"6_CR17","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1137\/0216019","volume":"16","author":"E Korach","year":"1987","unstructured":"Korach, E., Moran, S., Zaks, S.: The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors. SIAM J. Comput. 16(2), 231\u2013236 (1987)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"6_CR18","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0304-3975(89)90103-5","volume":"64","author":"E Korach","year":"1989","unstructured":"Korach, E., Moran, S., Zaks, S.: Optimal lower bounds for some distributed algorithms for a complete network of processors. Theor. Comput. Sci. 64(1), 125\u2013132 (1989)","journal-title":"Theor. Comput. Sci."},{"key":"6_CR19","doi-asserted-by":"crossref","DOI":"10.1016\/S0065-2458(08)60342-3","volume-title":"Communication Complexity","author":"E Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)"},{"issue":"1","key":"6_CR20","doi-asserted-by":"crossref","first-page":"7:1","DOI":"10.1145\/2699440","volume":"62","author":"S Kutten","year":"2015","unstructured":"Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: On the complexity of universal leader election. J. ACM 62(1), 7:1\u20137:27 (2015)","journal-title":"J. ACM"},{"key":"6_CR21","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/j.tcs.2014.02.009","volume":"561","author":"S Kutten","year":"2015","unstructured":"Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: Sublinear bounds for randomized leader election. Theor. Comput. Sci. 561, 134\u2013143 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"Lenzen, C.: Optimal deterministic routing and sorting on the congested clique. In: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC), pp. 42\u201350 (2013)","DOI":"10.1145\/2484239.2501983"},{"issue":"1","key":"6_CR23","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1137\/S0097539704441848","volume":"35","author":"Z Lotker","year":"2005","unstructured":"Lotker, Z., Patt-Shamir, B., Pavlov, E., Peleg, D.: Minimum-weight spanning tree construction in $${O}(\\log \\log n)$$ O ( log log n ) communication rounds. SIAM J. Comput. 35(1), 120\u2013131 (2005)","journal-title":"SIAM J. Comput."},{"key":"6_CR24","volume-title":"Distributed Algorithms","author":"NA Lynch","year":"1996","unstructured":"Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco (1996)"},{"key":"6_CR25","doi-asserted-by":"crossref","unstructured":"Nanongkai, D., Sarma, A.D., Pandurangan, G.: A tight unconditional lower bound on distributed randomwalk computation. In: Proceedings of the 30th ACM Symposium on Principles of Distributed Computing (PODC), pp. 257\u2013266 (2011)","DOI":"10.1145\/1993806.1993853"},{"key":"6_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/978-3-319-09620-9_2","volume-title":"Structural Information and Communication Complexity","author":"R Oshman","year":"2014","unstructured":"Oshman, R.: Communication complexity lower bounds in distributed message-passing. In: Halld\u00f3rsson, M.M. (ed.) SIROCCO 2014. LNCS, vol. 8576, pp. 14\u201317. Springer, Heidelberg (2014). doi: 10.1007\/978-3-319-09620-9_2"},{"key":"6_CR27","doi-asserted-by":"crossref","unstructured":"Pandurangan, G., Robinson, P., Scquizzato, M.: Fast distributed algorithms for connectivity and MST in large graphs. In: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 429\u2013438 (2016)","DOI":"10.1145\/2935764.2935785"},{"key":"6_CR28","doi-asserted-by":"crossref","unstructured":"Pandurangan, G., Robinson, P., Scquizzato, M.: A time- and message-optimal distributed algorithm for minimum spanning trees. CoRR, abs\/1607.06883 (2016)","DOI":"10.1145\/3055399.3055449"},{"key":"6_CR29","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia (2000)"},{"issue":"5","key":"6_CR30","doi-asserted-by":"crossref","first-page":"1427","DOI":"10.1137\/S0097539700369740","volume":"30","author":"D Peleg","year":"2000","unstructured":"Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM J. Comput. 30(5), 1427\u20131442 (2000)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"6_CR31","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1137\/0218050","volume":"18","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM J. Comput. 18(4), 740\u2013747 (1989)","journal-title":"SIAM J. Comput."},{"key":"6_CR32","doi-asserted-by":"crossref","DOI":"10.1002\/0470072644","volume-title":"Design and Analysis of Distributed Algorithms","author":"N Santoro","year":"2006","unstructured":"Santoro, N.: Design and Analysis of Distributed Algorithms. Wiley, Hoboken (2006)"},{"key":"6_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/978-3-642-24100-0_4","volume-title":"Distributed Computing","author":"J Schneider","year":"2011","unstructured":"Schneider, J., Wattenhofer, R.: Trading bit, message, and time complexity of distributed algorithms. In: Peleg, D. (ed.) DISC 2011. LNCS, vol. 6950, pp. 51\u201365. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-24100-0_4"},{"key":"6_CR34","volume-title":"Introduction to Distributed Algorithms","author":"G Tel","year":"2001","unstructured":"Tel, G.: Introduction to Distributed Algorithms, 2nd edn. Cambridge University Press, Cambridge (2001)","edition":"2"},{"issue":"4","key":"6_CR35","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/31846.32978","volume":"34","author":"P Tiwari","year":"1987","unstructured":"Tiwari, P.: Lower bounds on communication complexity in distributed computer networks. J. ACM 34(4), 921\u2013938 (1987)","journal-title":"J. ACM"},{"key":"6_CR36","doi-asserted-by":"crossref","unstructured":"Van Gucht, D., Williams, R., Woodruff, D.P., Zhang, Q.: The communication complexity of distributed set-joins with applications to matrix multiplication. In: Proceedings of the 34th ACM Symposium on Principles of Database Systems (PODS), pp. 199\u2013212 (2015)","DOI":"10.1145\/2745754.2745779"},{"key":"6_CR37","doi-asserted-by":"crossref","unstructured":"Woodruff, D.P., Zhang, Q.: When distributed computation is communication expensive. Distrib. Comput. (to appear)","DOI":"10.1007\/978-3-642-41527-2_2"},{"key":"6_CR38","doi-asserted-by":"crossref","unstructured":"Yao, AC.-C.: Some complexity questions related to distributive computing. In: Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC), pp. 209\u2013213 (1979)","DOI":"10.1145\/800135.804414"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-48314-6_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,15]],"date-time":"2019-09-15T03:43:15Z","timestamp":1568518995000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-48314-6_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319483139","9783319483146"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-48314-6_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}