{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T04:58:13Z","timestamp":1764133093473,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319690834"},{"type":"electronic","value":"9783319690841"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-69084-1_1","type":"book-chapter","created":{"date-parts":[[2017,10,5]],"date-time":"2017-10-05T23:30:06Z","timestamp":1507246206000},"page":"1-17","source":"Crossref","is-referenced-by-count":5,"title":["Proof-Labeling Schemes: Broadcast, Unicast and in Between"],"prefix":"10.1007","author":[{"given":"Boaz","family":"Patt-Shamir","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mor","family":"Perry","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,10,7]]},"reference":[{"key":"1_CR1","volume-title":"Network Flows","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows. Prentice-Hall, Engelwood Cliffs (1993)"},{"key":"1_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/978-3-319-12340-0_2","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H Arfaoui","year":"2014","unstructured":"Arfaoui, H., Fraigniaud, P., Ilcinkas, D., Mathieu, F.: Distributedly testing cycle-freeness. In: Kratsch, D., Todinca, I. (eds.) WG 2014. LNCS, vol. 8747, pp. 15\u201328. Springer, Cham (2014). doi: 10.1007\/978-3-319-12340-0_2"},{"key":"1_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/978-3-319-03089-0_10","volume-title":"Stabilization, Safety, and Security of Distributed Systems","author":"H Arfaoui","year":"2013","unstructured":"Arfaoui, H., Fraigniaud, P., Pelc, A.: Local decision and verification with bounded-size outputs. In: Higashino, T., Katayama, Y., Masuzawa, T., Potop-Butucaru, M., Yamashita, M. (eds.) SSS 2013. LNCS, vol. 8255, pp. 133\u2013147. Springer, Cham (2013). doi: 10.1007\/978-3-319-03089-0_10"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Patt-Shamir, B., Varghese, G.: Self-stabilization by local checking and correction. In: 32nd Symposium on Foundations of Computer Science (FOCS), pp. 268\u2013277. IEEE (1991)","DOI":"10.1109\/SFCS.1991.185378"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Baruch, M., Fraigniaud, P., Patt-Shamir, B.: Randomized proof-labeling schemes. In: Proceedings of 34th ACM Symposium on Principles of Distributed Computing (PODC), pp. 315\u2013324 (2015)","DOI":"10.1145\/2767386.2767421"},{"key":"1_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-319-42634-1_15","volume-title":"Computing and Combinatorics","author":"F Becker","year":"2016","unstructured":"Becker, F., Anta, A.F., Rapaport, I., R\u00e9mila, E.: The effect of range and bandwidth on the round complexity in the congested clique model. In: Dinh, T.N., Thai, M.T. (eds.) COCOON 2016. LNCS, vol. 9797, pp. 182\u2013193. Springer, Cham (2016). doi: 10.1007\/978-3-319-42634-1_15"},{"key":"1_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/978-3-319-11764-5_2","volume-title":"Stabilization, Safety, and Security of Distributed Systems","author":"L Blin","year":"2014","unstructured":"Blin, L., Fraigniaud, P., Patt-Shamir, B.: On proof-labeling schemes versus silent self-stabilizing algorithms. In: Felber, P., Garg, V. (eds.) SSS 2014. LNCS, vol. 8756, pp. 18\u201332. Springer, Cham (2014). doi: 10.1007\/978-3-319-11764-5_2"},{"issue":"5","key":"1_CR8","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/11085178X","volume":"41","author":"A Das Sarma","year":"2012","unstructured":"Das Sarma, A., 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."},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In: Proceedings of 2014 ACM Symposium on Principles of Distributed Computing, PODC 2014, pp. 367\u2013376. ACM, New York (2014)","DOI":"10.1145\/2611462.2611493"},{"key":"1_CR10","unstructured":"Feuilloley, L., Fraigniaud, P., Hirvonen, J.: A hierarchy of local decision. In: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), pp. 118:1\u2013118:15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016)"},{"key":"1_CR11","doi-asserted-by":"crossref","unstructured":"Foerster, K.-T., Luedi, T., Seidel, J., Wattenhofer, R.: Local checkability, no strings attached. In: Proceedings of 17th International Conference on Distributed Computing and Networking, ICDCN 2016, pp. 21:1\u201321:10. ACM, New York (2016)","DOI":"10.1145\/2833312.2833315"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"Foerster, K.-T., Richter, O., Seidel, J., Wattenhofer, R.: Local checkability in dynamic networks. In: Proceedings of 18th International Conference on Distributed Computing and Networking, ICDCN 2017, pp. 4:1\u20134:10. ACM, New York (2017)","DOI":"10.1145\/3007748.3007779"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., G\u00f6\u00f6s, M., Korman, A., Suomela, J.: What can be decided locally without identifiers? In: Proceedings of 2013 ACM Symposium on Principles of Distributed Computing, PODC 2013, pp. 157\u2013165. ACM, New York (2013)","DOI":"10.1145\/2484239.2484264"},{"key":"1_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/978-3-642-35476-2_16","volume-title":"Principles of Distributed Systems","author":"P Fraigniaud","year":"2012","unstructured":"Fraigniaud, P., Halld\u00f3rsson, M.M., Korman, A.: On the impact of identifiers on local decision. In: Baldoni, R., Flocchini, P., Binoy, R. (eds.) OPODIS 2012. LNCS, vol. 7702, pp. 224\u2013238. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-35476-2_16"},{"key":"1_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-319-25258-2_3","volume-title":"Structural Information and Communication Complexity","author":"P Fraigniaud","year":"2015","unstructured":"Fraigniaud, P., Hirvonen, J., Suomela, J.: Node labels in local decision. In: Scheideler, C. (ed.) Structural Information and Communication Complexity. LNCS, vol. 9439, pp. 31\u201345. Springer, Cham (2015). doi: 10.1007\/978-3-319-25258-2_3"},{"issue":"5","key":"1_CR16","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1145\/2499228","volume":"60","author":"P Fraigniaud","year":"2013","unstructured":"Fraigniaud, P., Korman, A., Peleg, D.: Towards a complexity theory for local distributed computing. J. ACM 60(5), 35 (2013)","journal-title":"J. ACM"},{"issue":"4","key":"1_CR17","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s00446-013-0188-x","volume":"26","author":"P Fraigniaud","year":"2013","unstructured":"Fraigniaud, P., Rajsbaum, S., Travers, C.: Locality and checkability in wait-free computing. Distrib. Comput. 26(4), 223\u2013242 (2013)","journal-title":"Distrib. Comput."},{"key":"1_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/978-3-319-11164-3_9","volume-title":"Runtime Verification","author":"P Fraigniaud","year":"2014","unstructured":"Fraigniaud, P., Rajsbaum, S., Travers, C.: On the number of opinions needed for fault-tolerant run-time monitoring in distributed systems. In: Bonakdarpour, B., Smolka, S.A. (eds.) RV 2014. LNCS, vol. 8734, pp. 92\u2013107. Springer, Cham (2014). doi: 10.1007\/978-3-319-11164-3_9"},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Suomela, J.: Locally checkable proofs. In: 30th ACM Symposium on Principles of Distributed Computing (PODC), pp. 159\u2013168 (2011)","DOI":"10.1145\/1993806.1993829"},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/s00446-007-0025-1","volume":"20","author":"A Korman","year":"2007","unstructured":"Korman, A., Kutten, S.: Distributed verification of minimum spanning trees. Distrib. Comput. 20, 253\u2013266 (2007)","journal-title":"Distrib. Comput."},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"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\u2013320 (2011)","DOI":"10.1145\/1993806.1993866"},{"issue":"4","key":"1_CR22","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s00446-010-0095-3","volume":"22","author":"A Korman","year":"2010","unstructured":"Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. Distrib. Comput. 22(4), 215\u2013233 (2010)","journal-title":"Distrib. Comput."},{"key":"1_CR23","doi-asserted-by":"publisher","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":"1_CR24","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1112\/jlms\/s1-36.1.445","volume":"s1\u201336","author":"CSA Nash-Williams","year":"1961","unstructured":"Nash-Williams, C.S.A.: Edge-disjoint spanning trees of finite graphs. J. Lond. Math. Soc. s1\u201336(1), 445\u2013450 (1961)","journal-title":"J. Lond. Math. Soc."},{"issue":"1","key":"1_CR25","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1112\/jlms\/s1-39.1.12","volume":"s1\u201339","author":"CSA Nash-Williams","year":"1964","unstructured":"Nash-Williams, C.S.A.: Decomposition of finite graphs into forests. J. Lond. Math. Soc. s1\u201339(1), 12 (1964)","journal-title":"J. Lond. Math. Soc."},{"key":"1_CR26","first-page":"1","volume-title":"Lecture Notes in Computer Science","author":"Boaz Patt-Shamir","year":"2017","unstructured":"Patt-Shamir, B., Perry, M.: Proof-labeling schemes: broadcast, unicast and in between. CoRR, abs\/1708.06947 (2017)"},{"key":"1_CR27","doi-asserted-by":"publisher","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)"}],"container-title":["Lecture Notes in Computer Science","Stabilization, Safety, and Security of Distributed Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-69084-1_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T05:16:41Z","timestamp":1570166201000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-69084-1_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319690834","9783319690841"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-69084-1_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}