{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,20]],"date-time":"2025-04-20T19:40:08Z","timestamp":1745178008343,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642336508"},{"type":"electronic","value":"9783642336515"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33651-5_26","type":"book-chapter","created":{"date-parts":[[2012,11,13]],"date-time":"2012-11-13T09:25:32Z","timestamp":1352798732000},"page":"371-385","source":"Crossref","is-referenced-by-count":8,"title":["Randomized Distributed Decision"],"prefix":"10.1007","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amos","family":"Korman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Merav","family":"Parter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1-2","key":"26_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"},{"issue":"4","key":"26_CR2","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms\u00a07(4), 567\u2013583 (1986)","journal-title":"J. Algorithms"},{"key":"26_CR3","unstructured":"Amit, A., Linial, N., Matousek, J., Rozenman, E.: Random lifts of graphs. In: Proc. 12th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 883\u2013894 (2001)"},{"key":"26_CR4","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":"26_CR5","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M.: Distributed (\u0394\u2009+\u20091)-coloring in linear (in delta) time. In: Proc. 41st ACM Symp. on Theory of computing (STOC), pp. 111\u2013120 (2009)","DOI":"10.1145\/1536414.1536432"},{"key":"26_CR6","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"},{"key":"26_CR7","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.jpdc.2011.10.004","volume":"72","author":"D. Dereniowski","year":"2012","unstructured":"Dereniowski, D., Pelc, A.: Drawing maps with advice. Journal of Parallel and Distributed Computing\u00a072, 132\u2013143 (2012)","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"11","key":"26_CR8","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1145\/361179.361202","volume":"17","author":"E.W. Dijkstra","year":"1974","unstructured":"Dijkstra, E.W.: Self-stabilization in spite of distributed control. Comm. ACM\u00a017(11), 643\u2013644 (1974)","journal-title":"Comm. ACM"},{"issue":"6","key":"26_CR9","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":"26_CR10","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":"26_CR11","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.: D\u00a0Ilcinkas, and A.\u00a0Pelc. Communication algorithms with advice. J. Comput. Syst. Sci.\u00a076(3-4), 222\u2013232 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P.: A\u00a0Korman, and E.\u00a0Lebhar. 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":"26_CR13","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Korman, A., Peleg, D.: Local Distributed Decision. In: Proc. 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 708\u2013717 (2011)","DOI":"10.1109\/FOCS.2011.17"},{"key":"26_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":"26_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":"26_CR16","unstructured":"Fraigniaud, P., Rajsbaum, S., Travers, C.: Universal Distributed Checkers and Orientation-Detection Tasks (submitted, 2012)"},{"key":"26_CR17","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":"26_CR18","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":"26_CR19","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":"26_CR20","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":"26_CR21","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.: D\u00a0Peleg. Proof labeling schemes. Distributed Computing\u00a022, 215\u2013233 (2010)","journal-title":"Distributed Computing"},{"key":"26_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":"26_CR23","doi-asserted-by":"crossref","unstructured":"Kuhn, F.: Weak graph colorings: distributed algorithms and applications. In: Proc. 21st ACM Symp. on Parallel Algorithms and Architectures (SPAA), pp. 138\u2013144 (2009)","DOI":"10.1145\/1583991.1584032"},{"key":"26_CR24","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput.\u00a015, 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"26_CR25","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1137\/0404036","volume":"4","author":"M. Naor","year":"1991","unstructured":"Naor, M.: A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring. SIAM J. Discrete Math.\u00a04(3), 409\u2013412 (1991)","journal-title":"SIAM J. Discrete Math."},{"issue":"6","key":"26_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."},{"issue":"2","key":"26_CR27","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1006\/jagm.1996.0017","volume":"20","author":"A. Panconesi","year":"1996","unstructured":"Panconesi, A., Srinivasan, A.: On the Complexity of Distributed Network Decomposition. J. Algorithms\u00a020(2), 356\u2013374 (1996)","journal-title":"J. Algorithms"},{"key":"26_CR28","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"26_CR29","doi-asserted-by":"crossref","unstructured":"Schneider, J., Wattenhofer, R.: A new technique for distributed symmetry breaking. In: Proc. 29th ACM Symp. on Principles of Distributed Computing (PODC), pp. 257\u2013266 (2010)","DOI":"10.1145\/1835698.1835760"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33651-5_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,20]],"date-time":"2025-04-20T19:21:19Z","timestamp":1745176879000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33651-5_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642336508","9783642336515"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33651-5_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}