D. Angluin, Local and global properties in networks of processors (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing , STOC '80, pp.28-30, 1980.
DOI : 10.1145/800141.804655

B. Awerbuch, B. Patt-shamir, and G. Varghese, Self-stabilization by local checking and correction, [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, pp.268-277, 1991.
DOI : 10.1109/SFCS.1991.185378
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.211.8704

H. Attiya, A. Bar-noy, D. Dolev, D. Peleg, and R. Reischuck, Renaming in an asynchronous environment, Journal of the ACM, vol.37, issue.3, pp.524-548, 1990.
DOI : 10.1145/79147.79158

H. Attiya and S. Rajsbaum, The Combinatorial Structure of Wait-Free Solvable Tasks, SIAM Journal on Computing, vol.31, issue.4, pp.1286-1313, 2002.
DOI : 10.1137/S0097539797330689

B. Awerbuch and G. Varghese, Distributed program checking: a paradigm for building self-stabilizing distributed protocols, [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, pp.258-267, 1991.
DOI : 10.1109/SFCS.1991.185377

L. Barenboim and M. Elkin, Deterministic distributed vertex coloring in polylogarithmic time, 29th ACM Symp. on Principles of Distributed Computing (PODC), pp.410-419, 2010.

M. Blum and S. Kannan, Designing programs that check their work, Journal of the ACM, vol.42, issue.1, pp.269-291, 1995.
DOI : 10.1145/200836.200880
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.2537

M. Blum, M. Luby, and R. Rubinfeld, Self-testing/correcting with applications to numerical problems, Journal of Computer and System Sciences, vol.47, issue.3, pp.549-595, 1993.
DOI : 10.1016/0022-0000(93)90044-W

S. Chaudhuri, More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems, Information and Computation, vol.105, issue.1, pp.132-158, 1993.
DOI : 10.1006/inco.1993.1043

J. Chalopin, E. Godard, and Y. Métivier, Local Terminations and Distributed Computability in Anonymous Networks, 22nd International Symposium on Distributed Computing (DISC), pp.47-62, 2008.
DOI : 10.1007/978-3-540-87779-0_4
URL : https://hal.archives-ouvertes.fr/hal-00332759

J. Chalopin and Y. Métivier, On the power of synchronization between two adjacent processes, Distributed Computing, vol.10, issue.9, pp.177-196, 2010.
DOI : 10.1007/s00446-010-0115-3
URL : https://hal.archives-ouvertes.fr/hal-00527102

R. Cole and U. Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control, vol.70, issue.1, p.3253, 1986.
DOI : 10.1016/S0019-9958(86)80023-7

D. Dolev, N. Lynch, S. Pinter, E. Stark, and W. Weihl, Reaching approximate agreement in the presence of faults, Journal of the ACM, vol.33, issue.3, pp.499-516, 1986.
DOI : 10.1145/5925.5931

F. Ergün, S. Kannan, R. Kumar, R. Rubinfeld, and M. Viswanathan, Spot-Checkers, Journal of Computer and System Sciences, vol.60, issue.3, pp.717-751, 2000.
DOI : 10.1006/jcss.1999.1692

M. Fischer, N. Lynch, and M. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM, vol.32, issue.2, pp.374-382, 1985.
DOI : 10.1145/3149.214121

P. Fraigniaud, D. Ilcinkas, and A. Pelc, Communication algorithms with advice, Journal of Computer and System Sciences, vol.76, issue.3-4, pp.3-4, 2010.
DOI : 10.1016/j.jcss.2009.07.002
URL : https://hal.archives-ouvertes.fr/hal-00412058

P. Fraigniaud, A. Korman, and D. Peleg, Local Distributed Decision, 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
DOI : 10.1109/FOCS.2011.17
URL : https://hal.archives-ouvertes.fr/hal-00912561

Y. Freund, M. Kearns, D. Ron, R. Rubinfeld, R. Schapire et al., Efficient Learning of Typical Finite Automata from Random Walks, Information and Computation, vol.138, issue.1, pp.23-48, 1997.
DOI : 10.1006/inco.1997.2648

E. Gafni and E. Koutsoupias, Three-Processor Tasks Are Undecidable, SIAM Journal on Computing, vol.28, issue.3, pp.970-983, 1999.
DOI : 10.1137/S0097539796305766
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.5196

S. Goldwasser, D. Gutfreund, A. Healy, T. Kaufman, and G. Rothblum, A (de)constructive approach to program checking, Proceedings of the fourtieth annual ACM symposium on Theory of computing, STOC 08, pp.143-152, 2008.
DOI : 10.1145/1374376.1374399

O. Goldreich, S. Goldwasser, S. , and R. D. , Property testing and its connection to learning and approximation, Journal of the ACM, vol.45, issue.4, pp.653-750, 1998.
DOI : 10.1145/285055.285060
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.6097

M. Goos and J. Suomela, Locally checkable proofs, 30th ACM Symp. on Principles of Distributed Computing, 2011.

M. Herlihy and S. Rajsbaum, The decidability of distributed decision tasks (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing , STOC '97, pp.589-598, 1997.
DOI : 10.1145/258533.258652

M. Herlihy and S. Rajsbaum, A classification of wait-free loop agreement tasks, Theoretical Computer Science, vol.291, issue.1, pp.55-77, 2003.
DOI : 10.1016/S0304-3975(01)00396-6

M. Herlihy and N. Shavit, The topological structure of asynchronous computability, Journal of the ACM, vol.46, issue.6, pp.858-923, 1999.
DOI : 10.1145/331524.331529

A. Korman, J. Sereni, and L. Viennot, Toward more localized local algorithms, Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing, PODC '11, 2011.
DOI : 10.1145/1993806.1993814
URL : https://hal.archives-ouvertes.fr/hal-01241086

F. Kuhn and R. Wattenhofer, On the complexity of distributed graph coloring, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing , PODC '06, pp.7-15, 2006.
DOI : 10.1145/1146381.1146387

R. Lipton, New Directions in Testing, DIMACS workshop on distributed computing and cryptography, vol.2, pp.191-202, 1991.

N. Lynch, Distributed Algorithms, 1996.

A. Mazurkiewicz, Distributed enumeration, Information Processing Letters, vol.61, issue.5, pp.233-239, 1997.
DOI : 10.1016/S0020-0190(97)00022-7

M. Naor and L. Stockmeyer, What Can be Computed Locally?, SIAM Journal on Computing, vol.24, issue.6, pp.1259-1277, 1995.
DOI : 10.1137/S0097539793254571

D. Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM, 2000.
DOI : 10.1137/1.9780898719772

J. Rotman, Covering complexes with applications to algebra, Rocky Mountain Journal of Mathematics, vol.3, issue.4, pp.641-674, 1973.
DOI : 10.1216/RMJ-1973-3-4-641

R. Rubinfeld, Designing checkers for programs that run in parallel, Algorithmica, vol.7, issue.4, pp.287-301, 1996.
DOI : 10.1007/BF01961540