Cálculo de procesos

Familia de enfoques para modelar sistemas concurrentes

En informática , los cálculos de procesos (o álgebras de procesos ) son una familia diversa de enfoques relacionados para modelar formalmente sistemas concurrentes . Los cálculos de procesos proporcionan una herramienta para la descripción de alto nivel de interacciones, comunicaciones y sincronizaciones entre una colección de agentes o procesos independientes. También proporcionan leyes algebraicas que permiten manipular y analizar las descripciones de procesos, y permiten el razonamiento formal sobre equivalencias entre procesos (por ejemplo, utilizando bisimulación ). Los principales ejemplos de cálculos de procesos incluyen CSP , CCS , ACP y LOTOS . ^[1] Las adiciones más recientes a la familia incluyen el cálculo π , el cálculo ambiental , PEPA , el cálculo de fusión y el cálculo de unión .

Características esenciales

Si bien la variedad de cálculos de procesos existentes es muy grande (incluidas variantes que incorporan comportamiento estocástico , información de tiempo y especializaciones para estudiar interacciones moleculares), hay varias características que todos los cálculos de procesos tienen en común: ^[2]

• Representar interacciones entre procesos independientes como comunicación ( paso de mensajes ), en lugar de como modificación de variables compartidas.
• Describir procesos y sistemas utilizando una pequeña colección de primitivos y operadores para combinar esos primitivos.
• Definición de leyes algebraicas para los operadores de proceso, que permiten manipular expresiones de proceso mediante razonamiento ecuacional .

Matemáticas de procesos

Para definir un cálculo de procesos , se comienza con un conjunto de nombres (o canales ) cuyo propósito es proporcionar medios de comunicación. En muchas implementaciones, los canales tienen una estructura interna rica para mejorar la eficiencia, pero esto se abstrae en la mayoría de los modelos teóricos. Además de los nombres, se necesita un medio para formar nuevos procesos a partir de los antiguos. Los operadores básicos, siempre presentes de una forma u otra, permiten: ^[3]

• composición paralela de procesos
• Especificación de qué canales utilizar para enviar y recibir datos
• secuencialización de interacciones
• ocultación de puntos de interacción
• recursión o replicación de procesos

Composición paralela

La composición paralela de dos procesos y , que se escribe normalmente , es la primitiva clave que distingue los cálculos de procesos de los modelos secuenciales de computación. La composición paralela permite que la computación en y se realice de manera simultánea e independiente, pero también permite la interacción, es decir, la sincronización y el flujo de información de a (o viceversa) en un canal compartido por ambos. Fundamentalmente, un agente o proceso puede estar conectado a más de un canal a la vez. ${\displaystyle {\mathit {P}}}$ ${\displaystyle {\mathit {Q}}}$ ${\displaystyle P\vert Q}$ ${\displaystyle {\mathit {P}}}$ ${\displaystyle {\mathit {Q}}}$ ${\displaystyle {\mathit {P}}}$ ${\displaystyle {\mathit {Q}}}$

Los canales pueden ser sincrónicos o asincrónicos. En el caso de un canal sincrónico, el agente que envía un mensaje espera hasta que otro agente haya recibido el mensaje. Los canales asincrónicos no requieren ninguna sincronización de este tipo. En algunos cálculos de procesos (en particular, el cálculo π ), los propios canales pueden enviarse en mensajes a través de (otros) canales, lo que permite cambiar la topología de las interconexiones de procesos. Algunos cálculos de procesos también permiten la creación de canales durante la ejecución de un cálculo.

Comunicación

La interacción puede ser (pero no siempre lo es) un flujo de información dirigido . Es decir, la entrada y la salida pueden distinguirse como primitivas de interacción dual. Los cálculos de proceso que hacen tales distinciones suelen definir un operador de entrada ( eg ) y un operador de salida ( eg ), los cuales nombran un punto de interacción (here ) que se utiliza para sincronizar con una primitiva de interacción dual. ${\displaystyle x(v)}$ ${\displaystyle x\langle y\rangle }$ ${\displaystyle {\mathit {x}}}$

Si se intercambia información, esta fluirá desde el proceso de salida al de entrada. La primitiva de salida especificará los datos que se enviarán. En , estos datos son . De manera similar, si una entrada espera recibir datos, una o más variables ligadas actuarán como marcadores de posición para ser reemplazados por datos, cuando lleguen. En , desempeña ese papel. La elección del tipo de datos que se pueden intercambiar en una interacción es una de las características clave que distingue a los diferentes cálculos de procesos. ${\displaystyle x\langle y\rangle }$ ${\displaystyle y}$ ${\displaystyle x(v)}$ ${\displaystyle v}$

Composición secuencial

A veces, las interacciones deben ordenarse temporalmente. Por ejemplo, puede ser deseable especificar algoritmos como: primero recibir algunos datos en y luego enviar esos datos en ${\displaystyle {\mathit {x}}}$ ${\displaystyle {\mathit {y}}}$ . La composición secuencial se puede utilizar para tales fines. Es bien conocida por otros modelos de computación. En los cálculos de procesos, el operador de secuenciación generalmente se integra con la entrada o la salida, o ambas. Por ejemplo, el proceso esperará una entrada en . Solo cuando se haya producido esta entrada , se activará el proceso, y los datos recibidos a través de se sustituirán por el identificador . ${\displaystyle x(v)\cdot P}$ ${\displaystyle {\mathit {x}}}$ ${\displaystyle {\mathit {P}}}$ ${\displaystyle {\mathit {x}}}$ ${\displaystyle {\mathit {v}}}$

Semántica de reducción

La regla de reducción operativa clave, que contiene la esencia computacional de los cálculos de procesos, se puede dar únicamente en términos de composición paralela, secuencialización, entrada y salida. Los detalles de esta reducción varían entre los cálculos, pero la esencia sigue siendo aproximadamente la misma. La regla de reducción es:

${\displaystyle x\langle y\rangle \cdot P\;\vert \;x(v)\cdot Q\longrightarrow P\;\vert \;Q[^{y}\!/\!_{v}]}$

La interpretación de esta regla de reducción es:

1. El proceso envía un mensaje, aquí , a través del canal . En ambos casos, el proceso recibe ese mensaje en el canal . ${\displaystyle x\langle y\rangle \cdot P}$ ${\displaystyle {\mathit {y}}}$ ${\displaystyle {\mathit {x}}}$ ${\displaystyle x(v)\cdot Q}$ ${\displaystyle {\mathit {x}}}$
2. Una vez enviado el mensaje, se convierte en el proceso , mientras que se convierte en el proceso , que es con el marcador de posición sustituido por , los datos recibidos en . ${\displaystyle x\langle y\rangle \cdot P}$ ${\displaystyle {\mathit {P}}}$ ${\displaystyle x(v)\cdot Q}$ ${\displaystyle Q[^{y}\!/\!_{v}]}$ ${\displaystyle {\mathit {Q}}}$ ${\displaystyle {\mathit {v}}}$ ${\displaystyle {\mathit {y}}}$ ${\displaystyle {\mathit {x}}}$

La clase de procesos que se permite que se extienda como continuación de la operación de salida influye sustancialmente en las propiedades del cálculo. ${\displaystyle {\mathit {P}}}$

Ocultación

Los procesos no limitan el número de conexiones que se pueden hacer en un punto de interacción dado. Pero los puntos de interacción permiten la interferencia (es decir, la interacción). Para la síntesis de sistemas compactos, mínimos y compositivos, la capacidad de restringir la interferencia es crucial. Las operaciones de ocultamiento permiten controlar las conexiones realizadas entre los puntos de interacción cuando se componen agentes en paralelo. El ocultamiento se puede denotar de diversas formas. Por ejemplo, en el cálculo π el ocultamiento de un nombre en se puede expresar como , mientras que en CSP podría escribirse como . ${\displaystyle {\mathit {x}}}$ ${\displaystyle {\mathit {P}}}$ ${\displaystyle (\nu \;x)P}$ ${\displaystyle P\setminus \{x\}}$

Recursión y replicación

Las operaciones presentadas hasta ahora describen únicamente interacciones finitas y, en consecuencia, son insuficientes para la computabilidad completa, que incluye el comportamiento no terminante. La recursión y la replicación son operaciones que permiten descripciones finitas de un comportamiento infinito. La recursión es bien conocida en el mundo secuencial. La replicación puede entenderse como la abreviatura de la composición paralela de un número infinito numerable de procesos: ${\displaystyle !P}$ ${\displaystyle {\mathit {P}}}$

${\displaystyle !P=P\mid !P}$

Proceso nulo

Los cálculos de procesos generalmente también incluyen un proceso nulo (denotado de diversas formas como , , , o algún otro símbolo apropiado) que no tiene puntos de interacción. Es completamente inactivo y su único propósito es actuar como el ancla inductiva sobre la cual se pueden generar procesos más interesantes. ${\displaystyle {\mathit {nil}}}$ ${\displaystyle 0}$ ${\displaystyle {\mathit {STOP}}}$ ${\displaystyle \delta }$

Álgebra de procesos discretos y continuos

El álgebra de procesos se ha estudiado para tiempo discreto y tiempo continuo (tiempo real o tiempo denso). ^[4]

Historia

En la primera mitad del siglo XX se propusieron varios formalismos para capturar el concepto informal de función computable , siendo las funciones μ-recursivas , las máquinas de Turing y el cálculo lambda posiblemente los ejemplos más conocidos en la actualidad. El hecho sorprendente de que sean esencialmente equivalentes, en el sentido de que todos son codificables entre sí, apoya la tesis de Church-Turing . Otra característica compartida es menos comentada: todos ellos se entienden más fácilmente como modelos de computación secuencial . La posterior consolidación de la ciencia informática requirió una formulación más sutil de la noción de computación, en particular representaciones explícitas de concurrencia y comunicación. Modelos de concurrencia como los cálculos de procesos, las redes de Petri en 1962 y el modelo de actor en 1973 surgieron de esta línea de investigación.

La investigación sobre los cálculos de procesos comenzó en serio con el trabajo seminal de Robin Milner sobre el Cálculo de Sistemas de Comunicación (CCS) durante el período de 1973 a 1980. Los Procesos Secuenciales de Comunicación (CSP) de CAR Hoare aparecieron por primera vez en 1978, y posteriormente se desarrollaron hasta convertirse en un cálculo de procesos completo a principios de la década de 1980. Hubo mucha fertilización cruzada de ideas entre CCS y CSP a medida que se desarrollaban. En 1982, Jan Bergstra y Jan Willem Klop comenzaron a trabajar en lo que llegó a conocerse como el Álgebra de Procesos de Comunicación (ACP), e introdujeron el término álgebra de procesos para describir su trabajo. ^[1] CCS, CSP y ACP constituyen las tres ramas principales de la familia de cálculos de procesos: la mayoría de los otros cálculos de procesos pueden rastrear sus raíces en uno de estos tres cálculos.

Investigación actual

Se han estudiado varios cálculos de procesos y no todos ellos se ajustan al paradigma esbozado aquí. El ejemplo más destacado puede ser el cálculo ambiental . Esto es de esperar, ya que los cálculos de procesos son un campo de estudio activo. Actualmente, la investigación sobre cálculos de procesos se centra en los siguientes problemas.

• Desarrollo de nuevos cálculos de procesos para un mejor modelado de fenómenos computacionales.
• Encontrar subcálculos que se comporten bien en un cálculo de procesos dado. Esto es valioso porque (1) la mayoría de los cálculos son bastante alocados en el sentido de que son bastante generales y no se puede decir mucho sobre procesos arbitrarios; y (2) las aplicaciones computacionales rara vez agotan la totalidad de un cálculo. En cambio, utilizan solo procesos que están muy restringidos en su forma. La restricción de la forma de los procesos se estudia principalmente por medio de sistemas de tipos .
• Lógicas para procesos que permiten razonar sobre propiedades (esencialmente) arbitrarias de los procesos, siguiendo las ideas de la lógica de Hoare .
• Teoría del comportamiento: ¿qué significa que dos procesos sean iguales? ¿Cómo podemos decidir si dos procesos son diferentes o no? ¿Podemos encontrar representantes de clases de equivalencia de procesos? En general, se considera que los procesos son iguales si ningún contexto, es decir, otros procesos que se ejecutan en paralelo, puede detectar una diferencia. Desafortunadamente, hacer que esta intuición sea precisa es sutil y, en la mayoría de los casos, produce caracterizaciones difíciles de manejar de la igualdad (que, en la mayoría de los casos, también deben ser indecidibles, como consecuencia del problema de la detención ). Las bisimulaciones son una herramienta técnica que ayuda a razonar sobre las equivalencias de procesos.
• Expresividad de los cálculos. La experiencia en programación muestra que ciertos problemas son más fáciles de resolver en algunos lenguajes que en otros. Este fenómeno requiere una caracterización más precisa de la expresividad de la computación de modelado de cálculos que la que ofrece la tesis de Church-Turing . Una forma de hacerlo es considerar las codificaciones entre dos formalismos y ver qué propiedades pueden preservar potencialmente las codificaciones. Cuantas más propiedades se puedan preservar, se dice que es más expresivo el objetivo de la codificación. Para los cálculos de proceso, los resultados celebrados son que el π-cálculo sincrónico es más expresivo que su variante asincrónica, tiene el mismo poder expresivo que el π-cálculo de orden superior ^[5] , pero es menor que el cálculo ambiental . ^{[ cita requerida ]}
• Uso del cálculo de procesos para modelar sistemas biológicos (cálculo π estocástico, BioAmbients, Beta Binders, BioPEPA, cálculo de branas). Algunos piensan que la composicionalidad que ofrecen las herramientas de teoría de procesos puede ayudar a los biólogos a organizar su conocimiento de manera más formal.

Implementaciones de software

Las ideas detrás del álgebra de procesos han dado lugar a varias herramientas, entre ellas:

• CAD
• Banco de trabajo de concurrencia
• Conjunto de herramientas mCRL2

Relación con otros modelos de concurrencia

El monoide histórico es el objeto libre que es capaz de representar genéricamente las historias de procesos comunicativos individuales. Un cálculo de procesos es entonces un lenguaje formal impuesto a un monoide histórico de manera consistente. ^[6] Es decir, un monoide histórico solo puede registrar una secuencia de eventos, con sincronización, pero no especifica las transiciones de estado permitidas. Por lo tanto, un cálculo de procesos es a un monoide histórico lo que un lenguaje formal es a un monoide libre (un lenguaje formal es un subconjunto del conjunto de todas las posibles cadenas de longitud finita de un alfabeto generado por la estrella de Kleene ).

El uso de canales para la comunicación es una de las características que distinguen a los cálculos de procesos de otros modelos de concurrencia , como las redes de Petri y el modelo de actores (véase Modelo de actores y cálculos de procesos ). Una de las motivaciones fundamentales para incluir canales en los cálculos de procesos fue permitir ciertas técnicas algebraicas, facilitando así el razonamiento algebraico sobre los procesos.

Véase también

• Comunicar procesos secuenciales
• Verificación profesional
• Sonda estocástica
• Probador de tamarinos
• Lenguaje de proceso temporal
• cálculo π

Referencias

1. Baeten, JCM (2004). "Una breve historia del álgebra de procesos" (PDF) . Informe RSC 04-02 . Vakgroep Informatica, Universidad Técnica de Eindhoven.
2. Pierce, Benjamin (21 de diciembre de 1996). "Cálculos básicos para lenguajes de programación". Manual de ingeniería y ciencias de la computación . CRC Press. págs. 2190–2207. ISBN 0-8493-2909-4.
3. Baeten, JCM; Bravetti, M. (agosto de 2005). "A Generic Process Algebra". Cálculos de procesos algebraicos: los primeros veinticinco años y más allá (BRICS Notes Series NS-05-3) . Bertinoro, Forlì, Italia: BRICS, Departamento de Ciencias de la Computación, Universidad de Aarhus . Consultado el 29 de diciembre de 2007 .
4. Baeten, JCM; Middelburg, CA (2000). "Álgebra de procesos con tiempo: tiempo real y tiempo discreto": 627–684. CiteSeerX 10.1.1.42.729 .  {{cite journal}}: Requiere citar revista |journal=( ayuda )
5. Sangiorgi, Davide (1993). "Del cálculo π al cálculo π de orden superior —y viceversa". En Gaudel, M. -C.; Jouannaud, J. -P. (eds.). TAPSOFT'93: Teoría y práctica del desarrollo de software . Apuntes de clase en informática. Vol. 668. Springer Berlin Heidelberg. págs. 151–166. doi : 10.1007/3-540-56610-4_62 . ISBN. 9783540475989.
6. Mazurkiewicz, Antoni (1995). "Introducción a la teoría de las trazas". En Diekert, V.; Rozenberg, G. (eds.). El libro de las trazas . Singapur: World Scientific. págs. 3–41. ISBN 981-02-2058-8Archivado desde el original (PostScript) el 13 de junio de 2011. Consultado el 29 de abril de 2009 .

Lectura adicional

• Matthew Hennessy : Teoría algebraica de procesos , The MIT Press , ISBN 0-262-08171-7 . 
• CAR Hoare : Comunicación de procesos secuenciales , Prentice Hall , ISBN 0-13-153289-8 .  
  • Este libro ha sido actualizado por Jim Davies en el Laboratorio de Computación de la Universidad de Oxford y la nueva edición está disponible para descargar como archivo PDF en el sitio web Using CSP .
• Robin Milner : Un cálculo de sistemas de comunicación , Springer Verlag, ISBN 0-387-10235-3 . 
• Robin Milner : Sistemas comunicantes y móviles: el cálculo Pi , Springer Verlag, ISBN 0-521-65869-1 . 
• Valk, Rüdiger ; Moldt, Daniel; Köhler-Bußmeier, Michael, eds. (2011). "Capítulo 5: Prozessalgebra - Parallele und kommunizierende Prozesse" (PDF) . Formale Grundlagen der Informatik II: Modellierung und Analyse von Informatiksystemen (en alemán). vol. Parte 2. Universidad de Hamburgo . FGI2. Archivado (PDF) desde el original el 9 de julio de 2019 . Consultado el 13 de julio de 2019 . {{cite book}}: |work=ignorado ( ayuda )