{"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":1789547659297,"version":"build-2803163510"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642354755","type":"print"},{"value":"9783642354762","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-35476-2_16","type":"book-chapter","created":{"date-parts":[[2012,12,13]],"date-time":"2012-12-13T20:48:14Z","timestamp":1355431694000},"page":"224-238","source":"Crossref","is-referenced-by-count":18,"title":["On the Impact of Identifiers on Local Decision"],"prefix":"10.1007","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amos","family":"Korman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"1-2","key":"16_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":"16_CR2","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and Global Properties in Networks of Processors. In: Proc. Twelfth ACM Symp. on Theory of Computing, STOC, pp. 82\u201393 (1980)","DOI":"10.1145\/800141.804655"},{"key":"16_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":"16_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":"16_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":"16_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":"16_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":"6","key":"16_CR8","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":"16_CR9","doi-asserted-by":"publisher","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. on Programming Languages and Systems\u00a05, 66\u201377 (1983)","journal-title":"ACM Trans. on Programming Languages and Systems"},{"key":"16_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":"16_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., 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":"16_CR12","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":"16_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":"16_CR14","unstructured":"Fraigniaud, P., Korman, A., Parter, M., Peleg, D.: Randomized Distributed Decision, http:\/\/arxiv.org\/abs\/1207.0252"},{"key":"16_CR15","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":"16_CR16","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":"16_CR17","unstructured":"Fraigniaud, P., Rajsbaum, S., Travers, C.: Universal Distributed Checkers and Orientation-Detection Tasks (submitted, 2012)"},{"key":"16_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/978-3-642-25873-2_14","volume-title":"Principles of Distributed Systems","author":"E.G. Fusco","year":"2011","unstructured":"Fusco, E.G., Pelc, A.: Communication Complexity of Consensus in Anonymous Message Passing Systems. In: Fern\u00e0ndez Anta, A., Lipari, G., Roy, M. (eds.) OPODIS 2011. LNCS, vol.\u00a07109, pp. 191\u2013206. Springer, Heidelberg (2011)"},{"key":"16_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":"16_CR20","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Hirvonen, J., Suomela, J.: Lower bounds for local approximation. In: Proc. 31st Symposium on Principles of Distributed Computing, PODC (2012)","DOI":"10.1145\/2332432.2332465"},{"key":"16_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/978-3-642-31104-8_5","volume-title":"Structural Information and Communication Complexity","author":"H. Hasemann","year":"2012","unstructured":"Hasemann, H., Hirvonen, J., Rybicki, J., Suomela, J.: Deterministic Local Algorithms, Unique Identifiers, and Fractional Graph Colouring. In: Even, G., Halld\u00f3rsson, M.M. (eds.) SIROCCO 2012. LNCS, vol.\u00a07355, pp. 48\u201360. Springer, Heidelberg (2012)"},{"issue":"1","key":"16_CR22","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1137\/S0895480100373121","volume":"15","author":"M. Hanckowiak","year":"2001","unstructured":"Hanckowiak, M., Karonski, M., Panconesi, A.: On the Distributed Complexity of Computing Maximal Matchings. SIAM J. Discrete Math.\u00a015(1), 41\u201357 (2001)","journal-title":"SIAM J. Discrete Math."},{"key":"16_CR23","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":"16_CR24","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":"16_CR25","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":"16_CR26","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"},{"key":"16_CR27","unstructured":"Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. Detailed version, http:\/\/ie.technion.ac.il\/~kutten\/ps-links\/ProofLabelingSchemes.ps"},{"key":"16_CR28","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":"16_CR29","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"},{"issue":"1","key":"16_CR30","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput.\u00a021(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"16_CR31","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1137\/080714403","volume":"39","author":"Z. Lotker","year":"2009","unstructured":"Lotker, Z., Patt-Shamir, B., Rosen, A.: Distributed Approximate Matching. SIAM J. Comput.\u00a039(2), 445\u2013460 (2009)","journal-title":"SIAM J. Comput."},{"key":"16_CR32","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":"6","key":"16_CR33","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":"16_CR34","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":"16_CR35","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"16_CR36","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0095-8956(74)90063-X","volume":"16","author":"D. Seinsche","year":"1974","unstructured":"Seinsche, D.: On a property of the class of n-colorable graphs. J. Combinatorial Theory, Ser. B\u00a016, 191\u2013193 (1974)","journal-title":"J. Combinatorial Theory, Ser. B"}],"container-title":["Lecture Notes in Computer Science","Principles of Distributed Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-35476-2_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T17:39:57Z","timestamp":1745429997000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-35476-2_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642354755","9783642354762"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-35476-2_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}