TLA+ ne peut pas vérifier les propriétés d'existence et les hyperproperties

Principes de vérification de TLA+

TLA+ décrit un système comme un ensemble de behaviors, chaque behavior étant une suite d'états. Les propriétés de base s'expriment avec les opérateurs temporels []P (toujours), P' (état suivant) et <>P (éventuellement). Un invariant []P doit être vrai dans l'état initial de chaque behavior et, par définition de [], dans tous les états futurs. Les propriétés d'action, comme [] (x' >= x), et les propriétés de vivacité, comme []<>P, sont également supportées. Ces constructions couvrent les safety (quelque chose de mauvais n'arrive jamais) et les liveness (quelque chose de bon finit par arriver) classiques.

Limites d'expressivité

Le formalisme impose une quantification universelle sur l'ensemble des behaviors. Ainsi, TLA+ ne peut pas exprimer une propriété de type « existe un behavior où P est vrai », même si ce behavior est réalisable. Cette impossibilité exclut les propriétés de reachability (ex. « le jeu est gagnable ») et leurs variantes « P est atteignable depuis chaque état initial ». De plus, les propriétés qui nécessitent plusieurs étapes consécutives, comme « appuyer sur Supprimer puis Annuler restaure l'état d'origine », ne sont pas modélisables directement, car les invariants et les actions ne couvrent qu'un état ou un pas.

Les opérateurs temporels de TLA+ ne traitent que le temps logique. Les calculs sur les nombres à virgule flottante ou les contraintes de temps réel (ex. « l'ordinateur s'allume en moins de dix pas après mise sous tension ») échappent au modèle. Enfin, les hyperproperties, qui comparent plusieurs behaviors simultanément, sont hors de portée. Un exemple typique est « le mode économie d'énergie consomme toujours moins que le mode normal », qui nécessite deux executions parallèles du même modèle pour être vérifié.

Conséquences pratiques

Lorsque l'on utilise TLA+ pour concevoir un protocole concurrent, on peut garantir que aucune violation d'invariant ne se produira et que les conditions de terminaison exprimées par []<>P seront respectées. En revanche, on ne pourra pas prouver que le système possède une exécution favorable, ni que deux implémentations respectent une même contrainte de performance statistique. Les équipes doivent donc compléter TLA+ par d'autres techniques : analyse de modèles probabilistes pour les métriques de temps, tests de simulation pour les propriétés d'existence, ou cadres de vérification de hyperproperties comme HyperLTL.

Illustration de la syntaxe

// invariant example
[] (x' >= x)
// liveness example
[]<> (leader = chosen)
// action property example
[](P => P')