Similitudes y diferencias en álgebras de procesos principales

21

Que yo sepa, hay tres álgebras de procesos principales que han inspirado una amplia gama de investigaciones sobre modelos formales de concurrencia. Estos son:

  • CCS y cálculo ambos por Robin Milnerπ
  • CSP por Tony Hoare y
  • ACP por Jan Bergstra y Jan Willem Klop

Los tres parecen tener hasta el día de hoy un seguimiento bastante activo y se han realizado grandes cantidades de investigación sobre ellos.

¿Cuáles son las similitudes y diferencias clave de estos enfoques? ¿Por qué la investigación en álgebra de procesos divergió en lugar de converger, en el sentido de que no existe un modelo universal único para unificar el campo?

Dave Clarke
fuente
2
Una respuesta parcial parcialmente hereje: 3 enfoques permiten 3 veces más tesis.
Kai

Respuestas:

8

Solo conozco CSP y CCS / pi-calculus (no ACP).

CSP fue motivado por procesos de programación imperativos que se comunicaban a través de mensajes. Hoare luego trató de extraer un simple cálculo de él. CCS, por otro lado, fue un esfuerzo para crear un cálculo fundamental como el cálculo lambda. Dados sus puntos de partida originales y su forma final, diría que han convergido en lugar de divergir.

Lo que encuentro común entre CSP y CCS es que ambos se basan en la noción de "proceso" (y, con eso, me refiero a una noción abstracta de eventos organizados en el tiempo). La principal diferencia entre ellos es que CSP tiene dos formas de elección (interna / externa o no determinista / determinista). En CCS las dos ideas se fusionan en una. Creo que es una diferencia irreconciliable.

La distinción entre elección interna y externa permite a CSP tener una semántica en términos de trazas lineales. La semántica de CCS, por otro lado, debe basarse en árboles.

Creo que el plan actual de Hoare para "Teorías unificadoras" es poner ambas en un solo marco. ¡Tenemos que esperar y ver qué se le ocurre!

Uday Reddy
fuente
7

Otra respuesta parcial.

El enfoque de la semántica adoptado por las diversas comunidades difería, al menos originalmente.

  • La semántica ACP es axiomática / algebraica.
  • La semántica de CSP es denotacional, generalmente en términos de trazas.
  • π

Por supuesto, desde la semántica original, se han desarrollado más modelos. Pero es ciertamente interesante que los investigadores originales comenzaron con diferentes enfoques semánticos.

Dave Clarke
fuente
6

Respondiendo (al menos) la parte de su pregunta sobre por qué la investigación ha divergido en lugar de converger.

Al no ser un experto en álgebras de procesos, una vez me preguntaba exactamente lo mismo: ¿por qué hay tantas teorías? Parrow me señaló una encuesta : Expresividad de álgebras de procesos, 2008 . Creo que está muy bien escrito e incluso un principiante podría entenderlo.

Parrow investiga la expresividad de las álgebras y responde la pregunta. En resumen, las diferentes teorías son diferentes tipos de herramientas para resolver una tarea enorme.

Juho
fuente