Modèles de concurrence et calculs de processus
Les modèles de concurrence et les calculs de processus offrent des descriptions formelles de la manière dont des processus indépendants s'exécutent, communiquent et se synchronisent.
Definition
Un calcul de processus est une algèbre formelle permettant de décrire des systèmes concurrents comme des processus communicants, avec des opérateurs pour la composition parallèle, la communication et le choix, ainsi que des équivalences qui déterminent quand deux processus se comportent de manière identique.
Scope
Ce sujet aborde les modèles algébriques de calcul concurrent : le CSP de Hoare et le CCS de Milner, le pi-calcul pour les processus mobiles dont la topologie de communication évolue, et le modèle d'acteur pour la transmission asynchrone de messages. Il traite des primitives de communication et de synchronisation, des équivalences comportementales telles que la bisimulation, et du contraste entre la concurrence à mémoire partagée et la concurrence par passage de messages.
Core questions
- Comment les processus communicants concurrents peuvent-ils être décrits algébriquement ?
- Quand deux processus concurrents sont-ils équivalents sur le plan comportemental ?
- Comment le passage de messages se compare-t-il à la concurrence à mémoire partagée ?
- Comment les structures de communication dynamiques sont-elles modélisées, comme dans le pi-calcul ?
Key theories
- Communicating Sequential Processes (CSP)
- Le CSP de Hoare modélise la concurrence à travers des processus qui se synchronisent sur des événements de communication partagés, offrant une base pour les langages de passage de messages et une théorie du raffinement de processus.
- CCS and bisimulation
- Le Calcul des Systèmes Communicants de Milner fournit une algèbre de processus avec une notion précise d'équivalence comportementale, la bisimulation, pour raisonner sur l'interchangeabilité des processus.
- The pi-calculus
- Milner, Parrow et Walker ont étendu les calculs de processus à la mobilité, permettant aux canaux de communication eux-mêmes d'être passés comme messages, de sorte que la structure de connexion évolue dynamiquement.
Clinical relevance
Les calculs de processus et le modèle d'acteur sous-tendent la conception de langages et de frameworks concurrents et distribués basés sur le passage de messages, et ils fournissent des outils formels pour la spécification et la vérification de protocoles. La bisimulation et le raffinement offrent des critères précis pour un comportement concurrent correct.
History
La théorie de la concurrence a mûri à la fin des années 1970 avec le CSP de Hoare et le CCS de Milner, tandis que le modèle d'acteur de Hewitt (1973) offrait une alternative de passage de messages asynchrone. Le pi-calcul, en 1992, a permis de modéliser la mobilité des processus. Ces calculs ont influencé les langages de passage de messages et les bibliothèques de concurrence, et demeurent des fondements pour la vérification de protocoles.
Debates
- Mémoire partagée versus passage de messages
- Une question de conception fondamentale est de savoir si la concurrence doit être organisée autour d'un état mutable partagé avec synchronisation ou autour de processus isolés échangeant des messages, les calculs de processus et le modèle d'acteur défendant cette dernière approche.
Key figures
- C. A. R. Hoare
- Robin Milner
- Carl Hewitt
- Joachim Parrow
- David Walker
Related topics
Seminal works
- hoare1978
- milner1989
- milner1992
- hewitt1973
Frequently asked questions
- Qu'est-ce que la bisimulation ?
- La bisimulation est une équivalence sur les processus qui est vérifiée lorsque chacun peut correspondre indéfiniment aux étapes observables de l'autre, formalisant l'idée que deux processus concurrents présentent le même comportement.
- Qu'apporte le pi-calcul par rapport aux calculs antérieurs ?
- Le pi-calcul modélise la mobilité en permettant l'envoi de canaux de communication comme messages, de sorte que la topologie des interactions peut changer pendant l'exécution, capturant ainsi les systèmes dynamiques et reconfigurables.