Cálculo de procesos

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 herramientas para descripciones de alto nivel de interacciones, comunicaciones y sincronizaciones entre un conjunto de procesos independientes. Proporcionan leyes algebraicas que permiten manipular y analizar las descripciones de procesos, y también permiten el razonamiento formal sobre equivalencias entre procesos (por ejemplo, usando bisimulación ). Ejemplos destacados de cálculos de procesos incluyen CSP , CCS , ACP y LOTOS . ^{[ 1 ]} 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

Aunque 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 las interacciones entre procesos independientes como comunicación ( paso de mensajes ), en lugar de como modificación de variables compartidas.
Describir procesos y sistemas utilizando un pequeño conjunto de primitivas y operadores para combinar dichas primitivas.
Definir leyes algebraicas para los operadores de proceso, que permitan manipular expresiones de proceso utilizando razonamiento ecuacional .

Matemáticas de los 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 rica estructura interna 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
secuenciación de interacciones
ocultamiento de puntos de interacción
recursión o replicación de procesos

Composición paralela

Composición paralela de dos procesos ${\mathit {P}}$ y ${\mathit {Q}}$ , generalmente escrito $P\vert Q$ , es la primitiva clave que distingue los cálculos de proceso de los modelos secuenciales de computación. La composición paralela permite la computación en ${\mathit {P}}$ y ${\mathit {Q}}$ para proceder simultáneamente e independientemente. Pero también permite la interacción, es decir, la sincronización y el flujo de información desde ${\mathit {P}}$ a ${\mathit {Q}}$ (o viceversa) en un canal compartido por ambos. Fundamentalmente, un proceso puede estar conectado a más de un canal a la vez.

Los canales pueden ser síncronos o asíncronos. En un canal síncrono, el proceso que envía un mensaje espera hasta que otro proceso lo reciba. Los canales asíncronos no requieren sincronización. En algunos cálculos de procesos (en particular, el cálculo π ), los propios canales pueden enviarse mediante mensajes a través de otros canales, lo que permite modificar la topología de las interconexiones entre procesos. Algunos cálculos de procesos también permiten crear canales durante la ejecución de un cálculo.

Comunicación

La interacción puede ser (pero no siempre lo es) un flujo dirigido de información. Es decir, la entrada y la salida pueden distinguirse como primitivas de interacción duales. Los cálculos de procesos que hacen tales distinciones suelen definir un operador de entrada ( p. ej. $x(v)$ ) y un operador de salida ( por ejemplo $x\langle y\rangle$ ), ambos nombran un punto de interacción (aquí ${\mathit {x}}$ ) que se utiliza para sincronizarse con una primitiva de interacción dual.

Si se intercambia información, fluirá del proceso de salida al de entrada. La primitiva de salida especificará los datos que se enviarán. $x\langle y\rangle$ , estos datos son $y$ De manera similar, si una entrada espera recibir datos, una o más variables vinculadas actuarán como marcadores de posición que serán sustituidos por los datos cuando lleguen. $x(v)$ , $v$ 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 los diferentes cálculos de procesos.

Composición secuencial

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

semántica de reducción

La regla de reducción operacional clave, que contiene la esencia computacional de los cálculos de procesos, puede expresarse únicamente en términos de composición paralela, secuenciación, entrada y salida. Los detalles de esta reducción varían entre los distintos cálculos, pero la esencia permanece prácticamente invariable. La regla de reducción es:

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:

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

La clase de procesos que ${\mathit {P}}$ se permite que varíe a medida que la continuación de la operación de salida influye sustancialmente en las propiedades del cálculo.

Ocultación

Los procesos no limitan el número de conexiones que se pueden establecer 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 ocultación permiten controlar las conexiones establecidas entre puntos de interacción al componer procesos en paralelo. La ocultación se puede denotar de diversas maneras. Por ejemplo, en el cálculo π, la ocultación de un nombre ${\mathit {x}}$ en ${\mathit {P}}$ puede expresarse como $(\nu \;x)P$ , mientras que en CSP podría escribirse como $P\setminus \{x\}$ .

Recursión y replicación

Las operaciones presentadas hasta ahora describen únicamente una interacción finita y, por consiguiente, son insuficientes para una computabilidad completa, que incluye un 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. Replicación $!P$ puede entenderse como una abreviación de la composición paralela de un número infinito numerable de ${\mathit {P}}$ procesos:

!P=P\mid !P

proceso nulo

Los cálculos de procesos generalmente también incluyen un proceso nulo (denotado de diversas maneras como ${\mathit {nil}}$ , $0$ , ${\mathit {STOP}}$ , $\delta$ (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 ancla inductiva sobre la cual se pueden generar procesos más interesantes.

Á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 diversos 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 sorprendente hecho de que sean esencialmente equivalentes, en el sentido de que todos se pueden codificar entre sí, respalda la tesis de Church-Turing . Otra característica común, menos comentada, es que todos se entienden mejor como modelos de computación secuencial . 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 los cálculos de procesos, las redes de Petri en 1962 y el modelo de actores en 1973.

La investigación sobre cálculos de procesos comenzó en serio con el trabajo seminal de Robin Milner sobre el Cálculo de Sistemas Comunicantes (CCS) durante el período de 1973 a 1980. Los Procesos Secuenciales Comunicantes (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 Comunicantes (ACP) e introdujeron el término álgebra de procesos para describir su trabajo. ^[¹^] CCS, CSP y ACP constituyen las tres ramas principales de la familia de cálculos de procesos: la mayoría de los demás cálculos de procesos pueden rastrear sus raíces a uno de estos tres cálculos.

Investigación actual

Se han estudiado diversos cálculos de procesos y no todos se ajustan al paradigma aquí descrito. El ejemplo más destacado podría ser el cálculo ambiental . Esto es de esperar, ya que los cálculos de procesos constituyen 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 bien comportados de un cálculo de procesos dado. Esto es valioso porque (1) la mayoría de los cálculos son bastante impredecibles 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. Más bien, utilizan solo procesos que están muy restringidos en su forma. La restricción de la forma de los procesos se estudia principalmente a través 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 para clases de equivalencia de procesos? Generalmente, se considera que dos procesos son iguales si ningún contexto, es decir, otros procesos que se ejecutan en paralelo, puede detectar una diferencia. Desafortunadamente, precisar esta intuición es complejo y suele dar lugar a 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 parada ). Las bisimulaciones son una herramienta técnica que facilita el razonamiento 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 exige una caracterización más precisa de la expresividad de los cálculos que modelan la computación que la que proporciona la tesis de Church-Turing . Una forma de hacerlo es considerar codificaciones entre dos formalismos y ver qué propiedades pueden preservar potencialmente las codificaciones. Cuantas más propiedades se puedan preservar, más expresivo se dice que es el objetivo de la codificación. Para los cálculos de procesos, los resultados más conocidos son que el π-cálculo síncrono es más expresivo que su variante asíncrona, tiene el mismo poder expresivo que el π-cálculo de orden superior , ^{[ 5 ]} pero es menor que el cálculo ambiental .
Utilización del cálculo de procesos para modelar sistemas biológicos (cálculo π estocástico, BioAmbients, Beta Binders, BioPEPA, cálculo de branas). Algunos consideran que la composicionalidad que ofrecen las herramientas de la teoría de procesos puede ayudar a los biólogos a organizar su conocimiento de forma más formal.

Implementaciones de software

Las ideas que subyacen al álgebra de procesos han dado lugar a varias herramientas, entre ellas:

CADP
Entorno de trabajo de concurrencia
Conjunto de herramientas mCRL2

Relación con otros modelos de concurrencia

El monoide de historia es el objeto libre que puede representar genéricamente las historias de procesos individuales que se comunican. Un cálculo de procesos es entonces un lenguaje formal impuesto a un monoide de historia de manera consistente. ^{[ 6 ]} Es decir, un monoide de historia 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 de historia 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 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 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 habilitar ciertas técnicas algebraicas, facilitando así el razonamiento algebraico sobre los procesos.

Véase también

Referencias

^ Baeten , JCM (2004). "Una breve historia del álgebra de procesos" (PDF) . Informe RSC 04-02 . Vakgroep Informatica, Universidad Técnica de Eindhoven.
↑ Pierce, Benjamin (21 de diciembre de 1996). «Cálculos fundamentales para lenguajes de programación». Manual de informática e ingeniería . CRC Press. págs. 2190–2207 . ISBN 0-8493-2909-4.
↑ Baeten, JCM; Bravetti, M. (agosto de 2005). "Un álgebra de procesos genérica" . 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 . Recuperado el 29 de diciembre de 2007 .
↑ Baeten, JCM; Middelburg, CA (2000). "Álgebra de procesos con temporización: tiempo real y tiempo discreto". Manual de álgebra de procesos : 627–684 . CiteSeerX 10.1.1.42.729 .
↑ 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 . Lecture Notes in Computer Science. Vol. 668. Springer Berlin Heidelberg. pp. 151– 166. doi : 10.1007/3-540-56610-4_62 . ISBN 9783540475989.
↑ 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. pp. 3–41 . ISBN 981-02-2058-8. Archivado del original (PostScript) el 13-06-2011 . Recuperado el 29-04-2009 .

Lecturas adicionales

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 su descarga en formato PDF en el sitio web Using CSP .
Robin Milner : Un cálculo de sistemas comunicantes , Springer Verlag, ISBN 0-387-10235-3.
Robin Milner : Sistemas de comunicación 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 )

[baeten2004-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 fundamentales para lenguajes de programación». Manual de informática e ingeniería . CRC Press. págs. 2190–2207 . ISBN 0-8493-2909-4.

[3] Baeten, JCM; Bravetti, M. (agosto de 2005). "Un álgebra de procesos genérica" . 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 . Recuperado el 29 de diciembre de 2007 .

[4] Baeten, JCM; Middelburg, CA (2000). "Álgebra de procesos con temporización: tiempo real y tiempo discreto". Manual de álgebra de procesos : 627–684 . CiteSeerX 10.1.1.42.729 .

[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 . Lecture Notes in Computer Science. Vol. 668. Springer Berlin Heidelberg. pp. 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. pp. 3–41 . ISBN 981-02-2058-8. Archivado del original (PostScript) el 13-06-2011 . Recuperado el 29-04-2009 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]