Comment corriger des erreurs dans un réseau, en l’absence d’autorité centrale permettant de contrôler l’ensemble du fonctionnement ? Cet article présente des travaux de recherche récents motivés par cette question de nature informatique. Pour y répondre, l’outil et les méthodes mathématiques s’avèrent essentiels, à la fois dans les étapes de modélisation et de résolution. L’informatique mathématique, est ainsi un domaine de l’informatique qui utilise non seulement des mathématiques, mais se révèle aussi créateur de nouvelles mathématiques.

Automates cellulaires

Considérons un ruban infini, divisé en cases régulières que l’on appelle des cellules, et colorions chacune de ces cellules à l’aide d’une palette composée d’un nombre fini de couleurs. On dit qu’un tel coloriage du ruban est une configuration de dimension $1$. Si on colorie une grille infinie, on obtient aussi une configuration, de dimension $2$ cette fois.

Voici ci-dessous une portion finie d’une configuration en dimension $1$, avec deux couleurs : blanc et bleu.

Dans les composants informatiques et électroniques, l’information est encodée de cette manière : une image numérique est ainsi constituée d’un ensemble de cellules disposées sur une grille, auxquelles sont attribuées des couleurs, parmi un ensemble fini de couleurs possibles.

Donnons-nous une configuration, et supposons qu’une cellule décide de changer de couleur, en observant les couleurs de ses voisines et en choisissant une nouvelle couleur en fonction de cette observation. Si toutes les cellules appliquent simultanément la même règle de changement de couleur, cette étape de mise à jour est précisément ce qu’on appelle un automate cellulaire. Cette notion prend sa source dans les travaux de Stanislaw Ulam et de John von Neumann dans les années 40. Les automates cellulaires ont ensuite été popularisés par John Conway, qui a introduit dans les années 70 un automate cellulaire particulier appelé le « jeu de la vie » au comportement fascinant [1], puis par Stephen Wolfram à partir des années 80.

On peut représenter l’évolution d’un automate cellulaire de dimension $1$ par un diagramme espace-temps : on représente la configuration initiale en bas d’une figure, puis on écrit successivement de bas en haut les configurations observées au cours du temps.

Voici par exemple un diagramme espace-temps obtenu pour l’automate cellulaire défini de la manière suivante : une cellule est coloriée en bleu au temps $t+1$ si au temps $t$, parmi les deux cellules voisines immédiates, à sa gauche et à sa droite, il y a exactement une cellule bleue. Dans la figure ci-dessous, la configuration initiale est constituée d’un ruban blanc avec une seule cellule bleue.

On remarque que le diagramme espace-temps présente alors une structure auto-similaire : si on fait un zoom arrière, on observe encore globalement les mêmes motifs en triangles.

L’application ci-dessous permet également de tracer les diagrammes espace-temps obtenus pour des configurations initiales constituées de plusieurs cellules bleues.

Le succès des automates cellulaires provient du contraste saisissant entre la simplicité de leur définition et la grande complexité des évolutions qu’ils engendrent [2].

Les automates cellulaires sont ainsi utilisés pour modéliser des systèmes complexes, constitués d’un grand nombre d’entités qui évoluent au cours du temps, et dont le comportement ne dépend que de ce qu’elles peuvent observer localement autour d’elles. Les exemples sont nombreux : trafic routier, réseaux informatiques, formation d’essaims d’oiseaux, occupation de nids d’abeille, tissus cellulaires...

Du côté informatique, les automates cellulaires peuvent également être vus comme un modèle abstrait représentant le fonctionnement des ordinateurs (précisément, ils constituent un modèle de calcul ayant la puissance des machines de Turing).

Les mathématiciens s’intéressent également aux automates cellulaires car on peut
les caractériser comme les dynamiques définies sur les configurations et respectant des propriétés d’homogénéité et de localité [3].

Ici, nous allons nous intéresser à des automates cellulaires à deux couleurs (bleu et blanc) définis de la manière suivante : chaque cellule regarde les couleurs des cellules de son voisinage, et choisit comme nouvelle couleur la couleur majoritaire. On peut ainsi penser à un processus de vote : chaque individu sur le territoire possède une certaine couleur politique, qui peut changer au cours du temps sous l’influence de ses voisins. Pour bien définir l’automate cellulaire, il faut alors préciser ce que l’on entend par voisinage. En dimension $2$, les choix les plus fréquents sont les suivants :

• le voisinage de von Neumann d’une cellule est constitué d’elle-même et de ses quatre plus proches voisines sur la grille (à gauche, au-dessus, à droite, et en dessous),
• le voisinage de Moore d’une cellule est constitué d’elle-même et des huit cellules qui l’entourent,
• le voisinage de Toom d’une cellule est constitué d’elle-même, de sa voisine du dessus et de sa voisine de droite (contrairement aux deux autres, il s’agit donc d’un voisinage asymétrique).

Sur la figure ci-dessous, les cellules rouges correspondent au voisinage de la cellule marquée d’un point noir. Notons que ces voisinages empêchent tout cas d’égalité lors du vote, puisqu’il y a un nombre impair de cellules.

Voisinage de von Neumann	Voisinage de Moore	Voisinage de Toom

Erosion : corriger un nombre fini d’anomalies

On dit qu’un automate cellulaire a la propriété d’érosion si, à partir de n’importe quelle configuration ne contenant qu’un nombre fini de cellules bleues, son évolution est telle qu’au bout d’un certain temps, il n’y a plus aucune cellule bleue, et si, à partir de n’importe quelle configuration ne contenant qu’un nombre fini de cellules blanches, l’évolution est telle qu’au bout d’un certain temps, il n’y a plus aucune cellule blanche.

On peut voir la propriété d’érosion comme la capacité à effacer des « anomalies » qui apparaîtraient en nombre fini sur une configuration toute blanche ou toute bleue.

L’automate cellulaire de la majorité sur le voisinage de von Neumann ne possède pas la propriété d’érosion. En effet, si la configuration initiale est constituée de quatre cellules bleues disposées en carré, avec uniquement des cellules blanches autour, cette configuration va rester inchangée au cours du temps.

L’automate cellulaire de la majorité sur le voisinage de Moore ne possède pas non plus de propriété d’érosion, comme le montre la configuration représentée à droite dans la figure ci-dessous, dont on vérifie qu’elle est stable au cours du temps.

Motifs stables pour les voisinages de Von Neumann (à gauche) et de Moore (à droite)

Mais les obstructions de ce type n’existent pas pour l’automate cellulaire de la majorité sur le voisinage de Toom...

L’application ci-dessous permet d’observer l’évolution de l’automate cellulaire de Toom à partir d’autres configurations initiales ne comportant qu’un nombre fini de cellules bleues.

En dimension $1$, il existe aussi des automates cellulaires qui possèdent la propriété d’érosion. Les exemples sont un peu plus compliqués. Un des plus simples est l’automate cellulaire GKL, proposé en 1978 par Gacs, Kurdyumov, et Levin. Il est défini de la manière suivante.

• Si une cellule (repérée par l’indice $n$ sur le ruban) est blanche, elle prend comme nouvelle couleur celle qui est majoritaire parmi sa propre couleur, celle de sa voisine de gauche (cellule d’indice $n-1$), et celle de la cellule située trois places plus à gauche (cellule d’indice $n-3$).

• Au contraire, si une cellule (d’indice $n$) est bleue, elle prend comme nouvelle couleur celle qui est majoritaire parmi sa propre couleur, celle de sa voisine de droite (cellule d’indice $n+1$), et celle de la cellule située trois places plus à droite (cellule d’indice $n+3$).

Il est instructif de regarder opérer l’automate cellulaire GKL partant d’une configuration avec un intervalle fini de cellules bleues sur un ruban blanc, comme représenté ci-dessous.

L’application ci-dessous permet également de tracer les diagrammes obtenus pour d’autres configurations initiales.

Classification de la densité : corriger un bruit aléatoire

Nous avons vu que certains automates cellulaires avaient la propriété de nettoyer les configurations où toutes les cellules sont de la même couleur, sauf un nombre fini de cellules coloriées de la « mauvaise » couleur. Si on part maintenant d’une configuration comportant une certaine fraction de cellules (choisies aléatoirement) coloriées de la mauvaise couleur, est-il toujours possible de nettoyer la configuration à l’aide d’un automate cellulaire ?

Plus précisément, on considère un ruban infini ou une grille infinie, avec une configuration initiale obtenue en coloriant chaque cellule en bleu avec probabilité $p$ ou en blanc avec probabilité $1-p$ (en faisant des tirages indépendants pour les différentes cellules). Nous nous sommes demandé s’il était possible d’avoir la propriété suivante :

• si $p<1/2$, quand on itère l’automate cellulaire, la proportion de carrés bleus tend vers $0$,

• si $p>1/2$, quand on itère l’automate cellulaire, la proportion de carrés blancs tend vers $0$.

Cette propriété correspond à l’obtention d’un consensus sur la couleur qui était initialement majoritaire dans la configuration. On dit qu’un tel automate cellulaire classifie la densité. Il s’agit maintenant de corriger un nombre infini d’anomalies, donc le problème est plus difficile !

Regardons le problème en dimension $2$, lorsque la configuration est représentée sur la grille. Le comportement souhaité peut donc être représenté comme ci-dessous.

	$\xrightarrow[]{\hbox{évolution}}$
Majorité de cellules blanches ($p<1/2$)		Configuration toute blanche
	$\xrightarrow[]{\hbox{évolution}}$
Majorité de cellules bleues ($p>1/2$)		Configuration toute bleue

Ce problème trouve sa justification dans le contexte de ce qu’on appelle les réseaux distribués. De tels réseaux sont constitués d’un grand nombre d’entités, et ne disposent pas d’une autorité centrale. Les réseaux informatiques actuels opèrent, pour la plupart, sur ce mode. Les automates cellulaires sont une formalisation de la notion de réseau distribué. Quant au problème de la classification, il s’agit d’une abstraction du problème de recherche de consensus dans un réseau distribué : comment faire émerger une information globale en collectant seulement une information locale à chaque étape ?

Concevoir un automate cellulaire qui classifie la densité n’est pas une tâche aisée : premièrement, il n’est pas possible de centraliser l’information (les cellules sont indistingables) ; deuxièmement, il n’est pas possible d’utiliser des techniques de comptage classique (les cellules peuvent seulement mémoriser leur couleur) [4].

Dans un travail en collaboration avec Ana Bušić et Nazim Fatès [5], nous avons démontré le résultat suivant, qui résout le problème de la classification de la densité en dimension $2$.

Nous avons représenté ci-dessous un exemple d’évolution de l’automate cellulaire de Toom, pour une configuration initiale tirée avec une densité $p=0.45$ de cellules bleues. Sur les figures, on peut suivre l’évolution de deux îles particulières de cellules bleues, encerclées en rouge et en vert, qui finissent par disparaître.

L’énoncé du théorème recèle une subtilité. Considérons en effet une configuration constituée par une alternance de bandes verticales blanches et bleues, de largeurs variables. Une telle configuration est laissée inchangée par l’automate cellulaire de Toom et n’évolue donc pas vers une configuration toute blanche ou toute bleue. Ceci illustre la nature probabiliste du résultat énoncé, qui montre la convergence pour les configurations initiales choisies aléatoirement.

L’intérêt de ce théorème est qu’il propose une solution très simple au problème de la classification de la densité en dimension $2$. Pour mieux comprendre ce résultat, nous allons maintenant présenter deux situations proches dans lesquelles, pour la première, il n’y a pas de solution connue, et, pour la seconde, on sait démontrer qu’il n’y a pas du tout de solution.

En premier lieu, regardons le problème de la classification de la densité en dimension $1$. C’est un problème non résolu : savoir s’il existe un automate cellulaire qui classifie la densité est une question ouverte, c’est-à-dire dont personne ne connaît aujourd’hui la réponse. Des simulations suggèrent que l’automate GKL pourrait bien classifier la densité en dimension $1$. Par exemple, la figure ci-dessous représente un diagramme espace-temps pour l’automate cellulaire GKL, à partir d’une configuration aléatoire dans laquelle les cellules blanches sont majoritaires.

Mais des simulations ne constituent pas une preuve, et le résultat reste à démontrer. Une avancée récente a été fournie par Siamak Taati [6], qui a démontré que l’automate cellulaire GKL sait corriger un bruit aléatoire s’il est suffisamment petit, inférieur à 0,17%. Comme on le voit, il s’agit d’une première étape, mais il reste du chemin à parcourir pour aller de $0.0017$ jusqu’à $1/2$ !

En second lieu, intéressons-nous à la variante périodique du problème de la classification de la densité. C’est en fait dans ce cadre que le problème a été initialement introduit dans les années 80. Cette variante a fait et continue de faire l’objet de nombreuses études, aussi bien numériques que théoriques. Définissons le contexte. Une configuration périodique est une configuration obtenue en répétant un motif fini. Précisément, en dimension $1$, une configuration est périodique si elle possède la propriété suivante : il existe un entier positif $L$ tel que pour tout entier $i$, les cellules d’indices $i$ et $i+L$ sont de même couleur. Cela signifie qu’on peut identifier un motif de taille $L$ qui se répète. Pour une telle configuration, $L$ cellules consécutives contiennent toujours le même nombre $n_B$ de cellules bleues. (Exercice : le montrer !) On appelle $d=n_B/L$, la densité de cellules bleues.

Voici un exemple de configuration périodique de dimension $1$, pour laquelle $L=7$ et $d=4/7$.

Ces notions s’étendent à la dimension $2$ : une configuration est alors périodique s’il existe un entier positif $L$ tel que pour tout couple $(i,j)$, les cellules d’indice $(i,j)$, $(i+L,j)$ et $(i,j+L)$ ont la même couleur, ce qui signifie qu’il y a un motif carré de taille $L$ qui se répète. Pour une telle configuration, un carré de côté $L$ contient toujours le même nombre $n_B$ de cellules bleues, et on appelle $d=n_B/L^2$, la densité de cellules bleues.

Voici un exemple de configuration périodique de dimension $2$, pour laquelle $L=3$ et $d=4/9$.

En dimension $1$, une configuration périodique peut être repliée sur elle-même pour être vue comme une configuration sur un anneau. On parle alors de configuration finie. De même, une configuration périodique en dimension $2$ peut être vue comme une configuration finie sur un tore bi-dimensionnel : on part du motif carré de taille $L$ qui se répète dans la configuration, on replie ses bords horizontaux bas et haut de manière à former un tube, puis on replie à nouveau ce tube en collant ses deux extrémités [7].

On dit qu’un automate cellulaire classifie la densité dans la variante périodique si, pour toute configuration périodique :

• si $d<1/2$, quand on itère l’automate cellulaire, la proportion de carrés bleus tend vers $0$,

• si $d>1/2$, quand on itère l’automate cellulaire, la proportion de carrés blancs tend vers $0$.

En 1995, Land et Belew ont démontré qu’il n’existait pas d’automate cellulaire classifiant la densité dans la variante périodique, aussi bien en dimension $1$ qu’en dimension $2$ [8].

Ce résultat négatif n’a pas mis fin aux recherches, qui se sont alors concentrées sur la quête expérimentale d’un automate ayant la propriété voulue pour la plus grande proportion possible de configurations périodiques, quand on augmente la taille $L$ du motif qui se répète. En dimension $1$, l’un des meilleurs automates cellulaires connus à ce jour n’est autre que... l’automate GKL. Encore lui !

Notre résultat, énoncé dans le théorème ci-dessus, a quant à lui relancé l’intérêt autour de ces questions selon un angle nouveau, en montrant que la classification de la densité était possible à condition de changer le point de vue et la formulation du problème.