{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T16:59:35Z","timestamp":1780073975640,"version":"3.54.0"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,3,3]],"date-time":"2010-03-03T00:00:00Z","timestamp":1267574400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2010,5]]},"DOI":"10.1007\/s00446-010-0095-3","type":"journal-article","created":{"date-parts":[[2010,3,2]],"date-time":"2010-03-02T12:34:06Z","timestamp":1267533246000},"page":"215-233","source":"Crossref","is-referenced-by-count":138,"title":["Proof labeling schemes"],"prefix":"10.1007","volume":"22","author":[{"given":"Amos","family":"Korman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shay","family":"Kutten","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2010,3,3]]},"reference":[{"issue":"5","key":"95_CR1","doi-asserted-by":"crossref","first-page":"745","DOI":"10.1006\/jpdc.2001.1823","volume":"62","author":"Y. Afek","year":"2002","unstructured":"Afek Y., Dolev S.: Local stabilizer. J. Parallel Distrib. Comput. 62(5), 745\u2013765 (2002)","journal-title":"J. Parallel Distrib. Comput."},{"issue":"1\u20132","key":"95_CR2","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/S0304-3975(96)00286-1","volume":"186","author":"Y. Afek","year":"1997","unstructured":"Afek Y., Kutten S., Yung M.: The local detection paradigm and its application to self-stabilization. Theor. Comput. Sci. 186(1\u20132), 199\u2013229 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"95_CR3","doi-asserted-by":"crossref","unstructured":"Aggarwal, S., Kutten, S.: Time optimal self-stabilizing spanning tree algorithms. In: Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 400\u2013410 (1993)","DOI":"10.1007\/3-540-57529-4_72"},{"key":"95_CR4","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processes. In: Proceedings of the 12th ACM Symposium on Theory of Computing, pp. 82\u201393 (1980)","DOI":"10.1145\/800141.804655"},{"key":"95_CR5","doi-asserted-by":"crossref","unstructured":"Arora, A., Gouda, M.: Distributed reset (extended abstract) In: Proceedings of the 10th Conference on Foundations of Software Technology and Theoretical Computer Science Bangalore, India, pp. 316\u2013331 (1990)","DOI":"10.1007\/3-540-53487-3_54"},{"key":"95_CR6","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Kutten, S., Mansour, Y., Patt-Shamir, B., Varghese, G.: Time optimal self-stabilizing synchronization. In: Proceedings of the ACM Symposium on the Theory of Computer Science, pp. 652\u2013661 (1993)","DOI":"10.1145\/167088.167256"},{"key":"95_CR7","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Patt-Shamir, B., Varghese, G.: Self-stabilization by local checking and correction. In: Proceedings of the IEEE Symposium on the Foundations of Computer Science, pp. 268\u2013277 (1991)","DOI":"10.1109\/SFCS.1991.185378"},{"key":"95_CR8","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Patt-Shamir, B., Varghese, G., Dolev, S.: Self-stabilization by local checking and global reset. In: Proceedings of the Workshop on Distributed Algorithms. Lecture Notes in Computer Science 857, pp. 326\u2013339. Springer (1994)","DOI":"10.1007\/BFb0020443"},{"key":"95_CR9","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Varghese, G.: Distributed program checking: a paradigm for building self-stabilizing distributed protocols. In: Proceedins of the IEEE Symposium on the Foundations of Computer Science, pp. 258\u2013267 (1991)","DOI":"10.1109\/SFCS.1991.185377"},{"key":"95_CR10","doi-asserted-by":"crossref","unstructured":"Beauquier, J., Delaet, S., Dolev, S., Tixeuil, S.: Transient Fault Detectors. In: Proceedings of the 12th International Symposium on Distributed Computing, LNCS 1499, pp. 62\u201374. Springer-Verlag (1998)","DOI":"10.1007\/BFb0056474"},{"key":"95_CR11","doi-asserted-by":"crossref","unstructured":"Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Labeling schemes for tree representation. In: Proceedings of the 7th International Workshop on Distributed Computing, LNCS 3741, pp. 13\u201324. Springer (2005)","DOI":"10.1007\/11603771_2"},{"key":"95_CR12","doi-asserted-by":"crossref","unstructured":"Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-guided graph exploration by a finite automaton. In: Proceedings of the 32nd International Colloquium on Automata, Languages, and Programming, pp. 335\u2013346 (2005)","DOI":"10.1007\/11523468_28"},{"issue":"11","key":"95_CR13","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1145\/361179.361202","volume":"17","author":"E.W. Dijkstra","year":"1974","unstructured":"Dijkstra E.W.: Self-stabilizing systems in spite of distributed control. Commun. ACM 17(11), 643\u2013644 (1974)","journal-title":"Commun. ACM"},{"issue":"6","key":"95_CR14","doi-asserted-by":"crossref","first-page":"1184","DOI":"10.1137\/0221070","volume":"21","author":"B. Dixon","year":"1992","unstructured":"Dixon B., Rauch M., Tarjan R.E.: Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM J. Comput. 21(6), 1184\u20131192 (1992)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"95_CR15","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1007\/s002360050180","volume":"36","author":"S. Dolev","year":"1999","unstructured":"Dolev S., Gouda M., Schneider M.: Requirements for silent stabilization. Acta Inform. 36(6), 447\u2013462 (1999)","journal-title":"Acta Inform."},{"issue":"1","key":"95_CR16","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02278851","volume":"7","author":"S. Dolev","year":"1993","unstructured":"Dolev S., Israeli A., Moran S.: Self-stabilization of dynamic systems assuming only read\/write atomicity. Distrib. Comput. J. 7(1), 3\u201316 (1993)","journal-title":"Distrib. Comput. J."},{"issue":"4","key":"95_CR17","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1109\/71.588622","volume":"8","author":"S. Dolev","year":"1997","unstructured":"Dolev S., Israeli A., Moran S.: Uniform dynamic self-stabilizing leader election. IEEE Trans. Parallel Distrib. Syst. 8(4), 424\u2013440 (1997)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"95_CR18","unstructured":"Even, S.: Graph Algorithms. Computer Science Press (1979)"},{"key":"95_CR19","volume-title":"Computers and Intractability","author":"M. Garey","year":"1979","unstructured":"Garey M., Johnson D.: Computers and Intractability. W.H. Freeman and Company, New York (1979)"},{"key":"95_CR20","doi-asserted-by":"crossref","unstructured":"Fredman, M.L., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. In: Proceedings of the 31st Annual Symposium on Foundations of Computer Science. Los Alamitos, CA, pp. 719\u2013725 (1990)","DOI":"10.1109\/FSCS.1990.89594"},{"key":"95_CR21","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/357195.357200","volume":"5","author":"R.G. Gallager","year":"1983","unstructured":"Gallager R.G., Humblet P.A., Spira P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. 5, 66\u201377 (1983)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"95_CR22","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1145\/568438.568451","volume":"32","author":"C. Gavoille","year":"2001","unstructured":"Gavoille C.: Routing in distributed networks: overview and open problems. ACM SIGACT News-Distrib. Comput. Column 32, 36\u201352 (2001)","journal-title":"ACM SIGACT News-Distrib. Comput. Column"},{"issue":"1","key":"95_CR23","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.jalgor.2004.05.002","volume":"53","author":"C. Gavoille","year":"2004","unstructured":"Gavoille C., Peleg D., P\u00e9rennes S., Raz R.: Distance labeling in graphs. J. Algorithms 53(1), 85\u2013112 (2004)","journal-title":"J. Algorithms"},{"key":"95_CR24","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Ilcinkas, D., Pelc, A.: Oracle size: a new measure of difficulty for communication tasks. In: Proceedings of the 25th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 179\u2013187 (2006)","DOI":"10.1145\/1146381.1146410"},{"key":"95_CR25","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Ilcinkas, D., Pelc, A.: Tree exploration with an oracle. In: Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science, pp. 24\u201337 (2006)","DOI":"10.1007\/11821069_2"},{"key":"95_CR26","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Korman, A., Lebhar, E.: Local MST computation with short advice. In: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 154\u2013160 (2007)","DOI":"10.1145\/1248377.1248402"},{"key":"95_CR27","doi-asserted-by":"crossref","unstructured":"Jayaram, G.M., Varghese, G.: Crash failures can drive protocols to arbitrary states. In: Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing, pp. 247\u2013256 (1996)","DOI":"10.1145\/248052.248104"},{"key":"95_CR28","doi-asserted-by":"crossref","unstructured":"Jayaram, G.M., Varghese, G.: The complexity of crash failures. In: Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing, pp. 179\u2013188","DOI":"10.1145\/259380.259438"},{"key":"95_CR29","unstructured":"Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. In: SIAM Joural on Descrete Mathematics 5, 596\u2013603 (1992)"},{"issue":"2","key":"95_CR30","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/201019.201022","volume":"42","author":"D.R. Karger","year":"1955","unstructured":"Karger D.R., Klein P.N., Tarjan R.E.: A randomized linear-time algorithm to find minimum spanning trees. J. ACM 42(2), 321\u2013328 (1955)","journal-title":"J. ACM"},{"key":"95_CR31","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1137\/S0097539703433912","volume":"34","author":"M. Katz","year":"2004","unstructured":"Katz M., Katz N.A., Korman A., Peleg D.: Labeling schemes for flow and connectivity. SIAM J. Comput. 34, 23\u201340 (2004)","journal-title":"SIAM J. Comput."},{"key":"95_CR32","doi-asserted-by":"crossref","unstructured":"Korman, A.: Labeling schemes for vertex connectivity. In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming, pp. 102\u2013109 (2007)","DOI":"10.1007\/978-3-540-73420-8_11"},{"key":"95_CR33","unstructured":"Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. A detailed version. http:\/\/ie.technion.ac.il\/~kutten\/pdf\/ProofLabelingSchemes.pdf"},{"key":"95_CR34","doi-asserted-by":"crossref","unstructured":"Korman, A., Kutten, S.: Distributed verification of minimum spanning trees. In: Proceedings of the 25th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Denver, Colorado, USA, pp. 26\u201334 (2006)","DOI":"10.1145\/1146381.1146389"},{"key":"95_CR35","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proceedings of the ACM Symposium on the Principles of Distributed Computing, pp. 300\u2013309 (2004)","DOI":"10.1145\/1011767.1011811"},{"key":"95_CR36","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nissan, N.: Communication complexity. Cambridge University Press (1997)","DOI":"10.1016\/S0065-2458(08)60342-3"},{"key":"95_CR37","doi-asserted-by":"crossref","unstructured":"Linial, N.: Distributive graph algorithms-global solutions from local data. In: IEEE Symposium on the Foundations of Computer Science, pp. 331\u2013335 (1987)","DOI":"10.1109\/SFCS.1987.20"},{"key":"95_CR38","doi-asserted-by":"crossref","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? In: Proceedings of the 25th ACM Symposium on Theory of Computing, pp. 184\u2013193 (1993)","DOI":"10.1145\/167088.167149"},{"key":"95_CR39","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1145\/65950.65953","volume":"36","author":"D. Peleg","year":"1989","unstructured":"Peleg D., Upfal E.: A tradeoff between size and efficiency for routing tables. J. ACM 36, 510\u2013530 (1989)","journal-title":"J. ACM"},{"key":"95_CR40","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"95_CR41","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1002\/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5","volume":"33","author":"D. Peleg","year":"2000","unstructured":"Peleg D.: Proximity-preserving labeling schemes. J. Graph Theory 33, 167\u2013176 (2000)","journal-title":"J. Graph Theory"},{"key":"95_CR42","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Informative Labeling Schemes for Graphs, Theoretical Computer Science 340. Special Issue of MFCS\u201900 papers pp. 577\u2013593 (2005)","DOI":"10.1016\/j.tcs.2005.03.015"},{"key":"95_CR43","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1093\/comjnl\/28.1.5","volume":"28","author":"N. Santoro","year":"1985","unstructured":"Santoro N., Khatib R.: Labeling and implicit routing in networks. Comput. J. 28, 5\u20138 (1985)","journal-title":"Comput. J."},{"key":"95_CR44","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/31846.32978","volume":"34","author":"P. Tiwari","year":"1987","unstructured":"Tiwari P.: Lower bounds on communication complexity in distributed computer networks. J. ACM 34, 921\u2013938 (1987)","journal-title":"J. ACM"},{"key":"95_CR45","doi-asserted-by":"crossref","unstructured":"Wattenhofer, M., Wattenhofer, R.: Distributed weighted matching. In: Proceedings of the 18th International Symposium on Distributed Computing. LNCS 3274, pp. 335\u2013348. Springer (2004)","DOI":"10.1007\/978-3-540-30186-8_24"},{"key":"95_CR46","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Some complexity questions related to distributed computing. In: Proceedings of the 11th ACM Symposium on Theory of Computing, pp. 209\u2013213 (1979)","DOI":"10.1145\/800135.804414"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-010-0095-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-010-0095-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-010-0095-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:26:43Z","timestamp":1559136403000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-010-0095-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3,3]]},"references-count":46,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,5]]}},"alternative-id":["95"],"URL":"https:\/\/doi.org\/10.1007\/s00446-010-0095-3","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3,3]]}}}