{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,16]],"date-time":"2026-09-16T08:34:18Z","timestamp":1789547658553,"version":"build-2803163510"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,6,7]],"date-time":"2013-06-07T00:00:00Z","timestamp":1370563200000},"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":[[2013,8]]},"DOI":"10.1007\/s00446-013-0188-x","type":"journal-article","created":{"date-parts":[[2013,6,6]],"date-time":"2013-06-06T07:12:03Z","timestamp":1370502723000},"page":"223-242","source":"Crossref","is-referenced-by-count":28,"title":["Locality and checkability in wait-free computing"],"prefix":"10.1007","volume":"26","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sergio","family":"Rajsbaum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Corentin","family":"Travers","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2013,6,7]]},"reference":[{"key":"188_CR1","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors. In: 12th Annual ACM Symposium on Theory of Computing (STOC), pp. 82\u201393 (1980)","DOI":"10.1145\/800141.804655"},{"key":"188_CR2","doi-asserted-by":"crossref","unstructured":"Afek, Y., Merritt, M., Taubenfeld, G., Touitou, D.: Disentangling multi-object operations. In: 16th ACM Symposium on Principle of Distributed Computing (PODC), pp. 111\u2013120 (1997)","DOI":"10.1145\/259380.259431"},{"issue":"2","key":"188_CR3","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/s00446-011-0134-8","volume":"25","author":"J Aspnes","year":"2012","unstructured":"Aspnes, J.: A modular approach to shared-memory consensus, with applications to the probabilistic-write model. Distrib. Comput. 25(2), 179\u2013188 (2012)","journal-title":"Distrib. Comput."},{"issue":"3","key":"188_CR4","doi-asserted-by":"crossref","first-page":"524","DOI":"10.1145\/79147.79158","volume":"37","author":"H Attiya","year":"1990","unstructured":"Attiya, H., Bar-Noy, A., Dolev, D., Peleg, D., Reischuck, R.: Renaming in asynchronous environment. J. ACM 37(3), 524\u2013548 (1990)","journal-title":"J. ACM"},{"key":"188_CR5","doi-asserted-by":"crossref","unstructured":"Aspnes, J., Ellen F.: Tight bounds for adopt-commit objects. Theory Comput. Syst. (2013, to appear). Published online February 6th, 2013. doi: 10.1007\/s00224-013-9448-1","DOI":"10.1007\/s00224-013-9448-1"},{"key":"188_CR6","unstructured":"Awerbuch, B., Patt-Shamir, B., Varghese, G.: Self-stabilization by Local Checking and Correction. In: 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 268\u2013277 (1991)"},{"key":"188_CR7","unstructured":"Awerbuch, B. Varghese, G.: Distributed program checking: a paradigm for building self-stabilizing distributed protocols. In: 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 258\u2013267 (1991)"},{"key":"188_CR8","doi-asserted-by":"crossref","DOI":"10.1002\/0471478210","volume-title":"Distributed Computing: Fundamentals, Simulations, and Advanced Topics","author":"H Attiya","year":"2004","unstructured":"Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations, and Advanced Topics. Wiley, New York (2004)"},{"issue":"5","key":"188_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2027216.2027221","volume":"58","author":"L Barenboim","year":"2011","unstructured":"Barenboim, L., Elkin, M.: Deterministic distributed vertex coloring in polylogarithmic time. J. ACM (JACM) 58(5), 1\u201325 (2011)","journal-title":"J. ACM (JACM)"},{"key":"188_CR10","doi-asserted-by":"crossref","unstructured":"Borowsky, E., Gafni, E.: Immediate atomic snapshots and fast renaming. In: 12th ACM Symposium on Principles of Distributed Computing (PODC), pp. 41\u201351 (1993)","DOI":"10.1145\/164051.164056"},{"issue":"3","key":"188_CR11","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/PL00008933","volume":"14","author":"E Borowsky","year":"2001","unstructured":"Borowsky, E., Gafni, E., Lynch, N., Rajsbaum, S.: The BG distributed simulation algorithm. Distrib. Comput. 14(3), 127\u2013146 (2001)","journal-title":"Distrib. Comput."},{"issue":"1","key":"188_CR12","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1145\/200836.200880","volume":"42","author":"M Blum","year":"1995","unstructured":"Blum, M., Kannan, S.: Designing programs that check their work. J. ACM 42(1), 269\u2013291 (1995)","journal-title":"J. ACM"},{"issue":"3","key":"188_CR13","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"M Blum","year":"1993","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with applications to numerical problems. J. Comput. Syst. Sci. 47(3), 549\u2013595 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"188_CR14","doi-asserted-by":"crossref","unstructured":"Chalopin, J., Godard, E., M\u00e9tivier, Y.: Local terminations and distributed computability in anonymous networks. In: 22nd International Symposium on Distributed Computing (DISC), Lecture Notes in Computer Science. vol. 5218, pp. 47\u201362 (2008)","DOI":"10.1007\/978-3-540-87779-0_4"},{"issue":"3","key":"188_CR15","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/s00446-010-0115-3","volume":"23","author":"J Chalopin","year":"2010","unstructured":"Chalopin, J., M\u00e9tivier, Y.: On the power of synchronization between two adjacent processes. Distrib. Comput. 23(3), 177\u2013196 (2010)","journal-title":"Distrib. Comput."},{"issue":"1","key":"188_CR16","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1006\/inco.1993.1043","volume":"105","author":"S Chaudhuri","year":"1993","unstructured":"Chaudhuri, S.: More choices allow more faults: set consensus problems in totally asynchronous systems. Inf. Comput. 105(1), 132\u2013158 (1993)","journal-title":"Inf. Comput."},{"issue":"1","key":"188_CR17","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R Cole","year":"1986","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control 70(1), 32\u201353 (1986)","journal-title":"Inf. Control"},{"issue":"5","key":"188_CR18","doi-asserted-by":"crossref","first-page":"1235","DOI":"10.1137\/11085178X","volume":"41","author":"SA Das","year":"2012","unstructured":"Das, S.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."},{"issue":"3","key":"188_CR19","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1145\/5925.5931","volume":"33","author":"D Dolev","year":"1986","unstructured":"Dolev, D., Lynch, N., Pinter, S., Stark, E., Weihl, W.: Reaching approximate agreement in the presence of faults. J. ACM 33(3), 499\u2013516 (1986)","journal-title":"J. ACM"},{"issue":"3","key":"188_CR20","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1006\/jcss.1999.1692","volume":"60","author":"F Erg\u00fcn","year":"2000","unstructured":"Erg\u00fcn, F., Kannan, S., Kumar, R., Rubinfeld, R., Viswanathan, M.: Spot-checkers. J. Comput. Syst. Sci. 60(3), 717\u2013751 (2000)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"188_CR21","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1145\/3149.214121","volume":"32","author":"M Fischer","year":"1985","unstructured":"Fischer, M., Lynch, N., Paterson, M.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374\u2013382 (1985)","journal-title":"J. ACM"},{"issue":"3\u20134","key":"188_CR22","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/j.jcss.2009.07.002","volume":"76","author":"P Fraigniaud","year":"2010","unstructured":"Fraigniaud, P., Ilcinkas, D., Pelc, A.: Communication algorithms with advice. J. Comput. Syst. Sci. 76(3\u20134), 222\u2013232 (2010)","journal-title":"J. Comput. Syst. Sci."},{"key":"188_CR23","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Korman, A., Peleg, D.: Local distributed decision. In: 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 708\u2013717 (2011)","DOI":"10.1109\/FOCS.2011.17"},{"key":"188_CR24","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Rajsbaum, S., Travers, C.: Locality and checkability in wait-free computing. In: 25th International Symposium on Distributed Computing (DISC). Lecture Notes in Computer Science, vol. 6950, pp. 333\u2013347 (2011)","DOI":"10.1007\/978-3-642-24100-0_34"},{"key":"188_CR25","doi-asserted-by":"crossref","unstructured":"Franklin, M., Garay, J.A., Yung, M.: Self-testing\/correcting protocols. In: 13th International Symposium on Distributed Computing (DISC). Lecture Notes in Computer Science, vol. 1693, pp. 269\u2013284 (1999)","DOI":"10.1007\/3-540-48169-9_19"},{"issue":"1","key":"188_CR26","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1006\/inco.1997.2648","volume":"138","author":"Y Freund","year":"1997","unstructured":"Freund, Y., Kearns, M., Ron, D., Rubinfeld, R., Schapire, R., Sellie, L.: Efficient learning of typical finite automata from random walks. Inf. Comput. 138(1), 23\u201348 (1997)","journal-title":"Inf. Comput."},{"key":"188_CR27","doi-asserted-by":"crossref","unstructured":"Gafni, E.: The 0\u20131-exclusion families of tasks. In: 12th International Conference on Principles of Distributed Systems (OPODIS). Lecture Notes in Computer Science, vol. 5401, pp. 246\u2013258 (2008)","DOI":"10.1007\/978-3-540-92221-6_17"},{"key":"188_CR28","unstructured":"Gafni E.: Round-by-round fault detectors: unifying synchrony and asynchrony (Extended Abstract). In: 17th ACM Symposium on Principles of Distributed Computing (PODC), pp. 143\u2013152 (1998)"},{"issue":"3","key":"188_CR29","doi-asserted-by":"crossref","first-page":"970","DOI":"10.1137\/S0097539796305766","volume":"28","author":"E Gafni","year":"1999","unstructured":"Gafni, E., Koutsoupias, E.: Three-processor tasks are undecidable. SIAM J. Comput. 28(3), 970\u2013983 (1999)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"188_CR30","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. ACM 45(4), 653\u2013750 (1998)","journal-title":"J. ACM"},{"key":"188_CR31","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Gutfreund, D., Healy, A., Kaufman, T., Rothblum, G.: A (De)constructive approach to program checking. In: 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 143\u2013152 (2008)","DOI":"10.1145\/1374376.1374399"},{"key":"188_CR32","doi-asserted-by":"crossref","unstructured":"Goos, 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":"188_CR33","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1145\/114005.102808","volume":"13","author":"M Herlihy","year":"1991","unstructured":"Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13, 124\u2013149 (1991)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"188_CR34","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Rajsbaum, S.: The decidability of distributed decision tasks (Extended Abstract). In: 29th Annual ACM Symposium on the Theory of Computing (STOC), pp. 589\u2013598 (1997)","DOI":"10.1145\/258533.258652"},{"issue":"1","key":"188_CR35","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0304-3975(01)00396-6","volume":"291","author":"M Herlihy","year":"2003","unstructured":"Herlihy, M., Rajsbaum, S.: A classification of wait-free loop agreement tasks. Theor. Comput. Sci. 291(1), 55\u201377 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"188_CR36","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Shavit, N.: The topological structure of asynchronous computability. J. ACM 46(6), 858\u2013923 (1999)","DOI":"10.1145\/331524.331529"},{"key":"188_CR37","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":"188_CR38","doi-asserted-by":"crossref","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":"188_CR39","doi-asserted-by":"crossref","unstructured":"Korman, A., Sereni, J.-S., Viennot, L: Toward more localized local algorithms: removing assumptions concerning global knowledge. In: 30th ACM Symposium on Principles of Distributed Computing (PODC), pp. 49\u201358 (2011)","DOI":"10.1145\/1993806.1993814"},{"key":"188_CR40","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In: 25th ACM Symposium on Principles of Distributed Computing (PODC), pp. 7\u201315 (2006)","DOI":"10.1145\/1146381.1146387"},{"issue":"1","key":"188_CR41","doi-asserted-by":"crossref","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. 21(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"key":"188_CR42","first-page":"191","volume":"2","author":"R Lipton","year":"1991","unstructured":"Lipton, R.: New directions in testing. DIMACS Workshop Distrib. Comput. Cryptogr. 2, 191\u2013202 (1991)","journal-title":"DIMACS Workshop Distrib. Comput. Cryptogr."},{"issue":"21\u201323","key":"188_CR43","doi-asserted-by":"crossref","first-page":"2162","DOI":"10.1016\/j.tcs.2009.01.033","volume":"410","author":"X Liu","year":"2009","unstructured":"Liu, X., Xu, Z., Pan, J.: Classifying rendezvous tasks of arbitrary dimension. Theor. Comput. Sci. 410(21\u201323), 2162\u20132173 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"188_CR44","volume-title":"Distributed Algorithms","author":"N Lynch","year":"1996","unstructured":"Lynch, N.: Distributed Algorithms. Morgan Kaufmann Publishers, San Francisco (1996)"},{"key":"188_CR45","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/S0020-0190(97)00022-7","volume":"61","author":"A Mazurkiewicz","year":"1997","unstructured":"Mazurkiewicz, A.: Distributed enumeration. Inf. Process. Lett. 61, 233\u2013239 (1997)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"188_CR46","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1142\/S0129626401000452","volume":"11","author":"A Mostefaoui","year":"2001","unstructured":"Mostefaoui, A., Raynal, M.: Leader-based consensus. Parallel Process. Lett. 11(2), 95\u2013107 (2001)","journal-title":"Parallel Process. Lett."},{"key":"188_CR47","doi-asserted-by":"crossref","unstructured":"Mostefaoui, A., Raynal, M.: Solving consensus using chandra-Toueg\u2019s unreliable failure detectors: a general quorum-based approach. In: 13th International Symposium on Distributed Computing (DISC). Lecture Notes in Computer Science, vol. 1693, pp. 49\u201363 (1999)","DOI":"10.1007\/3-540-48169-9_4"},{"issue":"6","key":"188_CR48","doi-asserted-by":"crossref","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. 24(6), 1259\u20131277 (1995)","journal-title":"SIAM J. Comput."},{"key":"188_CR49","doi-asserted-by":"crossref","unstructured":"Peleg D.: Distributed computing: a locality-sensitive approach. SIAM (2000)","DOI":"10.1137\/1.9780898719772"},{"issue":"4","key":"188_CR50","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1216\/RMJ-1973-3-4-641","volume":"3","author":"J Rotman","year":"1973","unstructured":"Rotman, J.: Covering complexes with applications to algebra. Rocky Mt. J. Math. 3(4), 641\u2013674 (1973)","journal-title":"Rocky Mt. J. Math."},{"issue":"4","key":"188_CR51","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/BF01961540","volume":"15","author":"R Rubinfeld","year":"1996","unstructured":"Rubinfeld, R.: Designing checkers for programs that run in parallel. Algorithmica 15(4), 287\u2013301 (1996)","journal-title":"Algorithmica"},{"key":"188_CR52","doi-asserted-by":"crossref","unstructured":"Yang, J., Neiger, G. Gafni, E.: Structured derivations of consensus algorithms for failure detectors. In: 17th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 297\u2013306 (1998)","DOI":"10.1145\/277697.277755"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-013-0188-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-013-0188-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-013-0188-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,14]],"date-time":"2019-07-14T20:09:39Z","timestamp":1563134979000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-013-0188-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6,7]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,8]]}},"alternative-id":["188"],"URL":"https:\/\/doi.org\/10.1007\/s00446-013-0188-x","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,6,7]]}}}