{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,16]],"date-time":"2026-09-16T08:34:19Z","timestamp":1789547659095,"version":"build-2803163510"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319030883","type":"print"},{"value":"9783319030890","type":"electronic"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-319-03089-0_10","type":"book-chapter","created":{"date-parts":[[2013,10,17]],"date-time":"2013-10-17T15:18:14Z","timestamp":1382023094000},"page":"133-147","source":"Crossref","is-referenced-by-count":9,"title":["Local Decision and Verification with Bounded-Size Outputs"],"prefix":"10.1007","author":[{"given":"Heger","family":"Arfaoui","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"1-2","key":"10_CR1","doi-asserted-by":"publisher","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 applications to self stabilization. Theoretical Computer Science\u00a0186(1-2), 199\u2013230 (1997)","journal-title":"Theoretical Computer Science"},{"key":"10_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-31104-8_12","volume-title":"Structural Information and Communication Complexity","author":"H. Arfaoui","year":"2012","unstructured":"Arfaoui, H., Fraigniaud, P.: What Can Be Computed without Communications? In: Even, G., Halld\u00f3rsson, M.M. (eds.) SIROCCO 2012. LNCS, vol.\u00a07355, pp. 135\u2013146. Springer, Heidelberg (2012)"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Patt-Shamir, B., Varghese, G.: Self-Stabilization By Local Checking and Correction. In: Proc. IEEE Symp. on the Foundations of Computer Science (FOCS), pp. 268\u2013277 (1991)","DOI":"10.1109\/SFCS.1991.185378"},{"key":"10_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/BFb0020443","volume-title":"Distributed Algorithms","author":"B. Awerbuch","year":"1994","unstructured":"Awerbuch, B., Patt-Shamir, B., Varghese, G., Dolev, S.: Self-Stabilization by Local Checking and Global Reset. In: Tel, G., Vit\u00e1nyi, P. (eds.) WDAG 1994. LNCS, vol.\u00a0857, pp. 326\u2013339. Springer, Heidelberg (1994)"},{"key":"10_CR5","doi-asserted-by":"crossref","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. In: Proc. 43rd ACM Symp. on Theory of Computing, STOC (2011)","DOI":"10.1145\/1993636.1993686"},{"issue":"6","key":"10_CR6","doi-asserted-by":"publisher","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 Informatica\u00a036(6), 447\u2013462 (1999)","journal-title":"Acta Informatica"},{"key":"10_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/978-3-540-73420-8_22","volume-title":"Automata, Languages and Programming","author":"P. Fraigniaud","year":"2007","unstructured":"Fraigniaud, P., Gavoille, C., Ilcinkas, D., Pelc, A.: Distributed Computing with Advice: Information Sensitivity of Graph Coloring. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 231\u2013242. Springer, Heidelberg (2007)"},{"issue":"3-4","key":"10_CR8","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1016\/j.jcss.2009.07.002","volume":"76","author":"P. Fraigniaud","year":"2008","unstructured":"Fraigniaud, P., Ilcinkas, D., Pelc, A.: Communication algorithms with advice. J. Comput. Syst. Sci.\u00a076(3-4), 222\u2013232 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"10_CR9","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.\u00a07702, pp. 224\u2013238. Springer, Heidelberg (2012)"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Korman, A., Lebhar, E.: Local MST computation with short advice. In: Proc. 19th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pp. 154\u2013160 (2007)","DOI":"10.1145\/1248377.1248402"},{"key":"10_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/978-3-642-33651-5_26","volume-title":"Distributed Computing","author":"P. Fraigniaud","year":"2012","unstructured":"Fraigniaud, P., Korman, A., Parter, M., Peleg, D.: Randomized Distributed Decision. In: Aguilera, M.K. (ed.) DISC 2012. LNCS, vol.\u00a07611, pp. 371\u2013385. Springer, Heidelberg (2012)"},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Korman, A., Peleg, D.: Local Distributed Decision. In: Proc. 52nd Annual IEEE Symp. on Foundations of Computer Science (FOCS), pp. 708\u2013717 (2011)","DOI":"10.1109\/FOCS.2011.17"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., G\u00f6\u00f6s, M., Korman, A., Suomela, J.: What can be decided locally without identifiers? In: 32nd ACM Symp. on Principles of Distributed Computing, PODC (2013)","DOI":"10.1145\/2484239.2484264"},{"key":"10_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/978-3-642-29344-3_31","volume-title":"LATIN 2012: Theoretical Informatics","author":"P. Fraigniaud","year":"2012","unstructured":"Fraigniaud, P., Pelc, A.: Decidability Classes for Mobile Agents\u00a0Computing. In: Fern\u00e1ndez-Baca, D. (ed.) LATIN 2012. LNCS, vol.\u00a07256, pp. 362\u2013374. Springer, Heidelberg (2012)"},{"key":"10_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/978-3-642-24100-0_34","volume-title":"Distributed Computing","author":"P. Fraigniaud","year":"2011","unstructured":"Fraigniaud, P., Rajsbaum, S., Travers, C.: Locality and Checkability in Wait-Free Computing. In: Peleg, D. (ed.) DISC 2011. LNCS, vol.\u00a06950, pp. 333\u2013347. Springer, Heidelberg (2011)"},{"key":"10_CR16","unstructured":"Fraigniaud, P., Rajsbaum, S., Travers, C.: An Impossibility Result for Run-Time Monitoring (submitted, 2013)"},{"key":"10_CR17","series-title":"Lecture Notes in Computer Science","volume-title":"Property Testing","year":"2010","unstructured":"Goldreich, O. (ed.): Property Testing. LNCS, vol.\u00a06390. Springer, Heidelberg (2010)"},{"issue":"2","key":"10_CR18","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/s00453-001-0078-7","volume":"32","author":"O. Goldreich","year":"2002","unstructured":"Goldreich, O., Ron, D.: Property Testing in Bounded Degree Graphs. Algorithmica\u00a032(2), 302\u2013343 (2002)","journal-title":"Algorithmica"},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Suomela, J.: Locally checkable proofs. In: Proc. 30th ACM Symp. on Principles of Distributed Computing, PODC (2011)","DOI":"10.1145\/1993806.1993829"},{"key":"10_CR20","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/BF02278852","volume":"7","author":"S. Katz","year":"1993","unstructured":"Katz, S., Perry, K.: Self-stabilizing extensions to for message-passing systems. Distributed Computing\u00a07, 17\u201326 (1993)","journal-title":"Distributed Computing"},{"key":"10_CR21","unstructured":"Kor, L., Korman, A., Peleg, D.: Tight Bounds For Distributed MST Verification. In: Proc. 28th Int. Symp. on Theoretical Aspects of Computer Science, STACS (2011)"},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"Korman, A., Sereni, J.S., Viennot, L.: Toward More Localized Local Algorithms: Removing Assumptions Concerning Global Knowledge. In: Proc. 30th ACM Symp. on Principles of Distributed Computing, PODC, pp. 49\u201358 (2011)","DOI":"10.1145\/1993806.1993814"},{"key":"10_CR23","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. Distributed Computing\u00a020, 253\u2013266 (2007)","journal-title":"Distributed Computing"},{"key":"10_CR24","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: Proc. 30th ACM Symp. on Principles of Distributed Computing, PODC (2011)","DOI":"10.1145\/1993806.1993866"},{"key":"10_CR25","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. Distributed Computing\u00a022, 215\u2013233 (2010)","journal-title":"Distributed Computing"},{"issue":"6","key":"10_CR26","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M. Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? SIAM J. Comput.\u00a024(6), 1259\u20131277 (1995)","journal-title":"SIAM J. Comput."},{"key":"10_CR27","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM (2000)","DOI":"10.1137\/1.9780898719772"}],"container-title":["Lecture Notes in Computer Science","Stabilization, Safety, and Security of Distributed Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-03089-0_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T17:25:55Z","timestamp":1746033955000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-03089-0_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319030883","9783319030890"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-03089-0_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}