Cálculo de procesos

Familia de enfoques para modelar sistemas concurrentes

En ciencias de la computación , 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 descripciones de procesos, y permiten el razonamiento formal sobre equivalencias entre procesos (por ejemplo, usando 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 .

Funciones 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 primitivas y operadores para combinar esas primitivas.
• 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 parte de 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
• recursividad o replicación de procesos

Composición paralela

La composición paralela de dos procesos y , generalmente escrita , es la primitiva clave que distingue los cálculos de procesos de los modelos secuenciales de computación. Composición paralela permite el cálculo en y para proceder simultáneamente e independientemente. Pero también permite la interacción, que es la sincronización y el flujo de información de a (o viceversa) en un canal compartido por ambos. Fundamentalmente, un agente o proceso se puede conectar 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 síncrono, el agente que envía un mensaje espera hasta que otro agente haya recibido el mensaje. Los canales asíncronos no requieren tal sincronización. En algunos procesos de cálculo (en particular, el cálculo π ), los propios canales pueden enviarse en mensajes a través de (otros) canales, lo que permite que cambie la topología de las interconexiones de procesos. Algunos cálculos de proceso 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) un flujo de información dirigido . Es decir, la entrada y la salida se pueden distinguir como primitivas de interacción dual. Los cálculos de proceso que hacen tales distinciones definen típicamente un operador de entrada ( p . Ej. ) Y un operador de salida ( p . Ej. ), Los cuales nombran un punto de interacción (aquí ) que se usa 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, fluirá del proceso de salida al proceso 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 vinculadas actuarán como marcadores de posición para ser sustituidos por datos, cuando llegue. En , juega 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 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, podría ser conveniente especificar algoritmos como: primero reciba algunos datos y luego envíe esos datos${\displaystyle {\mathit {x}}}$${\displaystyle {\mathit {y}}}$ . La composición secuencial se puede utilizar para tales fines. Es bien conocido por otros modelos de cálculo. En los cálculos de procesos, el operador de secuenciación suele estar integrado con la entrada o la salida, o con ambas. Por ejemplo, el proceso esperará una entrada . Solo cuando se haya producido esta entrada se activará el proceso , sustituyendo los datos recibidos 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 lo largo del canal . Dualmente, 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 que el mensaje ha sido enviado, se convierte en el proceso , mientras que se convierte en el proceso , que es con el marcador 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 variar como continuación de la operación de salida influye sustancialmente en las propiedades del cálculo.${\displaystyle {\mathit {P}}}$

Ocultar

Los procesos no limitan el número de conexiones que se pueden realizar 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 composicionales, la capacidad de restringir la interferencia es crucial. Las operaciones de ocultación permiten controlar las conexiones realizadas entre los puntos de interacción al componer agentes en paralelo. La ocultación se puede denotar de diversas formas. Por ejemplo, en el cálculo π, la ocultación 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\}}$

Recurrencia y replicación

Las operaciones presentadas hasta ahora describen solo una interacción finita y, en consecuencia, son insuficientes para la computabilidad completa, que incluye el comportamiento no terminante. La recursividad y la replicación son operaciones que permiten descripciones finitas de comportamiento infinito. La recursividad 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

Cálculos de procesos generalmente también incluyen un proceso nulo (denotado diversamente 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 continua y discreta

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 una 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 se pueden codificar entre sí, apoya la tesis de Church-Turing . Otra característica compartida es menos comentada: todos se entienden más fácilmente como modelos de secuenciacálculo. La posterior consolidación de la 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. De esta línea de investigación surgieron modelos de concurrencia como el cálculo de procesos, las redes de Petri en 1962 y el modelo del actor en 1973.

La investigación sobre los cálculos de proceso comenzó en serio con Robin Milner 's trabajo seminal en el cálculo de sistemas comunicantes (CCS) durante el período de 1973 a 1980. CAR Hoare ' s Procesos de Comunicación secuencial (CSP) apareció por primera vez en 1978, y fue desarrollado posteriormente en un cálculo de proceso completo durante principios de la década de 1980. Hubo mucha fertilización cruzada de ideas entre CCS y CSP a medida que se desarrollaron. En 1982, Jan Bergstra y Jan Willem Klop comenzaron a trabajar en lo que llegó a conocerse como Á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 proceso: la mayoría de los otros cálculos de proceso 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 se ajustan al paradigma aquí esbozado. 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.

• Desarrollar nuevos cálculos de procesos para un mejor modelado de fenómenos computacionales.
• Encontrar subcálculos de buen comportamiento de un cálculo de proceso dado. Esto es valioso porque (1) la mayoría de los cálculos son bastante disparatados 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. Por el contrario, utilizan solo procesos que tienen una forma muy restringida. La restricción de la forma de los procesos se estudia principalmente mediante sistemas de tipos .
• Lógicas para procesos que permiten razonar sobre propiedades (esencialmente) arbitrarias de procesos, siguiendo las ideas de la lógica de Hoare .
• Teoría del comportamiento: ¿que significa que dos procesos sean iguales? ¿Cómo podemos decidir si dos procesos son diferentes o no? ¿Podemos encontrar representantes para clases de equivalencia de procesos? Generalmente, los procesos se consideran iguales si ningún contexto, es decir, otros procesos que se ejecutan en paralelo, pueden detectar una diferencia. Desafortunadamente, precisar esta intuición es sutil y en su mayoría produce caracterizaciones de igualdad difíciles de manejar (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 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 del cálculo de modelado de cálculos que la que ofrece la tesis de Church-Turing . Una forma de hacer esto es considerar codificaciones entre dos formalismos y ver qué propiedades pueden preservar potencialmente las codificaciones. Cuantas más propiedades puedan conservarse, más expresivo se dice que es 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 elcálculo ambiental . ^{[ cita requerida ]}
• Utilización del cálculo de procesos para modelar sistemas biológicos (cálculo π estocástico, BioAmbientes, Aglutinantes Beta, BioPEPA, cálculo Brane). Algunos piensan que la composicionalidad que ofrecen las herramientas de la 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 que incluyen:

• CADP
• Banco de trabajo de simultaneidad
• Conjunto de herramientas mCRL2

Relación con otros modelos de concurrencia

El monoide de historia es el objeto libre que genéricamente puede representar las historias de los procesos comunicativos individuales. Un cálculo de proceso es entonces un lenguaje formal impuesto a un monoide de historia 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 proceso de cálculo es para un monoide de historia lo que un lenguaje formal es para 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 de comunicación es una de las características que distinguen los cálculos de procesos de otros modelos de concurrencia , como las redes de Petri y el modelo de actor (ver Modelo de actor y cálculos de proceso ). Una de las motivaciones fundamentales para incluir canales en los cálculos de procesos fue habilitar ciertas técnicas algebraicas, facilitando así el razonamiento algebraico sobre los procesos.

Ver también

• Sonda estocástica
• Lenguaje de proceso temporal

Referencias

1. Baeten, JCM (2004). "Una breve historia del álgebra de procesos" (PDF) . Rapport CSR 04-02 . Vakgroep Informatica, Technische Universiteit Eindhoven.
2. Pierce, Benjamin (21 de diciembre de 1996). "Cálculos fundamentales para lenguajes de programación". El Manual de Ingeniería y Ciencias de la Computación . Prensa CRC. págs. 2190–2207. ISBN 0-8493-2909-4.
3. Baeten, JCM; Bravetti, M. (agosto de 2005). "Un proceso de álgebra genérico" . Cálculos de procesos algebraicos: los primeros veinticinco años y más allá (Serie de notas BRICS 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 "Álgebra de procesos con sincronización: tiempo real y tiempo discreto". CiteSeerX 10.1.1.42.729 . 
5. Sangiorgi, Davide (1993). Gaudel, M.-C .; Jouannaud, J. -P. (eds.). "De π-cálculo a π-cálculo de orden superior - y viceversa" . TAPSOFT'93: Teoría y Práctica del Desarrollo de Software . Apuntes de conferencias en informática. Springer Berlín Heidelberg. 668 : 151-166. doi : 10.1007 / 3-540-56610-4_62 . ISBN 9783540475989.
6. Mazurkiewicz, Antoni (1995). "Introducción a la teoría de la traza" (PostScript) . En Diekert, V .; Rozenberg, G. (eds.). El libro de las huellas . Singapur: World Scientific. págs. 3-41. ISBN  981-02-2058-8.

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 móviles y de comunicación: Pi-Calculus , Springer Verlag, ISBN 0-521-65869-1 . 
• Andrew Mironov : Teoría de procesos
• 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 Analyze von Informatiksystemen . Theoretische Grundlagen der Informatik (en alemán). Parte 2. Universidad de Hamburgo . FGI2. Archivado (PDF) desde el original el 9 de julio de 2019 . Consultado el 13 de julio de 2019 .