El álgebra de procesos de comunicación (ACP) es un enfoque algebraico para razonar sobre sistemas concurrentes . Es un miembro de la familia de teorías matemáticas de concurrencia conocidas como álgebras de procesos o cálculos de procesos . El ACP fue desarrollado inicialmente por Jan Bergstra y Jan Willem Klop en 1982, [1] como parte de un esfuerzo por investigar las soluciones de ecuaciones recursivas no vigiladas. Más que los otros cálculos de procesos seminales ( CCS y CSP ), el desarrollo de ACP se centró en el álgebra de procesos y buscó crear un sistema axiomático abstracto y generalizado para procesos, [2]y de hecho, el término álgebra de procesos se acuñó durante la investigación que condujo a ACP.
Descripción informal
ACP es fundamentalmente un álgebra, en el sentido de álgebra universal . Esta álgebra es una forma de describir sistemas en términos de expresiones de procesos algebraicos que definen composiciones de otros procesos o de ciertos elementos primitivos.
Primitivos
ACP utiliza acciones atómicas instantáneas () como sus primitivas. Algunas acciones tienen un significado especial, como la acción, que representa un punto muerto o estancamiento, y la acción, que representa una acción silenciosa (acciones abstractas que no tienen una identidad específica).
Operadores algebraicos
Las acciones se pueden combinar para formar procesos utilizando una variedad de operadores. Estos operadores pueden clasificarse a grandes rasgos como que proporcionan un álgebra , concurrencia y comunicación de procesos básicos .
- Elección y secuenciación : los operadores algebraicos más fundamentales son el operador alternativo (), que permite elegir entre acciones y el operador de secuenciación (), que especifica un orden de acciones. Entonces, por ejemplo, el proceso
- primero elige realizar una o , y luego realiza la acción . ¿Cómo la elección entre y se hace no importa y se deja sin especificar. Tenga en cuenta que la composición alternativa es conmutativa, pero la composición secuencial no lo es (porque el tiempo fluye hacia adelante).
- Concurrencia : para permitir la descripción de la concurrencia, ACP proporciona los operadores de combinación y combinación a la izquierda . El operador de combinación,, representa la composición paralela de dos procesos, cuyas acciones individuales están intercaladas. El operador de combinación a la izquierda,, es un operador auxiliar con semántica similar a la fusión, pero con el compromiso de elegir siempre su paso inicial del proceso de la izquierda. Como ejemplo, el proceso
- puede realizar las acciones en cualquiera de las secuencias . Por otro lado, el proceso
- solo puede realizar las secuencias ya que los operadores de combinación a la izquierda aseguran que la acción ocurre primero.
- Comunicación : la interacción (o comunicación) entre procesos se representa mediante el operador de comunicaciones binarias,. Por ejemplo, las acciones y podría interpretarse como la lectura y escritura de un elemento de datos , respectivamente. Entonces el proceso
- comunicará el valor del proceso del componente derecho al proceso del componente izquierdo ( es decir, el identificador está ligado al valor , e instancias gratuitas de en el proceso tomar ese valor), y luego comportarse como la fusión de y .
- Abstracción : el operador de abstracción,, es una forma de "ocultar" ciertas acciones y tratarlas como eventos internos de los sistemas que se están modelando. Las acciones abstraídas se convierten en la acción de paso silencioso. En algunos casos, estos pasos silenciosos también se pueden eliminar de la expresión del proceso como parte del proceso de abstracción. Por ejemplo,
- que, en este caso, se puede reducir a
- desde el evento ya no es observable y no tiene efectos observables.
Definicion formal
ACP adopta fundamentalmente un enfoque axiomático y algebraico para la definición formal de sus diversos operadores. Los axiomas presentados a continuación comprenden el sistema axiomático completo para ACP (ACP con abstracción).
Álgebra básica de procesos
Usando los operadores alternativos y de composición secuencial, ACP define un álgebra de proceso básico que satisface los axiomas [3]
Punto muerto
Más allá del álgebra básica, dos axiomas adicionales definen las relaciones entre los operadores alternativos y de secuenciación, y la acción de interbloqueo ,
Simultaneidad e interacción
Los axiomas asociados con los operadores de combinación, combinación a la izquierda y comunicación son [3]
Cuando el operador de comunicaciones se aplica solo a acciones, en lugar de procesos, se interpreta como una función binaria de acciones a acciones, . La definición de esta función define las posibles interacciones entre procesos: los pares de acciones que no constituyen interacciones se asignan a la acción de interbloqueo,, mientras que los pares de interacciones permitidas se asignan a las acciones individuales correspondientes que representan la ocurrencia de una interacción. Por ejemplo, la función de comunicaciones podría especificar que
lo que indica que una interacción exitosa se reducirá a la acción . ACP también incluye un operador de encapsulación, para algunos , que se utiliza para convertir intentos de comunicación fallidos (es decir, elementos de que no se han reducido a través de la función de comunicación) a la acción de interbloqueo. Los axiomas asociados con la función de comunicaciones y el operador de encapsulación son [3]
Abstracción
Los axiomas asociados con el operador de abstracción son [3]
Tenga en cuenta que la acción a en la lista anterior puede tomar el valor δ (pero, por supuesto, δ no puede pertenecer al conjunto de abstracción I ).
Formalismos relacionados
ACP ha servido como base o inspiración para varios otros formalismos que se pueden utilizar para describir y analizar sistemas concurrentes, que incluyen:
Referencias
- ^ JCM Baeten, Una breve historia del álgebra de procesos , Rapport CSR 04-02, Vakgroep Informatica, Technische Universiteit Eindhoven, 2004
- ^ Bas Luttik, Qué es algebraico en la teoría de procesos , Cálculos de procesos algebraicos: Los primeros veinticinco años y más allá Archivado 2005-12-04 en Wayback Machine , Bertinoro, Italia, 1 de agosto de 2005
- ^ a b c d J.A. Bergstra y JW Klop, ACP τ : A Universal Axiom System for Process Specification , CWI Quarterly 15, págs. 3-23, 1987
- ^ PJL Cuijpers y MA Reniers, Álgebra de procesos híbridos , Informe técnico, Departamento de Matemáticas e Informática, Universidad Técnica de Eindhoven, 2003