Y. Afek, S. Kutten, and M. Yung, The local detection paradigm and its applications to self-stabilization, Theoretical Computer Science, vol.186, issue.1-2, pp.199-230, 1997.
DOI : 10.1016/S0304-3975(96)00286-1

D. Angluin, Local and Global Properties in Networks of Processors, Proc. Twelfth ACM Symp. on Theory of Computing (STOC), pp.82-93, 1980.

A. Amit, N. Linial, J. Matousek, and E. Rozenman, Random lifts of graphs, Proc. 12th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp.883-894, 2001.

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

L. Barenboim and M. Elkin, Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time, Proc. 41st ACM Symp. on Theory of computing (STOC), pp.111-120, 2009.
DOI : 10.1137/12088848X

A. D. Sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai et al., Distributed Verification and Hardness of Distributed Approximation, Proc. 43rd ACM Symp. on Theory of Computing (STOC), 2011.
DOI : 10.1137/11085178X

D. Dereniowski and A. Pelc, Drawing maps with advice, Journal of Parallel and Distributed Computing, vol.72, issue.2, pp.132-143, 2012.
DOI : 10.1016/j.jpdc.2011.10.004

S. Dolev, M. Gouda, and M. Schneider, Memory requirements for silent stabilization, Acta Informatica, vol.36, issue.6, pp.447-462, 1999.
DOI : 10.1007/s002360050180

R. G. Gallager, P. A. Humblet, and P. M. Spira, A distributed algorithm for minimumweight spanning trees, ACM Trans. on Programming Languages and Systems, pp.5-66, 1983.

P. Fraigniaud, C. Gavoille, D. Ilcinkas, and A. Pelc, Distributed Computing with Advice: Information Sensitivity of Graph Coloring, Proc. 34th Colloq. on Automata , Languages and Programming (ICALP), pp.231-242, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00339878

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

P. Fraigniaud, A. Korman, and E. Lebhar, Local MST computation with short advice, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures , SPAA '07, pp.154-160, 2007.
DOI : 10.1145/1248377.1248402
URL : https://hal.archives-ouvertes.fr/hal-00154849

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

P. Fraigniaud, A. Korman, M. Parter, and D. Peleg, Randomized Distributed Decision
URL : https://hal.archives-ouvertes.fr/hal-01093255

P. Fraigniaud and A. Pelc, Decidability Classes for Mobile Agents??Computing, Proc. LATIN 2012: Theoretical Informatics -10th Latin American Symposium, 2012.
DOI : 10.1007/978-3-642-29344-3_31

P. Fraigniaud, S. Rajsbaum, and C. Travers, Locality and Checkability in Waitfree Computing, Proc. 25th International Symposium on Distributed Computing (DISC), 2011.
URL : https://hal.archives-ouvertes.fr/hal-00992781

P. Fraigniaud, S. Rajsbaum, and C. Travers, Universal Distributed Checkers and Orientation-Detection Tasks, 2012.

E. Fusco and A. Pelc, Communication Complexity of Consensus in Anonymous Message Passing Systems, Proc. 15th International Conference on Principles of Distributed Systems (OPODIS 2011), pp.191-206
DOI : 10.1007/978-3-642-25873-2_14

M. Göös and J. Suomela, Locally checkable proofs, Proc. 30th ACM Symp. on Principles of Distributed Computing (PODC), 2011.

M. Göös, J. Hirvonen, and J. Suomela, Lower bounds for local approximation, Proc. 31st Symposium on Principles of Distributed Computing (PODC), 2012.

H. Hasemann, J. Hirvonen, J. Rybicki, and J. Suomela, Deterministic Local Algorithms , Unique Identifiers, and Fractional Graph Colouring, Proc. 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2012.

M. Hanckowiak, M. Karonski, and A. Panconesi, On the Distributed Complexity of Computing Maximal Matchings, SIAM Journal on Discrete Mathematics, vol.15, issue.1, pp.41-57, 2001.
DOI : 10.1137/S0895480100373121

L. Kor, A. Korman, and D. Peleg, Tight Bounds For Distributed MST Verification, Proc. 28th Int. Symp. on Theoretical Aspects of Computer Science (STACS), 2011.
URL : https://hal.archives-ouvertes.fr/hal-00573623

A. Korman and S. Kutten, Distributed verification of minimum spanning trees, Distributed Computing, vol.26, issue.1, pp.253-266, 2007.
DOI : 10.1007/s00446-007-0025-1

A. Korman, S. Kutten, and T. Masuzawa, Fast and Compact Self-Stabilizing Verification, Computation, and Fault Detection of an MST, Proc. 30th ACM Symp. on Principles of Distributed Computing (PODC), 2011.
URL : https://hal.archives-ouvertes.fr/hal-01240211

A. Korman, S. Kutten, and D. Peleg, Proof labeling schemes. Detailed version

A. Korman, J. S. 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, pp.49-58, 2011.
DOI : 10.1145/1993806.1993814
URL : https://hal.archives-ouvertes.fr/hal-01241086

F. Kuhn, Weak graph colorings, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, SPAA '09, pp.138-144, 2009.
DOI : 10.1145/1583991.1584032

M. Luby, A Simple Parallel Algorithm for the Maximal Independent Set Problem, SIAM Journal on Computing, vol.15, issue.4, pp.1036-1053, 1986.
DOI : 10.1137/0215074

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

A. Panconesi and A. Srinivasan, On the Complexity of Distributed Network Decomposition, Journal of Algorithms, vol.20, issue.2, pp.356-374, 1996.
DOI : 10.1006/jagm.1996.0017

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

D. Seinsche, On a property of the class of n-colorable graphs, Journal of Combinatorial Theory, Series B, vol.16, issue.2, pp.191-193, 1974.
DOI : 10.1016/0095-8956(74)90063-X