Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Distributed Computing
Erschienen in: Distributed Computing 6/2020

09.04.2020

Fooling views: a new lower bound technique for distributed computations under congestion

verfasst von: Amir Abboud, Keren Censor-Hillel, Seri Khoury, Christoph Lenzen

Erschienen in: Distributed Computing | Ausgabe 6/2020

Einloggen

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

search-config
loading …

Abstract

We introduce a novel lower bound technique for distributed graph algorithms under bandwidth limitations. We define the notion of fooling views and exemplify its strength by proving two new lower bounds for triangle membership in the Congest \((B)\) model:
1.
Any 1-round algorithm requires \(B\ge c\varDelta \log n\) for a constant \(c>0\).
 
2.
If \(B=1\), even in constant-degree graphs any algorithm must take \(\varOmega (\log ^* n)\) rounds.
 
The implication of the former is the first proven separation between the Local and the Congest models for deterministic triangle membership. The latter result is the first non-trivial lower bound on the number of rounds required, even for triangle detection, under limited bandwidth. All previous known techniques are provably incapable of giving these bounds. We hope that our approach may pave the way for proving lower bounds for additional problems in various settings of distributed computing for which previous techniques do not suffice.
Vorheriger Artikel Detecting cliques in CONGEST networks
Nächster Artikel Fault-tolerant simulation of population protocols

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
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
Congest \((B)\) stands for the synchronous model with a bandwidth of B bits. In particular, the standard Local and Congest models correspond to Congest \((\infty )\) and Congest \((\log {n})\), respectively.
 
2
Throughout this paper \(\varDelta \) denotes the maximum degree of the graph.
 
3
This result applies to small output, e.g. the triangle detection problem, which is a decision problem. For listing all triangles in the graph, a tight bound of \(\varOmega (n^{1/3}/\log n)\) holds [24, 34].
 
4
In the triangle membership problem, every node must indicate whether it participates in a triangle.
 
5
While this reduction increases the ID space by r, it remains polynomial in n, because we know that \(r<n\).
 
6
Locally Checkable Labeling (LCL) problems are problems in which the legality of the output can be verified by looking at the output of the immediate neighborhood (e.g., coloring).
 
7
For simplifying the exposition, we will assume that nodes send B bits in each round and cannot send less bits or remain silent. It is easy to verify that this only affects the constants in our asymptotic notation.
 
8
In fact, one can show that there are many such nodes as \(w^*\), but we do not use this in this section.
 
9
Throughout the paper, we denote by \({{\dot{\cup }}}\) a disjoint union.
 
10
Observe that the order of the triple doesn’t matter. We still choose the notation (u, w, x) instead of \(\{u,w,x\}\) as it helps us to refer to nodes from specific sets in the proofs. That is, in the proofs later when we denote (u, w, x) we mean \(u\in A_1\), \(w\in A_2\), \(x\in A_3\).
 
11
We say that an event occurs with high probability if it occurs with probability \(1-\frac{1}{n^c}\), for some constant \(c\ge 1\).
 
12
It can be proved by the rank method for proving lower bounds for deterministic protocols in communication complexity. To read more about the rank method, see for example [41, Section 1.4]. For the proof of the lower bound on the rank of S-Disjointness, see [35, page 175].
 
Literatur
1.
Abboud, A., Backurs, A., Williams, V.V.: If the current clique algorithms are optimal, so is Valiant’s parser. In: FOCS, pp. 98–117 (2015)
2.
Abboud, A., Censor-Hillel, K., Khoury, S., Lenzen, C.: Fooling views: a new lower bound technique for distributed computations under congestion (2017). arxiv:​1711.​01623
3.
Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: FOCS, pp. 434–443 (2014)
4.
Abboud, A., Williams, V.V., Yu, H.: Matching triangles and basing hardness on an extremely popular conjecture. In: STOC, pp. 41–50 (2015)
5.
Afrati, F.N., Fotakis, D., Ullman, J.D.: Enumerating subgraph instances using map-reduce. In: ICDE, pp. 62–73. IEEE (2013)
6.
Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7(4), 567–583 (1986)MathSciNetCrossRef
7.
8.
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)MathSciNetCrossRef
9.
Bansal, N., Williams, R.: Regularity lemmas and combinatorial algorithms. Theory Comput. 8(1), 69–94 (2012)MathSciNetCrossRef
10.
11.
Baruch, M., Fraigniaud, P., Patt-Shamir, B.: Randomized proof-labeling schemes. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC), pp. 315–324 (2015)
12.
Belovs, A.: Span programs for functions with constant-sized 1-certificates. In: STOC, pp. 77–84. ACM (2012)
13.
Björklund, A., Pagh, R., Williams, V.V., Zwick, U.: Listing triangles. In: International Colloquium on Automata, Languages, and Programming, pp. 223–234. Springer (2014)
14.
Brandt, S., Fischer, O., Hirvonen, J., Keller, B., Lempiäinen, T., Rybicki, J., Suomela, J., Uitto, J.: A lower bound for the distributed lovász local lemma. In: STOC, pp. 479–488 (2016)
15.
Buhrman, H., Durr, C., Heiligman, M., Hoyer, P., Magniez, F., Santha, M., De Wolf, R.: Quantum algorithms for element distinctness. In: CCC, pp. 131–137. IEEE (2001)
16.
Censor-Hillel, K., Fischer, E., Schwartzman, G., Vasudev, Y.: Fast distributed algorithms for testing graph properties. In: DISC, pp. 43–56. Springer (2016)
17.
Censor-Hillel, K., Kaski, P., Korhonen, J.H., Lenzen, C., Paz, A., Suomela, J.: Algebraic methods in the congested clique. In: PODC, pp. 143–152. ACM (2015)
18.
Censor-Hillel, K., Kavitha, T., Paz, A., Yehudayoff, A.: Distributed construction of purely additive spanners. In: DISC, pp. 129–142 (2016)
19.
Censor-Hillel, K., Khoury, S., Paz, A.: Quadratic and near-quadratic lower bounds for the CONGEST model. In: DISC, pp. 10:1–10:16 (2017)
20.
Chan, T.M.: Speeding up the four Russians algorithm by about one more logarithmic factor. In: SODA, pp. 212–217 (2015)
21.
Chang, Y.-J., Pettie, S., Zhang, H.: Distributed triangle detection via expander decomposition. In: SODA, pp. 821–840 (2019)
22.
Chang, Y.-J., Saranurak, T.: Improved distributed expander decomposition and nearly optimal triangle enumeration. In: PODC, pp. 66–73 (2019)
23.
Czumaj, A., Lingas, A.: Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication. SIAM J. Comput. 39(2), 431–444 (2009)MathSciNetCrossRef
24.
Dolev, D., Lenzen, C., Peled, S.: “tri, tri again”: finding triangles and small subgraphs in a distributed setting. In: DISC, pp. 195–209. Springer (2012)
25.
Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 367–376 (2014)
26.
Elkin, M.: A simple deterministic distributed MST algorithm, with near-optimal time and message complexities. In: PODC, pp. 157–163. ACM (2017)
27.
28.
Fischer, O., Gonen, T., Kuhn, F., Oshman, R.: Possibilities and impossibilities for distributed subgraph detection. In: SPAA, pp. 153–162 (2018)
29.
Fraigniaud, P., Rapaport, I., Salo, V., Todinca, I.: Distributed testing of excluded subgraphs. In: DISC, pp. 342–356. Springer (2016)
30.
Frischknecht, S., Holzer, S., Wattenhofer, R.: Networks cannot compute their diameter in sublinear time. In: SODA, pp. 1150–1162 (2012)
31.
Håstad, J., Wigderson, A.: The randomized communication complexity of set disjointness. Theory Comput. 3(1), 211–219 (2007)MathSciNetCrossRef
32.
Henzinger, M., Krinninger, S., Nanongkai, D., Saranurak, T.: Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In: STOC, pp. 21–30. ACM (2015)
33.
34.
Izumi, T., Le Gall, F.: Triangle finding and listing in CONGEST networks. In: Proceedings of the ACM Symposium on Principles of Distributed Computing, (PODC), pp. 381–389 (2017)
35.
Jukna, S.: Extremal Combinatorics–with Applications in Computer Science. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2001)MATH
36.
Kari, J., Matamala, M., Rapaport, I., Salo, V.: Solving the induced subgraph problem in the randomized multiparty simultaneous messages model. In: SIROCCO, pp. 370–384. Springer (2015)
37.
King, V., Kutten, S., Thorup, M.: Construction and impromptu repair of an MST in a distributed network with o(m) communication. In: PODC, pp. 71–80. ACM (2015)
38.
Kolountzakis, M.N., Miller, G.L., Peng, R., Tsourakakis, C.E.: Efficient triangle counting in large graphs via degree-based vertex partitioning. Internet Math. 8(1–2), 161–185 (2012)MathSciNetCrossRef
39.
Kothapalli, K., Scheideler, C., Onus, M., Schindelhauer, C.: Distributed coloring in \(\tilde{O}(\sqrt{\log {n}})\) bit rounds. In: IPDPS (2006)
40.
Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local computation: lower and upper bounds. J. ACM 63(2), 17 (2016)MathSciNetCrossRef
41.
Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)MATH
42.
Le Gall, F.: Improved quantum algorithm for triangle finding via combinatorial arguments. In: FOCS, pp. 216–225. IEEE (2014)
43.
Le Gall, F.: Powers of tensors and fast matrix multiplication. In: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pp. 296–303. ACM (2014)
44.
Le Gall, F., Nakajima, S.: Multiparty quantum communication complexity of triangle finding. In: TQC (to appear) (2017)
45.
Le Gall, F., Nakajima, S.: Quantum algorithm for triangle finding in sparse graphs. Algorithmica 79(3), 941–959 (2017)MathSciNetCrossRef
46.
Lee, T., Magniez, F., Santha, M.: Improved quantum query algorithms for triangle finding and associativity testing. In: SODA, pp. 1486–1502. SIAM (2013)
47.
Lenzen, C., Patt-Shamir, B.: Improved distributed steiner forest construction. In: PODC, pp. 262–271 (2014)
48.
Linial, N.: Distributive graph algorithms global solutions from local data. In: Proceedings of the 28th Annual Symposium on Foundations of Computer Science, FOCS, pp. 331–335 (1987)
49.
50.
Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036–1053 (1986)MathSciNetCrossRef
51.
Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. SIAM J. Comput. 37(2), 413–424 (2007)MathSciNetCrossRef
52.
Métivier, Y., Robson, J.M., Saheb-Djahromi, N., Zemmari, A.: An optimal bit complexity randomized distributed MIS algorithm. Distrib. Comput. 23(5–6), 331–340 (2011)CrossRef
53.
Nanongkai, D., Sarma, A.D., Pandurangan, G.: A tight unconditional lower bound on distributed randomwalk computation. In: PODC, pp. 257–266. ACM (2011)
54.
Naor, M.: A lower bound on probabilistic algorithms for distributive ring coloring. SIAM J. Discrete Math. 4(3), 409–412 (1991)MathSciNetCrossRef
55.
56.
Pai, S., Pandurangan, G., Pemmaraju, S.V., Riaz, T., Robinson, P.: Symmetry breaking in the congest model: time- and message-efficient algorithms for ruling sets. In: DISC 2017 (2017). arXiv:​1705.​07861
57.
Pai, S., Pandurangan, G., Pemmaraju, S.V., Riaz, T., Robinson, P.: Symmetry breaking in the congest model: time-and message-efficient algorithms for ruling sets. In: PODC (to appear) (2017)
58.
59.
Pandurangan, G., Robinson, P., Scquizzato, M.: A time- and message-optimal distributed algorithm for minimum spanning trees. In: STOC, pp. 743–756. ACM (2017)
60.
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia (2000)CrossRef
61.
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)MathSciNetCrossRef
62.
Razborov, A.A.: On the distributional complexity of disjointness. Theor. Comput. Sci. 106(2), 385–390 (1992)MathSciNetCrossRef
63.
Sarma, A.D., Afrati, F.N., Salihoglu, S., Ullman, J.D.: Upper and lower bounds on the cost of a map-reduce computation. In: VLDB, vol. 6:4, pp. 277–288. VLDB Endowment (2013)
64.
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)MathSciNetCrossRef
65.
Schank, T., Wagner, D.: Finding, counting and listing all triangles in large graphs, an experimental study. In: WEA, pp. 606–609. Springer (2005)
66.
67.
Williams, V.V.: Multiplying matrices faster than Coppersmith-Winograd. In: STOC, pp. 887–898. ACM (2012)
68.
Williams, V.V.: Hardness of easy problems: basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 43 (2015)
69.
Williams, V.V., Williams, R.: Subcubic equivalences between path, matrix and triangle problems. In: FOCS, pp. 645–654 (2010)
70.
Yu, H.: An improved combinatorial algorithm for Boolean matrix multiplication. In: ICALP, pp. 1094–1105. Springer (2015)
Metadaten
Titel
Fooling views: a new lower bound technique for distributed computations under congestion
verfasst von
Amir Abboud
Keren Censor-Hillel
Seri Khoury
Christoph Lenzen
Publikationsdatum
09.04.2020
Verlag
Springer Berlin Heidelberg
Erschienen in
Distributed Computing / Ausgabe 6/2020
Print ISSN: 0178-2770
Elektronische ISSN: 1432-0452
DOI
https://doi.org/10.1007/s00446-020-00373-4

Weitere Artikel der Ausgabe 6/2020

Distributed Computing 6/2020 Zur Ausgabe

OriginalPaper

Communication complexity of approximate maximum matching in the message-passing model

OriginalPaper

The RedBlue family of universal constructions

OriginalPaper

Fault-tolerant simulation of population protocols

OriginalPaper

A tight lower bound for semi-synchronous collaborative grid exploration

OriginalPaper

Detecting cliques in CONGEST networks