Top

Distributed Computing

Published in:

30-08-2018

Randomized proof-labeling schemes

Authors: Pierre Fraigniaud, Boaz Patt-Shamir, Mor Perry

Published in: Distributed Computing | Issue 3/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Proof-labeling schemes, introduced by Korman et al. (Distrib Comput 22(4):215–233, 2010. https://doi.org/10.1007/s00446-010-0095-3), are a mechanism to certify that a network configuration satisfies a given boolean predicate. Such mechanisms find applications in many contexts, e.g., the design of fault-tolerant distributed algorithms. In a proof-labeling scheme, predicate verification consists of neighbors exchanging labels, whose contents depends on the predicate. In this paper, we introduce the notion of randomized proof-labeling schemes where messages are randomized and correctness is probabilistic. We show that randomization reduces verification complexity exponentially while guaranteeing probability of correctness arbitrarily close to one. We also present a novel message-size lower bound technique that applies to deterministic as well as randomized proof-labeling schemes. Using this technique, we establish several tight bounds on the verification complexity of MST, acyclicity, connectivity, and longest cycle size.

previous article Chemical foundations of distributed aspects

next article The topology of look-compute-move robot wait-free algorithms with hard termination

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

The existence of p is guaranteed by the Bertrand–Chebyshev theorem, stating that for every \(n>1\) there is always at least one prime p such that \(n<p<2n\).

Although we always refer to connected graphs in this paper, here we emphasize again that this is the set of graphs on which our schemes work. Distributed algorithms are relevant for disconnected graphs when the input graph is a sub-graph of the communication network (e.g., the congested clique [41]).

Afek, Y., Kutten, S., Yung, M.: The local detection paradigm and its application to self-stabilization. Theor. Comput. Sci. 186(1–2), 199–229 (1997). https://doi.org/10.1016/S0304-3975(96)00286-1 MathSciNetMATHCrossRef

Alstrup, S., Bille, P., Rauhe, T.: Labeling schemes for small distances in trees. SIAM J. Discrete Math. 19(2), 448–462 (2005). https://doi.org/10.1137/S0895480103433409 MathSciNetMATHCrossRef

Alstrup, S., Gavoille, C., Kaplan, H., Rauhe, T.: Nearest common ancestors: a survey and a new distributed algorithm. In: 14th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 258–264 (2002). https://doi.org/10.1145/564870.564914

Alstrup, S., Rauhe, T.: Small induced-universal graphs and compact implicit graph representations. In: 43rd Symposium on Foundations of Computer Science (FOCS), pp. 53–62 (2002). https://doi.org/10.1109/SFCS.2002.1181882

Arfaoui, H., Fraigniaud, P., Ilcinkas, D., Mathieu, F.: Distributedly testing cycle-freeness. In: Graph-Theoretic Concepts in Computer Science - 40th International Workshop. Revised Selected Papers, pp. 15–28 (2014). https://doi.org/10.1007/978-3-319-12340-0_2

Arfaoui, H., Fraigniaud, P., Pelc, A.: Local decision and verification with bounded-size outputs. In: Stabilization, Safety, and Security of Distributed Systems - 15th International Symposium, SSS. Proceedings, pp. 133–147 (2013). https://doi.org/10.1007/978-3-319-03089-0_10

Awerbuch, B., Patt-Shamir, B., Varghese, G.: Self-stabilization by local checking and correction (extended abstract). In: 32nd Annual Symposium on Foundations of Computer Science, pp. 268–277 (1991). https://doi.org/10.1109/SFCS.1991.185378

Blin, L., Fraigniaud, P., Patt-Shamir, B.: On proof-labeling schemes versus silent self-stabilizing algorithms. In: Stabilization, Safety, and Security of Distributed Systems - 16th International Symposium, SSS. Proceedings, pp. 18–32 (2014). https://doi.org/10.1007/978-3-319-11764-5_2

Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM J. Comput. 32(5), 1338–1355 (2003). https://doi.org/10.1137/S0097539702403098 MathSciNetMATHCrossRef

10.

Feuilloley, L., Fraigniaud, P.: Survey of distributed decision. Bulletin of the EATCS (2016). http://bulletin.eatcs.org/index.php/beatcs/article/view/411/391

11.

Feuilloley, L., Fraigniaud, P., Hirvonen, J.: A Hierarchy of Local Decision. In: 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 118:1–118:15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik (2016). http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.118. http://drops.dagstuhl.de/opus/volltexte/2016/6253

12.

Foerster, K., Luedi, T., Seidel, J., Wattenhofer, R.: Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNS. Theor. Comput. Sci. 709, 48–63 (2018). https://doi.org/10.1016/j.tcs.2016.11.018 MathSciNetMATHCrossRef

13.

Foerster, K.T., Richter, O., Seidel, J., Wattenhofer, R.: Local checkability in dynamic networks. In: Proceedings of the 18th International Conference on Distributed Computing and Networking (ICDCN ’17), pp. 4:1–4:10. ACM (2017). https://doi.org/10.1145/3007748.3007779

14.

Fraigniaud, P., Gavoille, C.: Routing in trees. In: Automata, Languages and Programming, 28th International Colloquium, ICALP, Proceedings, pp. 757–772 (2001). https://doi.org/10.1007/3-540-48224-5_62

15.

Fraigniaud, P., Gavoille, C.: A space lower bound for routing in trees. In: STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings, pp. 65–75 (2002). https://doi.org/10.1007/3-540-45841-7_4

16.

Fraigniaud, P., Göös, M., Korman, A., Parter, M., Peleg, D.: Randomized distributed decision. Distrib. Comput. 27(6), 419–434 (2014). https://doi.org/10.1007/s00446-014-0211-x MathSciNetMATHCrossRef

17.

Fraigniaud, P., Göös, M., Korman, A., Suomela, J.: What can be decided locally without identifiers? In: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, pp. 157–165. ACM (2013). https://doi.org/10.1145/2484239.2484264

18.

Fraigniaud, P., Halldórsson, M.M., Korman, A.: On the impact of identifiers on local decision. In: Principles of Distributed Systems: 16th International Conference, OPODIS. Proceedings, pp. 224–238. Springer, Berlin (2012). https://doi.org/10.1007/978-3-642-35476-2_16

19.

Fraigniaud, P., Hirvonen, J., Suomela, J.: Node labels in local decision. In: Structural Information and Communication Complexity: 22nd International Colloquium, SIROCCO. Post-Proceedings, pp. 31–45. Springer, Berlin (2015). https://doi.org/10.1007/978-3-319-25258-2_3

20.

Fraigniaud, P., Korman, A.: On randomized representations of graphs using short labels. In: SPAA: Proceedings of the 21st Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 131–137 (2009). https://doi.org/10.1145/1583991.1584031

21.

Fraigniaud, P., Korman, A., Peleg, D.: Towards a complexity theory for local distributed computing. J. ACM 60(5), 35:1–35:26 (2013). https://doi.org/10.1145/2499228 MathSciNetMATHCrossRef

22.

Fraigniaud, P., Rajsbaum, S., Travers, C.: Locality and checkability in wait-free computing. Distrib. Comput. 26(4), 223–242 (2013). https://doi.org/10.1007/s00446-013-0188-x MATHCrossRef

23.

Fraigniaud, P., Rajsbaum, S., Travers, C.: On the number of opinions needed for fault-tolerant run-time monitoring in distributed systems. In: Runtime Verification - 5th International Conference, RV. Proceedings, pp. 92–107 (2014). https://doi.org/10.1007/978-3-319-11164-3_9

24.

Gavoille, C., Katz, M., Katz, N.A., Paul, C., Peleg, D.: Approximate distance labeling schemes. In: 9th European Symposium on Algorithms (ESA), pp. 476–487 (2001). https://doi.org/10.1007/3-540-44676-1_40

25.

Gavoille, C., Paul, C.: Split decomposition and distance labelling: an optimal scheme for distance hereditary graphs. Electron. Notes Discrete Math. 10, 117–120 (2001). https://doi.org/10.1016/S1571-0653(04)00374-9 MathSciNetMATHCrossRef

26.

Gavoille, C., Peleg, D., Pérennes, S., Raz, R.: Distance labeling in graphs. J. Algorithms 53(1), 85–112 (2004). https://doi.org/10.1016/j.jalgor.2004.05.002 MathSciNetMATHCrossRef

27.

Göös, M., Suomela, J.: Locally checkable proofs in distributed computing. Theory Comput. 12(1), 1–33 (2016). https://doi.org/10.4086/toc.2016.v012a019 MathSciNetMATHCrossRef

28.

Hopcroft, J.E., Tarjan, R.E.: Efficient algorithms for graph manipulation. Commun. ACM 16(6), 372–378 (1973). https://doi.org/10.1145/362248.362272 CrossRef

29.

Itkis, G., Levin, L.A.: Fast and lean self-stabilizing asynchronous protocols. In: 35th Annual Symposium on Foundations of Computer Science, pp. 226–239 (1994). https://doi.org/10.1109/SFCS.1994.365691

30.

Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. SIAM J. Discrete Math. 5(4), 596–603 (1992). https://doi.org/10.1137/0405049 MathSciNetMATHCrossRef

31.

Kaplan, H., Milo, T.: Short and simple labels for small distances and other functions. In: 7th International Workshop on Algorithms and Data Structures (WADS), pp. 246–257 (2001). https://doi.org/10.1007/3-540-44634-6_23

32.

Katz, M., Katz, N.A., Korman, A., Peleg, D.: Labeling schemes for flow and connectivity. SIAM J. Comput. 34(1), 23–40 (2004). https://doi.org/10.1137/S0097539703433912 MathSciNetMATHCrossRef

33.

Katz, M., Katz, N.A., Peleg, D.: Distance labeling schemes for well-separated graph classes. Discrete Appl. Math. 145(3), 384–402 (2005). https://doi.org/10.1016/j.dam.2004.03.005 MathSciNetMATHCrossRef

34.

Korman, A.: Labeling schemes for vertex connectivity. ACM Trans. Algorithms. https://doi.org/10.1145/1721837.1721855 (2012)

35.

Korman, A., Kutten, S.: Distributed verification of minimum spanning trees. Distrib. Comput. 20(4), 253–266 (2007). https://doi.org/10.1007/s00446-007-0025-1 MATHCrossRef

36.

Korman, A., Kutten, S., Masuzawa, T.: Fast and compact self stabilizing verification, computation, and fault detection of an MST. In: 30th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 311–320 (2011). https://doi.org/10.1145/1993806.1993866

37.

Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. Distrib. Comput. 22(4), 215–233 (2010). https://doi.org/10.1007/s00446-010-0095-3 MATHCrossRef

38.

Korman, A., Peleg, D., Rodeh, Y.: Constructing labeling schemes through universal matrices. Algorithmica 57(4), 641–652 (2010). https://doi.org/10.1007/s00453-008-9226-7 MathSciNetMATHCrossRef

39.

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

40.

Kutten, S., Trehan, C.: Fast and compact distributed verification and self-stabilization of a DFS tree. In: Principles of Distributed Systems - 18th International Conference, OPODIS. Proceedings, pp. 323–338 (2014). https://doi.org/10.1007/978-3-319-14472-6_22

41.

Lotker, Z., Pavlov, E., Patt-Shamir, B., Peleg, D.: MST construction in \(o(log log n)\) communication rounds. In: SPAA: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 94–100 (2003). https://doi.org/10.1145/777412.777428

42.

Ostrovsky, R., Perry, M., Rosenbaum, W.: Space–time tradeoffs for distributed verification. In: Structural Information and Communication Complexity - 24th International Colloquium, SIROCCO, Revised Selected Papers, pp. 53–70 (2017). https://doi.org/10.1007/978-3-319-72050-0_4

43.

Papadimitriou, C.H.: Computational complexity. In: Encyclopedia of Computer Science, pp. 260–265. Wiley, Chichester. URL http://dl.acm.org/citation.cfm?id=1074100.1074233

44.

Peleg, D.: Proximity-preserving labeling schemes and their applications. In: 25th International Workshop Graph-Theoretic Concepts in Computer Science (WG), pp. 30–41 (1999). https://doi.org/10.1007/3-540-46784-X_5

45.

Peleg, D.: Informative labeling schemes for graphs. Theor. Comput. Sci. 340(3), 577–593 (2005). https://doi.org/10.1016/j.tcs.2005.03.015 MathSciNetMATHCrossRef

46.

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). https://doi.org/10.1137/11085178X MathSciNetMATHCrossRef

47.

Schmid, S., Suomela, J.: Exploiting locality in distributed SDN control. In: Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking (HotSDN), pp. 121–126. ACM (2013). https://doi.org/10.1145/2491185.2491198

48.

Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146–160 (1972). https://doi.org/10.1137/0201010 MathSciNetMATHCrossRef

49.

Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. In: 42nd Symposium on Foundations of Computer Science (FOCS), pp. 242–251 (2001). https://doi.org/10.1109/SFCS.2001.959898

50.

Thorup, M., Zwick, U.: Compact routing schemes. In: 13th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 1–10 (2001). https://doi.org/10.1145/378580.378581

Title: Randomized proof-labeling schemes
Authors: Pierre Fraigniaud
Boaz Patt-Shamir
Mor Perry
Publication date: 30-08-2018
Publisher: Springer Berlin Heidelberg
Published in: Distributed Computing / Issue 3/2019
Print ISSN: 0178-2770
Electronic ISSN: 1432-0452
DOI: https://doi.org/10.1007/s00446-018-0340-8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner