Les systèmes faiblement synchrones avec trois machines sont Turing-complets - IDEX UCA JEDI Université Côte d'Azur Access content directly
Conference Papers Year : 2024

Les systèmes faiblement synchrones avec trois machines sont Turing-complets

Abstract

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.
Fichier principal
Vignette du fichier
RPalgotel.pdf (1.94 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-04551070 , version 1 (18-04-2024)

Identifiers

  • HAL Id : hal-04551070 , version 1

Cite

Cinzia Di Giusto, Davide Ferré, Étienne Lozes, Nicolas Nisse. Les systèmes faiblement synchrones avec trois machines sont Turing-complets. AlgoTel 2024 – 26èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2024, Saint-Briac-sur-Mer, France. ⟨hal-04551070⟩
6 View
2 Download

Share

Gmail Facebook X LinkedIn More