Randomized proof-labeling schemes
Tóm tắt
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.
Tài liệu tham khảo
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
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
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
Feuilloley, L., Fraigniaud, P.: Survey of distributed decision. Bulletin of the EATCS (2016). http://bulletin.eatcs.org/index.php/beatcs/article/view/411/391
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Korman, A.: Labeling schemes for vertex connectivity. ACM Trans. Algorithms. https://doi.org/10.1145/1721837.1721855 (2012)
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
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
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
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
Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)
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
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
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
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
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
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
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
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
Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146–160 (1972). https://doi.org/10.1137/0201010
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
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