nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Message Lower Bounds via Efficient Network Synchronization

verfasst von : Gopal Pandurangan, David Peleg, Michele Scquizzato

Erschienen in: Structural Information and Communication Complexity

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We present a uniform approach to derive message-time tradeoffs and message lower bounds for synchronous distributed computations using results from communication complexity theory.

Since the models used in the classical theory of communication complexity are inherently asynchronous, lower bounds do not directly apply in a synchronous setting. To address this issue, we show a general result called Synchronous Simulation Theorem (SST) which allows to obtain message lower bounds for synchronous distributed computations by leveraging lower bounds on communication complexity. The SST is a by-product of a new efficient synchronizer for complete networks, called \(\sigma \), which has simulation overheads that are only logarithmic in the number of synchronous rounds with respect to both time and message complexity in the CONGEST model. The \(\sigma \) synchronizer is particularly efficient in simulating synchronous algorithms that employ silence. In particular, a curious property of this synchronizer, which sets it apart from its predecessors, is that it is time-compressing, and hence in some cases it may result in a simulation that is faster than the original execution.

While the SST gives near-optimal message lower bounds up to large values of the number of allowed synchronous rounds r (usually polynomial in the size of the network), it fails to provide meaningful bounds when a very large number of rounds is allowed. To complement the bounds provided by the SST, we then derive message lower bounds for the synchronous message-passing model that are unconditional, that is, independent of r, via direct reductions from multi-party communication complexity.

We apply our approach to show (almost) tight message-time tradeoffs and message lower bounds for several fundamental problems in the synchronous message-passing model of distributed computation. These include sorting, matrix multiplication, and many graph problems. All these lower bounds hold for any distributed algorithms, including randomized Monte Carlo algorithms.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Public vs. Private Randomness in Simultaneous Multi-party Communication Complexity

Nächstes Kapitel Recent Results on Fault-Tolerant Consensus in Message-Passing Networks

We use \(\sigma \) as it is the first letter in the Greek word which means “silence”.

Throughout this paper, the notation \(\tilde{\varOmega }\) hides polylogarithmic factors in k and n, i.e., \({\tilde{\varOmega }}(f(n,k))\) denotes \(\varOmega (f(n,k)/({\text {polylog}}n {\text {polylog}}k))\).

Afek, Y., Gafni, E.: Time and message bounds for election in synchronous and asynchronous complete networks. SIAM J. Comput. 20(2), 376–394 (1991)MathSciNetCrossRefMATH

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–410. Springer, Heidelberg (2014). doi:10.1007/978-3-662-43951-7_34

Awerbuch, B.: Complexity of network synchronization. J. ACM 32(4), 804–823 (1985)MathSciNetCrossRefMATH

Awerbuch, B., Goldreich, O., Peleg, D., Vainish, R.: A trade-off between information and communication in broadcast protocols. J. ACM 37(2), 238–256 (1990)MathSciNetCrossRefMATH

Awerbuch, B., Peleg, D.: Network synchronization with polylogarithmic overhead. In: Proceedings of the 31st Annual Symposium on Foundations of Computer Science (FOCS), pp. 514–522 (1990)

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–1265 (2012)MathSciNetCrossRefMATH

Dolev, D., Feder, T.: Determinism vs. nondeterminism in multiparty communication complexity. SIAM J. Comput. 21(5), 889–895 (1992)MathSciNetCrossRefMATH

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–376 (2014)

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–456 (2006)MathSciNetCrossRefMATH

10.

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–576 (2013)

11.

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–1162 (2012)

12.

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–77 (1983)CrossRefMATH

13.

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–100 (2015)

14.

Impagliazzo, R., Williams, R.: Communication complexity with synchronized clocks. In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity (CCC), pp. 259–269 (2010)

15.

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–410 (2015)

16.

Kor, L., Korman, A., Peleg, D.: Tight bounds for distributed minimum-weight spanning tree verification. Theor. Comput. Syst. 53(2), 318–340 (2013)MathSciNetCrossRefMATH

17.

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–236 (1987)MathSciNetCrossRefMATH

18.

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–132 (1989)MathSciNetCrossRefMATH

19.

Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)CrossRefMATH

20.

Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: On the complexity of universal leader election. J. ACM 62(1), 7:1–7:27 (2015)MathSciNetCrossRefMATH

21.

Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: Sublinear bounds for randomized leader election. Theor. Comput. Sci. 561, 134–143 (2015)MathSciNetCrossRefMATH

22.

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–50 (2013)

23.

Lotker, Z., Patt-Shamir, B., Pavlov, E., Peleg, D.: Minimum-weight spanning tree construction in \({O}(\log \log n)\) communication rounds. SIAM J. Comput. 35(1), 120–131 (2005)MathSciNetCrossRefMATH

24.

Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco (1996)MATH

25.

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–266 (2011)

26.

Oshman, R.: Communication complexity lower bounds in distributed message-passing. In: Halldórsson, M.M. (ed.) SIROCCO 2014. LNCS, vol. 8576, pp. 14–17. Springer, Heidelberg (2014). doi:10.1007/978-3-319-09620-9_2

27.

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–438 (2016)

28.

Pandurangan, G., Robinson, P., Scquizzato, M.: A time- and message-optimal distributed algorithm for minimum spanning trees. CoRR, abs/1607.06883 (2016)

29.

Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia (2000)CrossRefMATH

30.

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–1442 (2000)MathSciNetCrossRefMATH

31.

Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM J. Comput. 18(4), 740–747 (1989)MathSciNetCrossRefMATH

32.

Santoro, N.: Design and Analysis of Distributed Algorithms. Wiley, Hoboken (2006)CrossRefMATH

33.

Schneider, J., Wattenhofer, R.: Trading bit, message, and time complexity of distributed algorithms. In: Peleg, D. (ed.) DISC 2011. LNCS, vol. 6950, pp. 51–65. Springer, Heidelberg (2011). doi:10.1007/978-3-642-24100-0_4 CrossRef

34.

Tel, G.: Introduction to Distributed Algorithms, 2nd edn. Cambridge University Press, Cambridge (2001)MATH

35.

Tiwari, P.: Lower bounds on communication complexity in distributed computer networks. J. ACM 34(4), 921–938 (1987)MathSciNetCrossRefMATH

36.

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–212 (2015)

37.

Woodruff, D.P., Zhang, Q.: When distributed computation is communication expensive. Distrib. Comput. (to appear)

38.

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–213 (1979)

Titel: Message Lower Bounds via Efficient Network Synchronization
verfasst von: Gopal Pandurangan
David Peleg
Michele Scquizzato
Verlag: Springer International Publishing
Buch: Structural Information and Communication Complexity
Print ISBN: 978-3-319-48313-9

Electronic ISBN: 978-3-319-48314-6

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-48314-6_6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"