Similitudes et différences dans les principales algèbres de processus

À ma connaissance, il existe trois grandes algèbres de processus qui ont inspiré une vaste gamme de recherches sur les modèles formels de concurrence. Ceux-ci sont:

• CCS et -calculus tous les deux par Robin Milner$\pi$
• CSP par Tony Hoare et
• ACP par Jan Bergstra et Jan Willem Klop

Tous les trois semblent avoir à ce jour un suivi assez actif et de nombreuses recherches ont été effectuées sur eux.

Quelles sont les principales similitudes et différences de ces approches? Pourquoi la recherche en algèbre de processus a-t-elle divergé au lieu de converger, en ce sens qu'il n'y a pas de modèle universel unique pour unifier le domaine?

Je ne connais que CSP et CCS / pi-calcul (pas ACP).

Le CSP était motivé par des processus de programmation impératifs communiquant via des messages. Hoare a ensuite tenté d'en extraire un simple calcul. CCS, d'autre part, était un effort pour créer un calcul fondamental comme le calcul lambda. Compte tenu de leurs points de départ d'origine et de leur forme finale, je dirais qu'ils ont convergé plutôt que divergé.

Ce que je trouve commun entre CSP et CCS, c'est que les deux sont basés sur la notion de "processus" (et, par là, je veux dire une notion abstraite d'événements organisés dans le temps). La principale différence entre eux est que le CSP a deux formes de choix (interne / externe ou non déterministe / déterministe). Dans CCS, les deux idées sont fusionnées en une seule. Je pense que c'est une différence irréconciliable.

La distinction entre choix interne et externe permet au CSP d'avoir une sémantique en termes de traces linéaires. La sémantique CCS, d'autre part, doit être basée sur des arbres.

Je pense que le plan actuel de Hoare pour "Unifier les théories" est de les mettre dans un même cadre. Nous devons attendre et voir ce qu'il propose!

Une autre réponse partielle.

L'approche de la sémantique adoptée par les différentes communautés différait, du moins à l'origine.

• La sémantique ACP est axiomatique / algébrique.
• La sémantique CSP est dénotationnelle, généralement en termes de traces.
• La sémantique CCS / -calculus est opérationnelle, généralement en termes de systèmes de transition étiquetés.$\pi$

Bien sûr, depuis la sémantique originale, plus de modèles ont été développés. Mais il est certainement intéressant que les chercheurs originaux aient commencé avec différentes approches sémantiques.

Répondre (au moins) à la partie de votre question concernant les raisons pour lesquelles la recherche a divergé au lieu de converger.

N'étant pas un expert des algèbres de processus, je me demandais une fois exactement la même chose: pourquoi y a-t-il tant de théories? J'ai été pointé vers une enquête de Parrow: Expressiveness of Process Algebras, 2008 . Je pense que c'est très bien écrit et même un novice pourrait le comprendre.

Parrow étudie l'expressivité des algèbres et répond à la question. En bref, différentes théories sont différents types d'outils pour résoudre une tâche énorme.