Robustness and emergence in complex systems : the model of cellular automata
Robustesse et émergence dans les systèmes complexes : le modèle des automates cellulaires
Résumé
The aim of this work is to better understand what happens when one perturbs a complex system, using the model of cellular automata. We focus mainly on two perturbations. The first one deals with how time is passing: as opposed to the usual model, we use asynchronous updates, i.e. at each time step, only some cells are updated. The second perturbations deals with the topology, i.e. the graph of interactions between cells.
The first part studies experimentally the apparition of directed percolation in cellular automata, in particular in the framework of damage spreading. The last chapter of this part proves an equivalence between a class of probabilistic cellular automata and asynchronous cellular automata.
The second part studies in a first chapter the interplay of both mentioned perturbations: asynchronism and topology. While the usual model is defined on a Zd grid, we study a grid where some links are temporarily broken. The a second chapter proves a few theoretical properties of the minority rule when the topology is a tree.
In this thesis, we conducted both experimental and theoretical studies. A transverse question is formal simulations between models. The aim of those works is, in the long term, to know how to get systems with a predefined global behavior, or how to make robust against some perturbations a given complex system.
The first part studies experimentally the apparition of directed percolation in cellular automata, in particular in the framework of damage spreading. The last chapter of this part proves an equivalence between a class of probabilistic cellular automata and asynchronous cellular automata.
The second part studies in a first chapter the interplay of both mentioned perturbations: asynchronism and topology. While the usual model is defined on a Zd grid, we study a grid where some links are temporarily broken. The a second chapter proves a few theoretical properties of the minority rule when the topology is a tree.
In this thesis, we conducted both experimental and theoretical studies. A transverse question is formal simulations between models. The aim of those works is, in the long term, to know how to get systems with a predefined global behavior, or how to make robust against some perturbations a given complex system.
L'objet de ce travail est de mieux comprendre ce qui se produit lorsque l'on perturbe un système complexe, en utilisant les automates cellulaires comme modèle. Nous nous intéressons principalement à deux perturbations. La première concerne l'écoulement du temps : contrairement au modèle habituel, nous utilisons des mises à jour asynchrones, c'est-à-dire que, à chaque étape, seulement une partie des cellules sont mises à jour. L'autre perturbation concerne la topologie, c'est-à-dire le graphe d'interaction entre les cellules.
Une première partie étudie expérimentalement l'apparition de la percolation dirigée dans les automates cellulaires, notamment dans le cadre du "damage spreading". Le dernier chapitre de cette partie prouve une équivalence entre une classe d'automates cellulaires probabilistes et les automates cellulaires asynchrones.
La seconde partie étudie dans un premier chapitre l'interaction des deux perturbations évoquées: asynchronisme et topologie. Alors que le modèle habituel utilise une grille Zd, nous étudions une grille où certains liens sont temporairement coupés. Puis un second chapitre démontre des propriétés théoriques sur la règles minorité lorsque la topologie est un arbre.
Nous avons dans cette thèse mené à la fois des études expérimentales et des études théoriques. Une préoccupation transversale est la simulation formelle entre modèles. L'enjeu de ces travaux est, à terme, de savoir comment obtenir des systèmes ayant un comportement global prédéfini, ou bien comment rendre robuste à certaines perturbations un système complexe donné.
Une première partie étudie expérimentalement l'apparition de la percolation dirigée dans les automates cellulaires, notamment dans le cadre du "damage spreading". Le dernier chapitre de cette partie prouve une équivalence entre une classe d'automates cellulaires probabilistes et les automates cellulaires asynchrones.
La seconde partie étudie dans un premier chapitre l'interaction des deux perturbations évoquées: asynchronisme et topologie. Alors que le modèle habituel utilise une grille Zd, nous étudions une grille où certains liens sont temporairement coupés. Puis un second chapitre démontre des propriétés théoriques sur la règles minorité lorsque la topologie est un arbre.
Nous avons dans cette thèse mené à la fois des études expérimentales et des études théoriques. Une préoccupation transversale est la simulation formelle entre modèles. L'enjeu de ces travaux est, à terme, de savoir comment obtenir des systèmes ayant un comportement global prédéfini, ou bien comment rendre robuste à certaines perturbations un système complexe donné.
Mots clés
cellular automata
complex systems
robustness
coupling
probabilistic cellular automata
elementary cellular automata
asynchronous cellular automata
directed percolation
universality class
phase transition
minority
trees
hitting time
relaxing time
asynchronism
topology perturbation
discrete dynamical system
stochastic process
Markov chain
automates cellulaires
systèmes complexes
perturbation
robustesse
synchronisation
coalescence
couplage
simulation
équivalence
réduction
CA
automate cellulaire probabiliste
PCA
automate cellulaire élémentaire
ECA
automate cellulaire asynchrone
percolation dirigée
classe d'universalité
transition de phase
minorité
arbres
temps d'atteinte
temps transitoire
temps de relaxation
asynchronisme
perturbation de la topologie
systéme dynamique discret
processus stochastique
chaîne de Markov
Loading...