.. .. Contexte,

T. Dans-cette, Chaque processus d'un système distribué exécute un algorithme (local) (i.e., une séquence ordonnée d'instructions) d'une manière non coordonnée, i.e., sans l'aide d'aucune entité centrale. Un algorithme distribué est l'ensemble de tous les algorithmes locaux des entités d'un système distribué. Les systèmes distribués sont à opposer aux systèmes centralisés dans lesquels une seule entité a une vue globale du système et prend toutes les décisions. Dans les systèmes distribués, tous les processus prennent leurs propres décisions en fonction de leurs propres connaissances du système. Ils ont leur propre horloge et leur propre vitesse de calcul, nous étudions des systèmes composés de plusieurs processus capables de communiquer ensemble

, Il existe plusieurs hypothèses qui peuvent être faites sur un système distribué pour représenter tous ces divers systèmes réels : les entités sont-elles synchrones (leur vitesse de calcul est bornée) ou sontelles asynchrones (leur vitesse de calcul est finie mais non bornée) ? Les entités sont-elles capables de communiquer ? Comment communiquent-elles (grâce à une mémoire partagée ou à des envois de messages) ? Les entités sont-elles capables de communiquer de manière synchrone (le temps d'acheminement des messages est borné) ou asynchrone (le temps d'acheminement des messages est fini mais non borné)? Les entités peuvent-elles être sujettes à des fautes ? Est-ce que le graphe de communication des entités est représenté par un graphe statique ou par un graphe dynamique (où les arêtes modélisent la possibilité pour deux entités de communiquer, Même si leur conception peut être délicate à divers égards, en particulier la synchronisation des algorithmes locaux, les systèmes distribués présentent certains avantages

, Quand un environnement est trop dur, certains problèmes deviennent impossibles à résoudre ou les bornes inférieures (i.e., la performance minimale selon certaines métriques comme le temps utilisé, la mémoire utilisée, le nombre de messages envoyés, etc., nécessaire pour résoudre un problème) pour résoudre certains problèmes augmentent. Par exemple, le problème du consensus (où les processus doivent décider de manière irrévocable, en temps fini, la même valeur le temps car ils s'adapteront à ces changements sans aucune intervention externe en, Certains environnements sont plus difficiles que d'autres : par exemple un environnement composé d'entités asynchrones est plus difficile que le même environnement où les entités sont synchrones

E. Aaron, D. Krizanc, and E. Meyerson, DMVP: foremost waypoint coverage of timevarying graphs, International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp.29-41, 2014.

S. Abshoff, A. Cord-landwehr, M. Fischer, D. Jung, F. Meyer et al., Gathering a closed chain of robots on a grid, International Parallel and Distributed Processing Symposium (IPDPS), pp.689-699, 2016.

A. Agarwalla, J. Augustine, W. K. Moses, K. Madhav, and A. K. Sridhar, Deterministic dispersion of mobile robots in dynamic rings, International Conference on Distributed Computing and Networking (ICDCN), vol.19, pp.1-19, 2018.

C. Agathangelou, C. Georgiou, and M. Mavronicolas, A distributed algorithm for gathering many fat mobile robots in the plane, ACM Symposium on Principles of Distributed Computing (PODC), pp.250-259, 2013.

D. Alistarh, S. Gilbert, R. Guerraoui, and C. Travers, Generating fast indulgent algorithms. Theory of Computing Systems (Theor, Comput. Sci.), vol.51, issue.4, pp.404-424, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00992779

A. Aljohani and G. Sharma, Complete visibility for mobile robots with lights tolerating faults, International Journal of Networking and Computing (IJNC), vol.8, issue.1, pp.32-52, 2018.

H. Ando, Y. Oasa, I. Suzuki, and M. Yamashita, Distributed memoryless point convergence algorithm for mobile robots with limited visibility, IEEE Transactions on Robotics and Automation (IEEE Trans. Robotics and Automation), vol.15, issue.5, pp.818-828, 1999.

H. Attiya and J. Welch, Fundamentals, Simulations and Advances Topics

J. Wiley-interscience, , 2004.

P. Aublin, R. Guerraoui, N. Knezevic, V. Quéma, and M. Vukolic, The next 700 BFT protocols, ACM Transactions on Computer Systems (ACM Trans. Comput. Syst.), vol.32, issue.4, 2015.

J. Augustine and W. K. Moses, Dispersion of mobile robots: A study of memorytime trade-offs, International Conference on Distributed Computing and Networking (ICDCN), vol.1, pp.1-1, 2018.

C. Avin, M. Koucký, and Z. Lotker, Cover time and mixing time of random walks on dynamic graphs. Random Structures and Algorithms, vol.52, pp.576-596, 2018.

R. Baldoni, F. Bonnet, A. Milani, and M. Raynal, On the solvability of anonymous partial grids exploration by mobile robots, International Conference on Principles of Distributed Systems (OPODIS), pp.428-445, 2008.
URL : https://hal.archives-ouvertes.fr/inria-00277344

E. Bampas, J. Czyzowicz, L. Gasieniec, D. Ilcinkas, and A. Labourel, Almost optimal asynchronous rendezvous in infinite multidimensional grids, International Symposium on Distributed Computing (DISC), pp.297-311, 2010.
URL : https://hal.archives-ouvertes.fr/hal-00534263

L. Barrière, P. Flocchini, E. Mesa, N. Barrameda, and . Santoro, Uniform scattering of autonomous mobile robots in a grid, International Journal of Foundations of Computer Science (Int. J. Found. Comput. Sci.), vol.22, issue.3, pp.679-697, 2011.

L. Barrière, P. Flocchini, P. Fraigniaud, and N. Santoro, Rendezvous and election of mobile agents: Impact of sense of direction, Theory of Computing Systems (Theory Comput. Syst.), vol.40, pp.143-162, 2007.

S. Beamer, A. Buluç, K. Asanovic, and D. A. Patterson, Distributed memory breadthfirst search revisited: Enabling bottom-up search, IEEE International Symposium on Parallel and Distributed Processing, Workshops and Phd Forum, pp.1618-1627, 2013.

M. A. Bender and D. K. Slonim, The power of team exploration: Two robots can learn unlabeled directed graphs, Symposium on Foundations of Computer Science (FOCS), pp.75-85, 1994.

K. A. Berman, Vulnerability of scheduled networks and a generalization of menger's theorem, vol.28, pp.125-134, 1996.

S. Bhagat, S. Gan-chaudhuri, and K. Mukhopadhyaya, Fault-tolerant gathering of asynchronous oblivious mobile robots under one-axis agreement, Journal of Discrete Algorithms (J. Discrete Algorithms), vol.36, pp.50-62, 2016.

M. Biely, P. Robinson, U. Schmid, M. Schwarz, and K. Winkler, Gracefully degrading consensus and k-set agreement in directed dynamic networks, Theoretical Computer Science (Theor. Comput. Sci.), vol.726, pp.41-77, 2018.

L. Blin, A. Milani, M. Potop-butucaru, and S. Tixeuil, Exclusive perpetual ring exploration without chirality, International Symposium on Distributed Computing (DISC), pp.312-327, 2010.
URL : https://hal.archives-ouvertes.fr/inria-00464206

S. Bouchard, M. Bournat, Y. Dieudonné, S. Dubois, and F. Petit, Asynchronous approach in the plane: A deterministic polynomial algorithm, International Symposium on Distributed Computing (DISC), vol.8, pp.1-8, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01672916

S. Bouchard, M. Bournat, Y. Dieudonné, S. Dubois, and F. Petit, Approche asynchrone dans le plan : un algorithme déterministe polynomial, rencontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL), 2018.

S. Bouchard, M. Bournat, Y. Dieudonné, S. Dubois, and F. Petit, Asynchronous approach in the plane: A deterministic polynomial algorithm
URL : https://hal.archives-ouvertes.fr/hal-01672916

S. Bouchard, Y. Dieudonné, and B. Ducourthial, Byzantine gathering in networks, Distributed Computing, vol.29, issue.6, pp.435-457, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01330420

S. Bouchard, Y. Dieudonné, and A. Lamani, Byzantine gathering in polynomial time, International Colloquium on Automata, Languages, and Programming (ICALP), vol.147, pp.1-147, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01965743

M. Bournat, A. K. Datta, and S. Dubois, Self-stabilizing robots in highly dynamic environments, International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp.54-69, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01416308

M. Bournat, A. K. Datta, and S. Dubois, Self-stabilizing robots in highly dynamic environments, Theoretical Computer Science (Theor. Comput. Sci.)
URL : https://hal.archives-ouvertes.fr/hal-01416308

M. Bournat, S. Dubois, and F. Petit, Computability of perpetual exploration in highly dynamic rings, IEEE International Conference on Distributed Computing Systems (ICDCS), pp.794-804, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01417565

M. Bournat, S. Dubois, and F. Petit, Quel est le nombre optimal de robots pour explorer un anneau hautement dynamique ?, rencontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL), 2017.
URL : https://hal.archives-ouvertes.fr/hal-01516182

M. Bournat, S. Dubois, and F. Petit, Gracefully degrading gathering in dynamic rings, International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2018.
URL : https://hal.archives-ouvertes.fr/hal-01790554

Z. Bouzid and A. Lamani, Robot networks with homonyms: The case of patterns formation, International Symposium on Stabilization, Safety, and Security of Distributed Systems, pp.92-107, 2011.
URL : https://hal.archives-ouvertes.fr/hal-01009455

Z. Bouzid, M. Potop-butucaru, and S. Tixeuil, Byzantine convergence in robot networks: The price of asynchrony, International Conference on Principles of Distributed Systems (OPODIS), pp.54-70, 2009.

N. Braud-santoni, S. Dubois, M. Kaaouachi, and F. Petit, The next 700 impossibility results in time-varying graphs, International Journal of Networking and Computing (IJNC), vol.6, issue.1, pp.27-41, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01344422

D. Canepa, X. Défago, T. Izumi, and M. Potop-butucaru, Flocking with oblivious robots, International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp.94-108, 2016.

D. Canepa and M. Gradinariu-potop-butucaru, Stabilizing flocking via leader election in robot networks, International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp.52-66, 2007.
URL : https://hal.archives-ouvertes.fr/inria-00166630

R. Carli and F. Bullo, Quantized coordination algorithms for rendezvous and deployment, SIAM Journal on Control and Optimization (SIAM J. Control and Optimization), vol.48, issue.3, pp.1251-1274, 2009.

A. Casteigts, Finding structure in dynamic networks, 2018.

A. Casteigts, P. Flocchini, B. Mans, and N. Santoro, Shortest, fastest, and foremost broadcast in dynamic networks, International Journal of Foundations of Computer Science (Int. J. Found. Comput. Sci.), vol.26, issue.4, pp.499-522, 2015.

A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro, Time-varying graphs and dynamic networks, Emergent and Distributed Systems (IJPEDS), vol.27, pp.387-408, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00847001

J. Chalopin, Y. Dieudonné, A. Labourel, and A. Pelc, Rendezvous in networks in spite of delay faults, Distributed Computing, vol.29, issue.3, pp.187-205, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01330426

J. Chalopin, P. Flocchini, B. Mans, and N. Santoro, Network exploration by silent and oblivious robots, Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp.208-219, 2010.
URL : https://hal.archives-ouvertes.fr/hal-01198880

M. Cieliebak, P. Flocchini, G. Prencipe, and N. Santoro, Solving the robots gathering problem, International Colloquium on Automata, Languages and Programming (ICALP), pp.1181-1196, 2003.

J. Clément, X. Défago, M. Potop-butucaru, T. Izumi, and S. Messika, The cost of probabilistic agreement in oblivious robot networks, Information Processing Letters (Inf. Process. Lett.), vol.110, issue.11, pp.431-438, 2010.

R. Cohen and D. Peleg, Local spreading algorithms for autonomous robot systems, Theoretical Computer Science (Theor. Comput. Sci.), vol.399, issue.1-2, pp.71-82, 2008.

A. Collins, J. Czyzowicz, L. Gasieniec, A. Kosowski, and R. A. Martin, Synchronous rendezvous for location-aware agents, International Symposium on Distributed Computing (DISC), pp.447-459, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00646907

A. Collins, J. Czyzowicz, L. Gasieniec, and A. Labourel, Tell me where I am so I can meet you sooner, International Colloquium on Automata, Languages and Programming (ICALP), pp.502-514, 2010.
URL : https://hal.archives-ouvertes.fr/hal-00866392

A. Cord-landwehr, B. Degener, M. Fischer, M. Hüllmann, B. Kempkes et al., Collisionless gathering of robots with an extent, Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), pp.178-189, 2011.

A. Cord-landwehr, M. Fischer, D. Jung, F. Meyer, and H. Der, Asymptotically optimal gathering on a grid, ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp.301-312, 2016.

J. Czyzowicz, L. Gasieniec, and A. Pelc, Gathering few fat mobile robots in the plane, Theoretical Computer Science (Theor. Comput. Sci.), pp.481-499, 2009.

J. Czyzowicz, A. Pelc, and A. Labourel, How to meet asynchronously (almost) everywhere, ACM Transactions on Algorithms (ACM Trans. Algorithms), vol.8, issue.4, p.37, 2012.
URL : https://hal.archives-ouvertes.fr/hal-01480380

S. Das, P. Flocchini, G. Prencipe, N. Santoro, and M. Yamashita, Autonomous mobile robots with lights, Theor. Comput. Sci, vol.609, pp.171-184, 2016.
URL : https://hal.archives-ouvertes.fr/hal-02082178

S. Das, R. Focardi, F. L. Luccio, E. Markou, D. Moro et al., Gathering of robots in a ring with mobile faults, Italian Conference on Theoretical Computer Science (ICTCS), pp.122-135, 2016.
URL : https://hal.archives-ouvertes.fr/hal-02082148

S. Das, F. L. Luccio, and E. Markou, Mobile agents rendezvous in spite of a malicious agent, International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS), pp.211-224, 2015.

A. K. Datta, A. Lamani, L. Larmore, and F. Petit, Ring exploration by oblivious agents with local vision, IEEE International Conference on Distributed Computing Systems (ICDCS), pp.347-356, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00933909

S. Datta, A. Dutta, S. Gan-chaudhuri, and K. Mukhopadhyaya, Circle formation by asynchronous transparent fat robots, International Conference on Distributed Computing and Internet Technology (ICDCIT), pp.195-207, 2013.

X. Défago, M. Gradinariu, S. Messika, and P. R. Parvédy, Fault-tolerant and selfstabilizing mobile robots gathering, International Symposium on Distributed Computing (DISC), pp.46-60, 2006.

X. Défago and A. Konagaya, Circle formation for oblivious anonymous mobile robots with no common sense of orientation, Workshop on Principles of Mobile Computing (POMC), pp.97-104, 2002.

X. Défago and S. Souissi, Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity, Theoretical Computer Science (Theor. Comput. Sci.), vol.396, issue.1-3, pp.97-112, 2008.

C. Delporte-gallet, H. Fauconnier, and H. Tran-the, Uniform consensus with homonyms and omission failures, International Conference on Distributed Computing and Networking (ICDCN), pp.161-175, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00922428

D. Dereniowski and A. Pelc, Leader election for anonymous asynchronous agents in arbitrary networks, Distributed Computing, vol.27, issue.1, pp.21-38, 2014.

A. Dessmark, P. Fraigniaud, D. R. Kowalski, and A. Pelc, Deterministic rendezvous in graphs, Algorithmica, vol.46, issue.1, pp.69-96, 2006.

S. Devismes, A. Lamani, F. Petit, P. Raymond, and S. Tixeuil, Optimal grid exploration by asynchronous oblivious robots, International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp.64-76, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00934161

S. Devismes, A. Lamani, F. Petit, and S. Tixeuil, Optimal torus exploration by oblivious robots, Third International Conference on Networked Systems (NETYS), vol.9466, pp.183-199, 2015.
URL : https://hal.archives-ouvertes.fr/hal-00926573

S. Devismes, F. Petit, and S. Tixeuil, Optimal probabilistic ring exploration by semisynchronous oblivious robots, Theoretical Computer Science (Theor. Comput. Sci.), vol.498, pp.10-27, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00930045

Y. Dieudonné, S. Dolev, F. Petit, and M. Segal, Deaf, dumb, and chatting robots, enabling distributed computation and fault-tolerance among stigmergic robot, 2009.

Y. Dieudonné and A. Pelc, Deterministic polynomial approach in the plane, Distributed Computing, vol.28, issue.2, pp.111-129, 2015.

Y. Dieudonné, A. Pelc, and D. Peleg, Gathering despite mischief, ACM Trans. Algorithms, vol.11, issue.1, 2014.

Y. Dieudonné, A. Pelc, and V. Villain, How to meet asynchronously at polynomial cost, SIAM Journal on Computing (SIAM J. Comput.), vol.44, issue.3, pp.844-867, 2015.

Y. Dieudonné and F. Petit, Scatter of robots, Parallel Processing Letters, vol.19, issue.1, pp.175-184, 2009.

Y. Dieudonné and F. Petit, Self-stabilizing gathering with strong multiplicity detection, Theoretical Computer Science (Theor. Comput. Sci.), vol.428, pp.47-57, 2012.

Y. Dieudonné, F. Petit, and V. Villain, Leader election problem versus pattern formation problem, International Symposium on Distributed Computing (DISC), pp.267-281, 2010.

E. Dijkstra, Self-stabilizing systems in spite of distributed control, Communication of the ACM (Commun. ACM), vol.17, issue.11, pp.643-644, 1974.

K. Diks, P. Fraigniaud, E. Kranakis, and A. Pelc, Tree exploration with little memory, Journal of Algorithms (J. Algorithms), vol.51, issue.1, pp.38-63, 2004.

S. Dobrev, N. Santoro, and W. Shi, Scattered black hole search in an oriented ring using tokens, International Parallel and Distributed Processing Symposium (IPDPS), pp.1-8, 2007.

S. Dolev, Self-stabilization, 2000.
URL : https://hal.archives-ouvertes.fr/inria-00627780

S. Dubois and R. Guerraoui, Introducing speculation in self-stabilization: an application to mutual exclusion, ACM Symposium on Principles of Distributed Computing (PODC), pp.290-298, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00786398

S. Dubois, M. Kaaouachi, and F. Petit, Enabling minimal dominating set in highly dynamic distributed systems, International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp.51-66, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01111610

T. Erlebach, M. Hoffmann, and F. Kammer, On temporal graph exploration, International Colloquium on Automata, Languages, and Programming (ICALP), pp.444-455, 2015.

A. Ferreira, On models and algorithms for dynamic communication networks: The case for evolving graphs, rencontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL), 2002.

M. Fischer, D. Jung, F. Meyer, and H. Der, Gathering anonymous, oblivious robots on a grid, International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS), pp.168-181, 2017.

M. J. Fischer, N. A. Lynch, and M. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (J. ACM), vol.32, issue.2, pp.374-382, 1985.

P. Flocchini, D. Ilcinkas, A. Pelc, and N. Santoro, Computing without communicating: Ring exploration by asynchronous oblivious robots, International Conference on Principles of Distributed Systems (OPODIS), pp.105-118, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00912499

P. Flocchini, D. Ilcinkas, A. Pelc, and N. Santoro, Remembering without memory: Tree exploration by asynchronous oblivious robots, Theoretical Computer Science (Theor. Comput. Sci.), pp.1583-1598, 2010.
URL : https://hal.archives-ouvertes.fr/hal-00464588

P. Flocchini, D. Ilcinkas, A. Pelc, and N. Santoro, How many oblivious robots can explore a line, Information Processing Letters (Inf. Process. Lett, issue.20, pp.1027-1031, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00643668

P. Flocchini, M. Kellett, P. C. Mason, and N. Santoro, Fault-tolerant exploration of an unknown dangerous graph by scattered agents, International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp.299-313, 2012.

P. Flocchini, M. Kellett, P. C. Mason, and N. Santoro, Finding good coffee in paris, International Conference on Fun with Algorithms (FUN), pp.154-165, 2012.

P. Flocchini, M. Kellett, P. C. Mason, and N. Santoro, Searching for black holes in subways, Theory of Computing Systems (Theory Comput. Syst.), vol.50, pp.158-184, 2012.

P. Flocchini, B. Mans, and N. Santoro, Exploration of periodically varying graphs, International Symposium on Algorithms and Computation (ISAAC), pp.534-543, 2009.

P. Flocchini, B. Mans, and N. Santoro, On the exploration of time-varying networks. Theoretical Computer Science (Theor, Comput. Sci.), vol.469, pp.53-68, 2013.

P. Flocchini, G. Prencipe, N. Santoro, and G. Viglietta, Distributed computing by mobile robots: uniform circle formation. Distributed Computing, vol.30, pp.413-457, 2017.

P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer, Hard tasks for weak robots: The role of common knowledge in pattern formation by autonomous mobile robots, International Symposium on Algorithms and Computation (ISAAC), pp.93-102, 1999.

P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer, Gathering of asynchronous robots with limited visibility, Theoretical Computer Science (Theor. Comput. Sci.), vol.337, issue.1-3, pp.147-168, 2005.

P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer, Arbitrary pattern formation by asynchronous, anonymous, oblivious robots, Theoretical Computer Science (Theor. Comput. Sci.), vol.407, issue.1-3, pp.412-447, 2008.

P. Flocchini, N. Santoro, G. Viglietta, and M. Yamashita, Rendezvous of two robots with constant memory, International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp.189-200, 2013.

K. Foerster and R. Wattenhofer, Lower and upper competitive bounds for online directed graph exploration, Theoretical Computer Science (Theor. Comput. Sci.), vol.655, pp.15-29, 2016.

P. Fraigniaud and D. Ilcinkas, Digraphs exploration with little memory, Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp.246-257, 2004.
URL : https://hal.archives-ouvertes.fr/hal-00339719

P. Fraigniaud, D. Ilcinkas, G. Peer, A. Pelc, and D. Peleg, Graph exploration by a finite automaton, Theoretical Computer Science (Theor. Comput. Sci.), vol.345, issue.2-3, pp.331-344, 2005.
URL : https://hal.archives-ouvertes.fr/hal-00339763

T. Gotoh, Y. Sudo, F. Ooshita, H. Kakugawa, and T. Masuzawa, Group exploration of dynamic tori, IEEE International Conference on Distributed Computing Systems (ICDCS), pp.775-785, 2018.

S. Guilbault and A. Pelc, Gathering asynchronous oblivious agents with local vision in regular bipartite graphs, Theoretical Computer Science (Theor. Comput. Sci.), vol.509, pp.86-96, 2013.

F. Harary and G. Gupta, Dynamic graph models, Mathematical and Computer Modelling, vol.25, issue.7, pp.79-87, 1997.

A. Heriban, X. Défago, and S. Tixeuil, Optimally gathering two robots, International Conference on Distributed Computing and Networking (ICDCN), vol.3, pp.1-3, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01575451

S. Huang and N. Chen, A self-stabilizing algorithm for constructing breadth-first trees, Information Processing Letters (Inf. Process. Lett.), vol.41, issue.2, pp.109-117, 1992.

D. Ilcinkas, R. Klasing, and A. M. Wade, Exploration of constantly connected dynamic graphs based on cactuses, International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp.250-262, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01068904

D. Ilcinkas and A. M. Wade, On the power of waiting when exploring public transportation systems, International Conference on Principles of Distributed Systems (OPODIS), pp.451-464, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00656607

D. Ilcinkas and A. M. Wade, Exploration of the T-interval-connected dynamic graphs: The case of the ring, International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp.13-23, 2013.
URL : https://hal.archives-ouvertes.fr/hal-01899735

T. Izumi, Z. Bouzid, S. Tixeuil, and K. Wada, Brief announcement: The bg-simulation for byzantine mobile robots, International Symposium on Distributed Computing (DISC), pp.330-331, 2011.
URL : https://hal.archives-ouvertes.fr/hal-01285672

T. Izumi, D. Kaino, M. Potop-butucaru, and S. Tixeuil, On time complexity for connectivity-preserving scattering of mobile robots, Theoretical Computer Science (Theor. Comput. Sci.), vol.738, pp.42-52, 2018.
URL : https://hal.archives-ouvertes.fr/hal-02076455

T. Izumi, S. Souissi, Y. Katayama, N. Inuzuka, X. Défago et al., The gathering problem for two oblivious robots with unreliable compasses, SIAM Journal on Computing (SIAM J. Comput.), vol.41, issue.1, pp.26-46, 2012.

T. Izumi, Y. Yamauchi, and S. Kamei, Brief announcement: Mobile agent rendezvous on edge evolving rings, International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp.92-94, 2012.

B. Katreniak, Convergence with limited visibility by asynchronous mobile robots, International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp.125-137, 2011.

D. Kempe, J. M. Kleinberg, and A. Kumar, Connectivity and inference problems for temporal networks, Journal of Computer and System Sciences (JCSS), vol.64, issue.4, pp.820-842, 2002.

R. Klasing, E. Markou, and A. Pelc, Gathering asynchronous oblivious mobile robots in a ring, International Symposium on Algorithms and Computation (ISAAC), pp.744-753, 2006.
URL : https://hal.archives-ouvertes.fr/hal-00307237

R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. L. Wong, Zyzzyva: Speculative byzantine fault tolerance, ACM Transactions on Computer Systems (ACM Trans. Comput. Syst.), vol.27, issue.4, 2009.

D. R. Kowalski and A. Malinowski, How to meet in anonymous network, Theoretical Computer Science (Theor. Comput. Sci.), vol.399, issue.1-2, pp.141-156, 2008.

F. Kuhn, N. A. Lynch, and R. Oshman, Distributed computation in dynamic networks, Symposium on the Theory of Computing (STOC), pp.513-522, 2010.

L. Lamport, Proving the correctness of multiprocess programs, IEEE Transactions on Software Engineering (TSE), vol.3, issue.2, pp.125-143, 1977.

L. Lamport, The part-time parliament, ACM Transactions on Computer Systems (TOCS), vol.16, issue.2, pp.133-169, 1998.

L. Lamport, R. E. Shostak, and M. C. Pease, The byzantine generals problem, ACM Transactions on Programming Languages and Systems (ACM Trans. Program. Lang. Syst.), vol.4, issue.3, pp.382-401, 1982.

M. Latapy, T. Viard, and C. Magnien, Stream graphs and link streams for the modeling of interactions over time, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01665084

X. Li, M. F. Ercan, and Y. Fung, Decentralized control for swarm flocking in 3d space, International Conference on Intelligent Robotics and Applications (ICIRA), pp.744-754, 2009.

G. A. Di-luna, P. Flocchini, L. Pagli, G. Prencipe, N. Santoro et al., Gathering in dynamic rings, International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp.339-355, 2017.

G. A. Di-luna, P. Flocchini, N. Santoro, and G. Viglietta, Turingmobile: A turing machine of oblivious mobile robots with limited visibility and its applications, International Symposium on Distributed Computing (DISC), 2018.

G. Luna, P. Flocchini, N. Santoro, G. Viglietta, and M. Yamashita, Meeting in a polygon by anonymous oblivious robots, International Symposium on Distributed Computing (DISC), vol.14, p.15, 2017.

G. D. Luna, S. Dobrev, P. Flocchini, and N. Santoro, Live exploration of dynamic rings, IEEE International Conference on Distributed Computing Systems (ICDCS), pp.570-579, 2016.

O. Michail and P. G. Spirakis, Traveling salesman problems in temporal graphs, Theoretical Computer Science (Theor. Comput. Sci.), vol.634, pp.1-23, 2016.

R. O'dell and R. Wattenhofer, Information dissemination in highly dynamic graphs, DIALM-POMC Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), pp.104-110, 2005.

F. Ooshita and A. K. Datta, Feasibility of weak gathering in connected-over-time dynamic rings, International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2018.

F. Ooshita and S. Tixeuil, On the self-stabilization of mobile oblivious robots in uniform rings, Theoretical Computer Science (Theor. Comput. Sci.), vol.568, pp.84-96, 2015.
URL : https://hal.archives-ouvertes.fr/hal-00934149

D. Peleg, Distributed coordination algorithms for mobile robot swarms: New directions and challenges, International Workshop on Distributed Computing (IWDC), pp.1-12, 2005.

R. De-prisco, B. W. Lampson, and N. A. Lynch, Revisiting the PAXOS algorithm, Theoretical Computer Science (Theor. Comput. Sci.), vol.243, issue.1-2, pp.35-91, 2000.

C. Shannon, Presentation of a maze-solving machine, Conference of the Josiah Macy, Jr. Foundation, pp.173-180, 1951.

M. Shibata, T. Mega, F. Ooshita, H. Kakugawa, and T. Masuzawa, Uniform deployment of mobile agents in asynchronous rings, Journal of Parallel and Distributed Computing, vol.119, pp.92-106, 2018.

S. Souissi, X. Défago, and M. Yamashita, Using eventually consistent compasses to gather memory-less mobile robots with limited visibility, ACM Transactions on Autonomous and Adaptive Systems (TAAS), vol.4, issue.1, p.27, 2009.

G. , D. Stefano, and A. Navarra, Optimal gathering of oblivious robots in anonymous graphs and its application on trees and rings. Distributed Computing, vol.30, pp.75-86, 2017.

I. Suzuki and M. Yamashita, Distributed anonymous mobile robots, International Colloquium on Structural Information & Communication Complexity (SIROCCO), pp.313-330, 1996.

I. Suzuki and M. Yamashita, Distributed anonymous mobile robots: Formation of geometric patterns, SIAM Journal on Computing (SIAM J. Comput.), vol.28, issue.4, pp.1347-1363, 1999.

S. , Algorithms and Theory of Computation Handbook, chapter Self-stabilizing Algorithms, vol.45, pp.26-27, 2009.

T. Uehara, Y. Yamauchi, S. Kijima, and M. Yamashita, Plane formation by semisynchronous robots in the three dimensional euclidean space, International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp.383-398, 2016.

N. H. Vaidya and D. K. Pradhan, Degradable agreement in the presence of byzantine faults, International Conference on Distributed Computing Systems (ICDCS), pp.237-244, 1993.

N. Xiong, J. He, Y. Yang, Y. He, T. Kim et al., A survey on decentralized flocking schemes for a set of autonomous mobile robots (invited paper), Journal of Communications (JCM), vol.5, issue.1, pp.31-38, 2010.

Y. Yamauchi, T. Izumi, and S. Kamei, Mobile agent rendezvous on a probabilistic edge evolving ring, International Conference on Networking and Computing (ICNC), pp.103-112, 2012.

Y. Yamauchi, T. Uehara, S. Kijima, and M. Yamashita, Plane formation by synchronous mobile robots in the three-dimensional euclidean space, Journal of the ACM (J. ACM), vol.64, issue.3, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01206131