Les systèmes faiblement synchrones avec trois machines sont Turing-complets
Résumé
Les automates finis communicants permettent de modéliser les systèmes distribués asynchrones à passage de messages. Dans les systèmes faiblement synchrones, les processus communiquent par le biais de phases au cours desquelles chaque processus envoie d'abord tous ses messages, puis reçoit tous les messages des autres processus. Ces systèmes bénéficient d'une forme limitée de synchronisation et, pour certains modèles de communication, cette restriction est suffisante pour que le problème d'accessibilité devienne décidable. En particulier, nous explorons le cas de la communication p2p (FIFO), pour lequel le problème d'accessibilité est connu pour être indécidable pour quatre processus, mais décidable pour deux. Nous montrons que le problème d'accessibilité pour les systèmes faiblement synchrones de trois processus est indécidable. Ce résultat est fortement inspiré par notre étude de la largeur arborescente des diagrammes de séquence de messages (MSC pour Message Sequence Chart) qui peuvent être générés par de tels systèmes. En ce sens, la principale contribution de ce travail est un système faiblement synchrone avec trois processus qui génère des MSCs d'une largeur arborescente arbitrairement grande.
Origine : Fichiers produits par l'(les) auteur(s)