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-229, 1997.
DOI : 10.1016/S0304-3975(96)00286-1

K. Akkaya and M. Younis, A survey on routing protocols for wireless sensor networks, Ad Hoc Networks, vol.3, issue.3, pp.325-349, 2005.
DOI : 10.1016/j.adhoc.2003.09.010

L. Noga-alon, A. Babai, and . Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, vol.7, issue.4, pp.567-583, 1986.
DOI : 10.1016/0196-6774(86)90019-2

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.82-93, 1980.
DOI : 10.1145/800141.804655

H. Arfaoui and P. Fraigniaud, What can be computed without communication, Proceedings of the 19th International Colloquium on Structural Information and Communication Complexity, pp.135-146, 2012.
DOI : 10.1007/978-3-642-31104-8_12
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.394.737

H. Arfaoui, P. Fraigniaud, and A. Pelc, Local Decision and Verification with Bounded-Size Outputs, SSS, pp.133-147, 2013.
DOI : 10.1007/978-3-319-03089-0_10
URL : https://hal.archives-ouvertes.fr/hal-00922700

E. Arjomandi, M. J. Fischer, and N. A. Lynch, Efficiency of Synchronous Versus Asynchronous Distributed Systems, Journal of the ACM, vol.30, issue.3, pp.449-456, 1983.
DOI : 10.1145/2402.322387

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

B. Awerbuch, Complexity of network synchronization, Journal of the ACM, vol.32, issue.4, pp.804-823, 1985.
DOI : 10.1145/4221.4227

B. Awerbuch, M. Luby, A. V. Goldberg, and S. A. Plotkin, Network decomposition and locality in distributed computation, 30th Annual Symposium on Foundations of Computer Science, pp.364-369, 1989.
DOI : 10.1109/SFCS.1989.63504

B. Awerbuch, B. Patt-shamir, G. Varghese, and S. Dolev, Self-stabilization by local checking and global reset, pp.326-339
DOI : 10.1007/BFb0020443

L. Barenboim and M. Elkin, Distributed Graph Coloring: Fundamentals and Recent Developments. Synthesis Lectures on Distributed Computing Theory Morgan &amp, 2013.
DOI : 10.2200/s00520ed1v01y201307dct011

L. Barenboim and M. Elkin, Distributed (??+1)-coloring in linear (in ??) time, Proceedings of the 41st annual ACM symposium on Symposium on theory of computing, STOC '09, pp.111-120, 2009.
DOI : 10.1145/1536414.1536432

L. Barenboim, M. Elkin, S. Pettie, and J. Schneider, The locality of distributed symmetry breaking, Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, FOCS '12, pp.321-330, 2012.

J. Barrett, N. Linden, S. Massar, S. Pironio, S. Popescu et al., Nonlocal correlations as an information-theoretic resource, Physical Review A, vol.71, issue.2, 2005.
DOI : 10.1103/PhysRevA.71.022101

J. Barrett and S. Pironio, Popescu-Rohrlich Correlations as a Unit of Nonlocality, Physical Review Letters, vol.95, issue.14, 2005.
DOI : 10.1103/PhysRevLett.95.140401

F. Becker, M. Matamala, N. Nisse, I. Rapaport, K. Suchan et al., Adding a Referee to an Interconnection Network: What Can(not) Be Computed in One Round, 2011 IEEE International Parallel & Distributed Processing Symposium, pp.508-514, 2011.
DOI : 10.1109/IPDPS.2011.55
URL : https://hal.archives-ouvertes.fr/inria-00528733

J. Stewart and B. , On the einstein-podolsky-rosen paradox, Physics, vol.1, issue.3, pp.195-200, 1964.

Y. Birk, L. Liss, A. Schuster, and R. Wolff, A Local Algorithm for Ad Hoc Majority Voting via Charge Fusion, pp.275-289
DOI : 10.1007/978-3-540-30186-8_20

G. Brassard, A. Broadbent, and A. Tapp, Quantum Pseudo-Telepathy, Foundations of Physics, vol.55, issue.6, pp.1877-1907, 2005.
DOI : 10.1007/s10701-005-7353-4
URL : http://arxiv.org/abs/quant-ph/0407221

A. Broadbent and A. Tapp, Can quantum mechanics help distributed computing? SIGACT News, pp.67-76, 2008.

J. J. Buckley and T. E. Westen, The majority rule game, International Journal of Game Theory, vol.28, issue.2, pp.105-112, 1975.
DOI : 10.1007/BF01766189

J. Clauser, M. Horne, R. Shimony, and . Holt, Proposed Experiment to Test Local Hidden-Variable Theories, Physical Review Letters, vol.23, issue.15, pp.880-884, 1969.
DOI : 10.1103/PhysRevLett.23.880

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

W. Dam, Implausible consequences of superstrong nonlocality, Natural Computing, vol.12, issue.1, pp.9-12, 2013.

A. Das-sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai et al., Distributed verification and hardness of distributed approximation, Proceedings of the 43rd annual ACM symposium on Theory of computing, STOC '11, pp.363-372, 2011.
DOI : 10.1145/1993636.1993686

S. Vasil, G. Denchev, and . Pandurangan, Distributed quantum computing: a new frontier in distributed systems or science fiction? SIGACT News, pp.77-95, 2008.

B. Derbel, C. Gavoille, D. Peleg, and L. Viennot, On the locality of distributed sparse spanner construction, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, PODC '08, pp.273-282, 2008.
DOI : 10.1145/1400751.1400788
URL : https://hal.archives-ouvertes.fr/hal-00343001

D. Dolev, C. Dwork, and L. Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the ACM, vol.34, issue.1, pp.77-97, 1987.
DOI : 10.1145/7531.7533

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

F. Dupuis, N. Gisin, and A. Hasidim, André Allan Méthot, and Haran Pilpel. No nonlocal box is universal, Journal of Mathematical Physics, issue.8, p.48, 2007.

C. Dwork, N. Lynch, and L. Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM, vol.35, issue.2, pp.288-323, 1988.
DOI : 10.1145/42282.42283

A. Einstein, B. Podolsky, and N. Rosen, Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?, Physical Review, vol.47, issue.10, pp.47777-780, 1935.
DOI : 10.1103/PhysRev.47.777

M. Elkin, A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, PODC '07, pp.185-194, 2007.
DOI : 10.1145/1281100.1281128

M. Elkin and H. Klauck, Danupon Nanongkai, and Gopal Pandurangan. Can quantum communication speed up distributed computation?, 2012.

P. Fraigniaud, C. Gavoille, D. Ilcinkas, and A. Pelc, Distributed computing with advice: information sensitivity of graph coloring, Distributed Computing, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00339878

P. Fraigniaud, M. Göös, A. Korman, and J. Suomela, What can be decided locally without identifiers?, Proceedings of the 2013 ACM symposium on Principles of distributed computing, PODC '13, pp.157-165, 2013.
DOI : 10.1145/2484239.2484264
URL : https://hal.archives-ouvertes.fr/hal-00912527

P. Fraigniaud, . Magnúsm, A. Halldórsson, and . Korman, On the Impact of Identifiers on Local Decision, Principles of Distributed Systems, pp.224-238, 2012.
DOI : 10.1007/978-3-642-35476-2_16
URL : https://hal.archives-ouvertes.fr/hal-01241093

P. Fraigniaud, D. Ilcinkas, and A. Pelc, Communication algorithms with advice, Journal of Computer and System Sciences, vol.76, issue.3-4, pp.222-232, 2010.
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 and A. Pelc, Decidability Classes for Mobile Agents??Computing, Proceedings of the 10th Latin American International Conference on Theoretical Informatics, pp.362-374, 2012.
DOI : 10.1007/978-3-642-29344-3_31

P. Fraigniaud, S. Rajsbaum, and C. Travers, Locality and checkability in wait-free computing. Distributed Computing, pp.223-242, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00992781

S. Freedman and J. F. Clauser, Experimental Test of Local Hidden-Variable Theories, Physical Review Letters, vol.28, issue.14, pp.938-941, 1972.
DOI : 10.1103/PhysRevLett.28.938

C. Felix and . Gärtner, Fundamentals of fault-tolerant distributed computing in asynchronous environments, ACM Comput. Surv, vol.31, issue.1, pp.1-26, 1999.

C. Gavoille, R. Klasing, A. Kosowski, A. Kuszner, and . Navarra, On the complexity of distributed graph coloring with local minimality constraints, Networks, vol.9, issue.1, pp.12-19, 2009.
DOI : 10.1002/net.20293
URL : https://hal.archives-ouvertes.fr/hal-00342898

C. Gavoille, A. Kosowski, and M. Markiewicz, What can be observed locally? round-based models for quantum distributed computing, Proceedings of the 23rd international conference on Distributed computing, DISC '09, pp.243-257, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00408727

G. C. Ghirardi, A. Rimini, and T. Weber, A general argument against superluminal transmission through the quantum mechanical measurement process, Lettere al Nuovo Cimento, vol.123, issue.10, 1980.
DOI : 10.1007/BF02817189

O. Goldreich and D. Ron, Property testing in bounded degree graphs, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing , STOC '97, pp.406-415, 1997.
DOI : 10.1145/258533.258627

M. Göös and J. Suomela, Locally checkable proofs, Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing, pp.159-168, 2011.

W. Rabiner-heinzelman, A. Chandrakasan, and H. Balakrishnan, Energy-efficient communication protocol for wireless microsensor networks, Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, p.0, 2000.
DOI : 10.1109/HICSS.2000.926982

E. Ralph, F. B. Johnson, and . Schneider, Symmetry and similarity in distributed systems, Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, PODC '85, pp.13-22, 1985.

S. Katz and K. Perry, Self-stabilizing extensions for message-passing systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing , PODC '90, pp.91-101, 1990.
DOI : 10.1145/93385.93405

L. Kor, A. Korman, and D. Peleg, Tight bounds for distributed mst verification, STACS, pp.69-80, 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, Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp.311-320, 2011.
URL : https://hal.archives-ouvertes.fr/hal-01240211

A. Korman, S. Kutten, and D. Peleg, Proof labeling schemes, Distributed Computing, pp.215-233, 2010.
DOI : 10.1145/1073814.1073817

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, 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

F. Kuhn, T. Moscibroda, and R. Wattenhofer, Local Computation, Journal of the ACM, vol.63, issue.2, 2010.
DOI : 10.1145/2742012

F. Kuhn, T. Moscibroda, and R. Wattenhofer, What cannot be computed locally!, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing , PODC '04, pp.300-309, 2004.
DOI : 10.1145/1011767.1011811
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.5623

S. Lindsey, C. Raghavendra, and K. M. Sivalingam, Data gathering algorithms in sensor networks using energy metrics, IEEE Transactions on Parallel and Distributed Systems, vol.13, issue.9, pp.924-935, 2002.
DOI : 10.1109/TPDS.2002.1036066

N. Linial, Locality in Distributed Graph Algorithms, SIAM Journal on Computing, vol.21, issue.1, pp.193-201, 1992.
DOI : 10.1137/0221015

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

O. Kenneth and . May, A set of independent necessary and sufficient conditions for simple majority decision, Econometrica, vol.20, issue.4, pp.680-684, 1952.

R. Nicholas and . Miller, Graph-Theoretical Approaches to the Theory of Voting, American Journal of Political Science, vol.21, pp.769-803, 1977.

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
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.902

A. Panconesi, . Aravind, and . Srinivasan, The local nature of ?-coloring and its algorithmic applications, Combinatorica, vol.47, issue.1, pp.255-280, 1995.
DOI : 10.1007/BF01200759

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, Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, 2000.
DOI : 10.1137/1.9780898719772

S. Popescu and D. Rohrlich, Quantum nonlocality as an axiom, Foundations of Physics, vol.49, issue.3, pp.379-385, 1994.
DOI : 10.1007/BF02058098

J. Schneider and R. Wattenhofer, A new technique for distributed symmetry breaking, Proceeding of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing, PODC '10, pp.257-266, 2010.
DOI : 10.1145/1835698.1835760

J. Suomela, Survey of local algorithms, ACM Computing Surveys, vol.45, issue.2, pp.1-2440, 2013.
DOI : 10.1145/2431211.2431223

H. Hüseyin¨ozgür, T. , and I. Körpeo?körpeo?glu, Power efficient data gathering and aggregation in wireless sensor networks, SIGMOD Rec, vol.32, issue.4, pp.66-71, 2003.

J. Lundelius and W. , Simulating synchronous processors, Information and Computation, vol.74, issue.2, pp.159-171, 1987.

N. Xiong, Y. Yang, M. Cao, J. He, and L. Shu, A survey on faulttolerance in distributed network systems, CSE '09. International Conference on, pp.1065-1070, 2009.