calcul de processus

En informatique , les calculs de processus (ou algèbres de processus ) forment une famille diversifiée d'approches apparentées permettant de modéliser formellement les systèmes concurrents . Ces calculs fournissent des outils pour la description de haut niveau des interactions, des communications et des synchronisations entre un ensemble de processus indépendants. Ils définissent des lois algébriques permettant de manipuler et d'analyser les descriptions de processus, et autorisent également un raisonnement formel sur les équivalences entre processus (par exemple, par bisimulation ). Parmi les calculs de processus les plus connus, on peut citer CSP , CCS , ACP et LOTOS . Plus récemment, cette famille s'est enrichie du π-calcul , du calcul ambiant , de PEPA , du calcul de jointure .

Caractéristiques essentielles

Bien que la variété des calculs de processus existants soit très grande (y compris des variantes qui intègrent un comportement stochastique , des informations temporelles et des spécialisations pour l'étude des interactions moléculaires), il existe plusieurs caractéristiques que tous les calculs de processus ont en commun :

Représenter les interactions entre processus indépendants comme une communication ( échange de messages ), plutôt que comme une modification de variables partagées.
Décrire les processus et les systèmes à l'aide d'un petit ensemble de primitives et d'opérateurs permettant de combiner ces primitives.
Définition des lois algébriques pour les opérateurs de processus, qui permettent de manipuler les expressions de processus à l'aide d'un raisonnement équationnel .

Mathématiques des processus

Pour définir un calcul de processus , on part d'un ensemble de noms (ou canaux ) dont le but est d'assurer la communication. Dans de nombreuses implémentations, les canaux possèdent une structure interne riche pour améliorer l'efficacité, mais celle-ci est généralement occultée dans les modèles théoriques. Outre les noms, il faut un moyen de former de nouveaux processus à partir d'anciens. Les opérateurs de base, toujours présents sous une forme ou une autre, permettent :

composition parallèle des processus
spécification des canaux à utiliser pour l'envoi et la réception des données
séquentialisation des interactions
masquage des points d'interaction
récursivité ou réplication de processus

Composition parallèle

Composition parallèle de deux processus ${\displaystyle {\mathit {P <semantics><mrow><mstyle><mrow><mrow><mi>P</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {P}}}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {Q <semantics><mrow><mstyle><mrow><mrow><mi>Q</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {Q}}}</annotation></semantics></math><img src=$ ${\displaystyle P\vert Q <semantics><mrow><mstyle><mi>P</mi><mo>|</mo><mi>Q</mi></mstyle></mrow><annotation>{\displaystyle P\vert Q}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {P <semantics><mrow><mstyle><mrow><mrow><mi>P</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {P}}}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {Q <semantics><mrow><mstyle><mrow><mrow><mi>Q</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {Q}}}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {P <semantics><mrow><mstyle><mrow><mrow><mi>P</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {P}}}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {Q <semantics><mrow><mstyle><mrow><mrow><mi>Q</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {Q}}}</annotation></semantics></math><img src=$

Les canaux peuvent être synchrones ou asynchrones. Dans le cas d'un canal synchrone, le processus qui envoie un message attend qu'un autre processus l'ait reçu. Les canaux asynchrones ne nécessitent aucune synchronisation. Dans certains calculs de processus (notamment le π-calcul ), les canaux eux-mêmes peuvent être transmis par messages via d'autres canaux, ce qui permet de modifier la topologie des interconnexions entre les processus. Certains calculs de processus permettent également la création de canaux pendant l'exécution d'un calcul.

Communication

L'interaction peut être (mais n'est pas toujours) un flux d'informations dirigé . Autrement dit, l'entrée et la sortie peuvent être distinguées comme des primitives d'interaction duales. Les calculs de processus qui font de telles distinctions définissent généralement un opérateur d'entrée ( par exemple) . ${\displaystyle x(v) <semantics><mrow><mstyle><mi>x</mi><mo>(</mo><mi>v</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle x(v)}</annotation></semantics></math><img src=$ par exemple ${\displaystyle x\langle y angle <semantics><mrow><mstyle><mi>x</mi><mo>⟨</mo><mi>y</mi><mo>⟩</mo></mstyle></mrow><annotation>{ displaystyle x langle y rangle}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {x <semantics><mrow><mstyle><mrow><mrow><mi>x</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {x}}}</annotation></semantics></math><img src=$

En cas d'échange d'informations, celles-ci circuleront du processus de sortie vers le processus d'entrée. La primitive de sortie spécifiera les données à envoyer. ${\displaystyle x\langle y angle <semantics><mrow><mstyle><mi>x</mi><mo>⟨</mo><mi>y</mi><mo>⟩</mo></mstyle></mrow><annotation>{ displaystyle x langle y rangle}</annotation></semantics></math><img src=$ ${\displaystyle y <semantics><mrow><mstyle><mi>y</mi></mstyle></mrow><annotation>{\displaystyle y}</annotation></semantics></math><img src=$ ${\displaystyle x(v) <semantics><mrow><mstyle><mi>x</mi><mo>(</mo><mi>v</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle x(v)}</annotation></semantics></math><img src=$ ${\displaystyle v <semantics><mrow><mstyle><mi>v</mi></mstyle></mrow><annotation>{\displaystyle v}</annotation></semantics></math><img src=$

Composition séquentielle

Parfois, les interactions doivent être ordonnées temporellement. Par exemple, il peut être souhaitable de spécifier des algorithmes tels que : recevoir d’abord des données sur ${\displaystyle {\mathit {x <semantics><mrow><mstyle><mrow><mrow><mi>x</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {x}}}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {y <semantics><mrow><mstyle><mrow><mrow><mi>y</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {y}}}</annotation></semantics></math><img src=$ La composition séquentielle peut être utilisée à ces fins . Elle est bien connue dans d'autres modèles de calcul. Dans les calculs de processus, l'opérateur de séquentialisation est généralement intégré à l'entrée ou à la sortie, voire aux deux. Par exemple, le processus ${\displaystyle x(v)\cdot P <semantics><mrow><mstyle><mi>x</mi><mo>(</mo><mi>v</mi><mo>)</mo><mo>⋅</mo><mi>P</mi></mstyle></mrow><annotation>{\displaystyle x(v)\cdot P}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {x <semantics><mrow><mstyle><mrow><mrow><mi>x</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {x}}}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {P <semantics><mrow><mstyle><mrow><mrow><mi>P</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {P}}}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {x <semantics><mrow><mstyle><mrow><mrow><mi>x</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {x}}}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {v <semantics><mrow><mstyle><mrow><mrow><mi>v</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {v}}}</annotation></semantics></math><img src=$

Sémantique de réduction

La règle de réduction opérationnelle fondamentale, qui renferme l'essence computationnelle des calculs de processus, peut être exprimée uniquement en termes de composition parallèle, de séquentialisation, d'entrée et de sortie. Les détails de cette réduction varient selon les calculs, mais l'essence demeure globalement la même. La règle de réduction est la suivante :

{\displaystyle x\langle y angle \cdot P\;\vert \;x(v)\cdot Q\longrightarrow P\;\vert \;Q[^{y}\!/\!_{v}] <semantics><mrow><mstyle><mi>x</mi><mo>⟨</mo><mi>y</mi><mo>⟩</mo><mo>⋅</mo><mi>P</mi><mspace></mspace><mo>|</mo><mspace></mspace><mi>x</mi><mo>(</mo><mi>v</mi><mo>)</mo><mo>⋅</mo><mi>Q</mi><mo>⟶</mo><mi>P</mi><mspace></mspace><mo>|</mo><mspace></mspace><mi>Q</mi><msup><mo>[</mo><mrow><mi>y</mi></mrow></msup><mspace></mspace><mrow><mo>/</mo></mrow><msub><mspace></mspace><mrow><mi>v</mi></mrow></msub><mo>]</mo></mstyle></mrow><annotation>{\displaystyle x\langle y angle \cdot P\;\vert \;x(v)\cdot Q\longrightarrow P\;\vert \;Q[^{y}\!/\!_{v}]}</annotation></semantics></math></span><img src=

L'interprétation de cette règle de réduction est la suivante :

Le processus ${\displaystyle x\langle y angle \cdot P <semantics><mrow><mstyle><mi>x</mi><mo>⟨</mo><mi>y</mi><mo>⟩</mo><mo>⋅</mo><mi>P</mi></mstyle></mrow><annotation>{ displaystyle x langle y rangle cdot P}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {y <semantics><mrow><mstyle><mrow><mrow><mi>y</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {y}}}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {x <semantics><mrow><mstyle><mrow><mrow><mi>x</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {x}}}</annotation></semantics></math><img src=$ ${\displaystyle x(v)\cdot Q <semantics><mrow><mstyle><mi>x</mi><mo>(</mo><mi>v</mi><mo>)</mo><mo>⋅</mo><mi>Q</mi></mstyle></mrow><annotation>{\displaystyle x(v)\cdot Q}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {x <semantics><mrow><mstyle><mrow><mrow><mi>x</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {x}}}</annotation></semantics></math><img src=$
Une fois le message envoyé, ${\displaystyle x\langle y angle \cdot P <semantics><mrow><mstyle><mi>x</mi><mo>⟨</mo><mi>y</mi><mo>⟩</mo><mo>⋅</mo><mi>P</mi></mstyle></mrow><annotation>{ displaystyle x langle y rangle cdot P}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {P <semantics><mrow><mstyle><mrow><mrow><mi>P</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {P}}}</annotation></semantics></math><img src=$ ${\displaystyle x(v)\cdot Q <semantics><mrow><mstyle><mi>x</mi><mo>(</mo><mi>v</mi><mo>)</mo><mo>⋅</mo><mi>Q</mi></mstyle></mrow><annotation>{\displaystyle x(v)\cdot Q}</annotation></semantics></math><img src=$ ${\displaystyle Q[^{y}\!/\!_{v}] <semantics><mrow><mstyle><mi>Q</mi><msup><mo>[</mo><mrow><mi>y</mi></mrow></msup><mspace></mspace><mrow><mo>/</mo></mrow><msub><mspace></mspace><mrow><mi>v</mi></mrow></msub><mo>]</mo></mstyle></mrow><annotation>{\displaystyle Q[^{y}\!/\!_{v}]}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {Q <semantics><mrow><mstyle><mrow><mrow><mi>Q</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {Q}}}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {v <semantics><mrow><mstyle><mrow><mrow><mi>v</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {v}}}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {y <semantics><mrow><mstyle><mrow><mrow><mi>y</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {y}}}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {x <semantics><mrow><mstyle><mrow><mrow><mi>x</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {x}}}</annotation></semantics></math><img src=$

La classe des processus qui ${\displaystyle {\mathit {P <semantics><mrow><mstyle><mrow><mrow><mi>P</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {P}}}</annotation></semantics></math><img src=$

Dissimulation

Les processus ne limitent pas le nombre de connexions possibles à un point d'interaction donné. Cependant, les points d'interaction permettent l'interférence (c'est-à-dire l'interaction). Pour la synthèse de systèmes compacts, minimaux et compositionnels, la capacité à restreindre l'interférence est cruciale. Les opérations de masquage permettent de contrôler les connexions établies entre les points d'interaction lors de la composition de processus en parallèle. Le masquage peut être noté de diverses manières. Par exemple, dans le π-calcul, le masquage d'un nom ${\displaystyle {\mathit {x <semantics><mrow><mstyle><mrow><mrow><mi>x</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {x}}}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {P <semantics><mrow><mstyle><mrow><mrow><mi>P</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {P}}}</annotation></semantics></math><img src=$ ${\displaystyle ( u \;x)P <semantics><mrow><mstyle><mo>(</mo><mi>ν</mi><mspace></mspace><mi>x</mi><mo>)</mo><mi>P</mi></mstyle></mrow><annotation>{\displaystyle ( u \;x)P}</annotation></semantics></math><img src=$ ${\displaystyle P\setminus \{x\ <semantics><mrow><mstyle><mi>P</mi><mo>∖</mo><mo>{</mo><mi>x</mi><mo>}</mo></mstyle></mrow><annotation>{\displaystyle P\setminus \{x\}}</annotation></semantics></math><img src=$

Récursivité et réplication

Les opérations présentées jusqu'ici ne décrivent qu'une interaction finie et sont donc insuffisantes pour une calculabilité complète, qui inclut les comportements non terminaux. La récursivité et la réplication sont des opérations qui permettent des descriptions finies de comportements infinis. La récursivité est bien connue dans le domaine séquentiel. La réplication ${\displaystyle !P <semantics><mrow><mstyle><mo>!</mo><mi>P</mi></mstyle></mrow><annotation>{\displaystyle !P}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {P <semantics><mrow><mstyle><mrow><mrow><mi>P</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {P}}}</annotation></semantics></math><img src=$

{\displaystyle !P=P\mid !P <semantics><mrow><mstyle><mo>!</mo><mi>P</mi><mo>=</mo><mi>P</mi><mo>∣</mo><mo>!</mo><mi>P</mi></mstyle></mrow><annotation>{\displaystyle !P=P\mid !P}</annotation></semantics></math></span><img src=

Processus nul

Les calculs de processus incluent généralement aussi un processus nul (noté de diverses manières comme ${\displaystyle {\mathit {nil <semantics><mrow><mstyle><mrow><mrow><mi>n</mi><mi>je</mi><mi>l</mi></mrow></mrow></mstyle></mrow><annotation>{ displaystyle { mathit {nil}}}</annotation></semantics></math><img src=$ ${\displaystyle 0 <semantics><mrow><mstyle><mn>0</mn></mstyle></mrow><annotation>{\displaystyle 0}</annotation></semantics></math><img src=$ ${\displaystyle {\mathit {STOP <semantics><mrow><mstyle><mrow><mrow><mi>S</mi><mi>T</mi><mi>O</mi><mi>P</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathit {STOP}}}</annotation></semantics></math><img src=$ ${\displaystyle \delta <semantics><mrow><mstyle><mi>δ</mi></mstyle></mrow><annotation>{\displaystyle \delta }</annotation></semantics></math><img src=$

Algèbre des processus discrets et continus

L'algèbre des processus a été étudiée pour le temps discret et le temps continu (temps réel ou temps dense).

Histoire

Durant la première moitié du XXe siècle, divers formalismes furent proposés pour appréhender le concept informel de fonction calculable , les fonctions μ -récursives , les machines de Turing et le lambda-calcul étant sans doute les exemples les plus connus aujourd'hui. Le fait surprenant qu'ils soient essentiellement équivalents, en ce sens qu'ils sont tous encodables les uns dans les autres, conforte la thèse de Church-Turing . Une autre caractéristique commune, moins souvent mentionnée, est qu'ils s'appréhendent tous plus aisément comme des modèles de calcul séquentiel . La consolidation ultérieure de l'informatique a nécessité une formulation plus nuancée de la notion de calcul, notamment des représentations explicites de la concurrence et de la communication. Des modèles de concurrence tels que les calculs de processus, les réseaux de Petri en 1962 et le modèle d'acteurs en 1973 ont émergé de cette recherche.

Les recherches sur les calculs de processus ont véritablement débuté avec les travaux fondateurs de Robin Milner sur le Calcul des Systèmes Communicants (CSC), entre 1973 et 1980. Le Calcul des Processus Séquentiels Communicants (CPC) de C.A.R. Hoare est apparu pour la première fois en 1978 et a ensuite été développé en un calcul de processus à part entière au début des années 1980. De nombreuses interactions ont eu lieu entre le CSC et le CPC au cours de leur développement. En 1982, Jan Bergstra et Jan Willem Klop ont entrepris des travaux sur ce qui allait devenir l' Algèbre des Processus Communicants (APC) et ont introduit le terme d'algèbre de processus pour décrire leurs travaux. Le CSC, le CPC et l'APC constituent les trois branches principales de la famille des calculs de processus : la majorité des autres calculs de processus trouvent leur origine dans l'un de ces trois calculs.

Recherches actuelles

Divers calculs de processus ont été étudiés, mais tous ne correspondent pas au paradigme présenté ici. Le calcul ambiant en est peut-être l'exemple le plus frappant . Cela n'est pas surprenant, car les calculs de processus constituent un domaine de recherche très actif. Actuellement, les recherches sur les calculs de processus portent sur les problèmes suivants.

Développement de nouveaux calculs de processus pour une meilleure modélisation des phénomènes informatiques.
Trouver des sous-calculs bien définis d'un calcul de processus donné est important car (1) la plupart des calculs sont assez généraux et il est difficile de se prononcer sur des processus arbitraires ; et (2) les applications informatiques exploitent rarement l'intégralité d'un calcul. Elles utilisent plutôt des processus dont la forme est très contrainte. La contrainte de la forme des processus est principalement étudiée à l'aide des systèmes de types .
Logiques pour les processus qui permettent de raisonner sur des propriétés (essentiellement) arbitraires des processus, suivant les idées de la logique de Hoare .
Théorie comportementale : que signifie l’équivalence entre deux processus ? Comment déterminer si deux processus sont différents ? Peut-on identifier des représentants de classes d’équivalence de processus ? Généralement, deux processus sont considérés comme identiques si aucun contexte, c’est-à-dire aucun autre processus exécuté en parallèle, ne permet de déceler une différence. Malheureusement, formaliser précisément cette intuition est complexe et aboutit souvent à des caractérisations de l’égalité difficiles à manipuler (qui, dans la plupart des cas, sont également indécidables, du fait du problème de l’arrêt ). Les bisimulations constituent un outil technique facilitant le raisonnement sur les équivalences de processus.
Expressivité des calculs. L'expérience en programmation montre que certains problèmes sont plus faciles à résoudre dans certains langages que dans d'autres. Ce phénomène exige une caractérisation plus précise de l'expressivité des calculs modélisant le calcul que celle permise par la thèse de Church-Turing . Une approche consiste à considérer les encodages entre deux formalismes et à examiner les propriétés que ces encodages peuvent potentiellement préserver. Plus les propriétés préservées sont nombreuses, plus l'objet de l'encodage est dit expressif. Concernant les calculs de processus, les résultats les plus connus montrent que le π-calcul synchrone est plus expressif que sa variante asynchrone, possède la même puissance expressive que le π-calcul d' ordre supérieur , mais est moins expressif que le calcul ambiant .
L'utilisation du calcul des processus pour modéliser les systèmes biologiques (π-calcul stochastique, BioAmbients, Beta Binders, BioPEPA, calcul des branes) est envisagée. Certains estiment que la compositionnalité offerte par les outils de la théorie des processus peut aider les biologistes à structurer leurs connaissances de manière plus formelle.

implémentations logicielles

Les concepts sous-jacents à l'algèbre des processus ont donné naissance à plusieurs outils, notamment :

CADP
Atelier de concurrence
Ensemble d'outils mCRL2

Relation avec d'autres modèles de concurrence

Le monoïde d'histoire est l' objet libre capable de représenter génériquement l'historique de processus communicants individuels. Un calcul de processus est alors un langage formel imposé à un monoïde d'histoire de manière cohérente. Autrement dit, un monoïde d'histoire ne peut qu'enregistrer une séquence d'événements, synchronisée, sans spécifier les transitions d'état autorisées. Ainsi, un calcul de processus est au monoïde d'histoire ce qu'un langage formel est à un monoïde libre (un langage formel est un sous-ensemble de l'ensemble de toutes les chaînes de longueur finie possibles d'un alphabet généré par l' étoile de Kleene ).

L'utilisation de canaux de communication est l'une des caractéristiques qui distinguent les calculs de processus des autres modèles de concurrence , tels que les réseaux de Petri et le modèle d'acteurs (voir Modèle d'acteurs et calculs de processus ). L'une des motivations fondamentales de l'inclusion de canaux dans les calculs de processus était de permettre l'application de certaines techniques algébriques, facilitant ainsi le raisonnement algébrique sur les processus.