À retenir
- C'est une relation d'équivalence stricte entre les comportements de deux systèmes.
- Elle garantit qu'on peut substituer un système par un autre sans changer la logique d'exécution.
- Elle est bidirectionnelle : chaque système doit pouvoir "imiter" l'autre à l'infini.
La bisimulation est une manière de comparer deux systèmes informatiques pour vérifier s'ils se comportent exactement de la même façon. On peut l'imaginer comme un jeu de miroir : si le premier système effectue une action, le second doit pouvoir faire la même chose pour arriver dans un état équivalent, et inversement. C'est une notion plus forte qu'une simple ressemblance, car elle garantit que les deux systèmes réagiront de manière identique à chaque étape de leur fonctionnement.
Étymologie
Le terme est composé du préfixe latin bi- (deux, double) et de simulation. Il a été popularisé dans les années 1980 par des chercheurs comme David Park et Robin Milner dans le cadre de l'étude des systèmes concurrents (systèmes où plusieurs tâches s'exécutent en même temps).
Exemples d'usage
- Deux automates de distributeurs de boissons : l'un possède 10 états internes et l'autre 5, mais pour l'utilisateur, ils proposent les mêmes boutons et réagissent de la même manière.
- Un protocole de communication complexe et sa version simplifiée (modèle) que l'on compare pour prouver que le modèle est fidèle à la réalité.
- La vérification qu'une optimisation de code ne change absolument pas le comportement logique d'un programme.
Cas d'usage
Elle est principalement utilisée en méthodes formelles et en vérification de logiciels (model checking). Elle permet de réduire la complexité d'un système en remplaçant un composant très lourd par un composant plus simple qui possède la même signature comportementale. On s'en sert aussi pour prouver la sécurité de protocoles réseaux.
Bonnes pratiques
Pour établir une bisimulation, il ne suffit pas de regarder les entrées et les sorties (boîte noire) ; il faut s'assurer que chaque choix possible dans un système peut être répliqué par l'autre. Un piège classique est de croire qu'une simple simulation (A fait ce que fait B) suffit, alors qu'en bisimulation, la réciproque est obligatoire.
Synonymes
Antonymes
Conseil
Pour bien comprendre, visualisez deux joueurs de mime : si le premier lève le bras, le second doit le lever aussi pour rester "synchro". Si à n'importe quel moment l'un des deux peut faire un mouvement que l'autre ne peut pas reproduire, alors il n'y a pas bisimulation.
Questions fréquentes
Quelle est la différence entre simulation et bisimulation ?
La simulation est à sens unique : le système A peut copier le système B. La bisimulation exige que A copie B ET que B copie A, créant une équivalence parfaite.
Est-ce utilisé dans le développement web classique ?
Rarement au quotidien. C'est un concept théorique utilisé surtout pour la conception de systèmes critiques (aéronautique, médical, processeurs) où l'on doit prouver que le code est sans faille.
Pourquoi simplifier un système si on a déjà l'original ?
Pour faciliter les tests. Il est plus simple de prouver qu'un petit système de 10 étapes fonctionne sans erreur plutôt qu'un système de 10 000 étapes, si l'on a prouvé qu'ils sont bisimilaires.