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 un conjunto 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, mediante 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 temporal 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 una pequeña colección de primitivas y operadores para combinar esas primitivas.
• Definir leyes algebraicas para los operadores de procesos, que permiten manipular expresiones de procesos mediante razonamiento ecuacional .

Matemáticas de procesos.

Para definir un proceso de cálculo , 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 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
• 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. La composición paralela permite que el cálculo se realice de forma 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 conectarse 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 dicha sincronización. En algunos cálculos de procesos (en particular, el cálculo π ), los propios canales se pueden enviar en mensajes a través de (otros) canales, lo que permite que cambie la topología de las interconexiones del proceso. 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 dirigido de información. Es decir, la entrada y la salida pueden distinguirse como primitivas de interacción dual. Los cálculos de proceso que hacen tales distinciones generalmente definen 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á 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 vinculadas actuarán como marcadores de posición que serán sustituidos por datos cuando lleguen. 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 recibir algunos datos y luego enviarlos ${\displaystyle {\mathit {x}}}$ ${\displaystyle {\mathit {y}}}$ . Para tales fines se puede utilizar la composición secuencial . Es bien conocido por otros modelos de computación. En los cálculos de procesos, el operador de secuencialización suele estar integrado con la entrada o la salida, o ambas. Por ejemplo, el proceso esperará una entrada en . Sólo 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 clave de reducción operativa, que contiene la esencia computacional de los cálculos de procesos, puede darse únicamente en términos de composición paralela, secuencialización, entrada y salida. Los detalles de esta reducción varían según los cálculos, pero la esencia sigue siendo más o menos 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 enviado el mensaje, pasa a ser el proceso , mientras que pasa a ser el proceso , que queda con el marcador de posición sustituido por , los datos recibidos el . ${\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 desarrollen 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 realizar en un punto de interacción determinado. Pero los puntos de interacción permiten interferencia (es decir, 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 realizadas entre puntos de interacción al componer agentes en paralelo. El ocultamiento se puede indicar de diversas formas. Por ejemplo, en el cálculo π, ocultar un nombre en se puede expresar como , mientras que en CSP se puede escribir 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 sólo una interacción finita y, en consecuencia, son insuficientes para una computabilidad total, que incluye un comportamiento no terminante. La recursividad y la replicación son operaciones que permiten descripciones finitas de comportamientos infinitos. La recursividad es bien conocida en el mundo secuencial. La replicación puede entenderse como una abreviatura de la composición paralela de un número contablemente infinito 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 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 posiblemente las funciones μ-recursivas , las máquinas de Turing y el cálculo lambda los ejemplos más conocidos en la actualidad. El sorprendente hecho de que sean esencialmente equivalentes, en el sentido de que todos sean codificables entre sí, respalda la tesis de Church-Turing . Otra característica compartida rara vez se comenta: todos ellos se entienden más fácilmente 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 actor en 1973.

La investigación sobre los cálculos de procesos comenzó en serio con el trabajo fundamental de Robin Milner sobre el cálculo de sistemas de comunicación (CCS) durante el período de 1973 a 1980. Los procesos de comunicación secuencial (CSP) de CAR Hoare aparecieron por primera vez en 1978 y se desarrollaron posteriormente. en un cálculo de proceso completo a 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 se conoció 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 demás cálculos de proceso pueden tener sus raíces en uno de estos tres cálculos.

La investigación actual

Se han estudiado varios cálculos de procesos y no todos se ajustan al paradigma esbozado aquí. El ejemplo más destacado puede ser el cálculo ambiental . Esto es de esperarse 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 modelar mejor los fenómenos computacionales.
• Encontrar subcálculos que se comporten bien de un cálculo de proceso determinado. Esto es valioso porque (1) la mayoría de los cálculos son bastante descabellados 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 sólo 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 de 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 procesos de equivalencia? Generalmente, 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, precisar esta intuición es sutil y en su mayoría 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 al razonamiento 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 exige una caracterización más precisa de la expresividad del cálculo de modelos de cálculos que la que ofrece 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 conservar, 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 el cálculo ambiental . ^{[ cita necesaria ]}
• Uso del cálculo de procesos para modelar sistemas biológicos (cálculo π estocástico, BioAmbients, Beta Binders, 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, entre ellas:

• 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 es capaz de representar las historias de procesos comunicativos individuales. Un cálculo de proceso es entonces un lenguaje formal impuesto a un monoide histórico de manera consistente. ^[6] Es decir, un monoide histórico sólo puede registrar una secuencia de eventos, con sincronización, pero no especifica las transiciones de estado permitidas. Así, un cálculo de procesos es para un monoide histórico 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 proceso 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 procesos.

Ver también

• Comunicar procesos secuenciales.
• ProVerif
• Sonda estocástica
• Probador de tití
• 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, Benjamín (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 álgebra de procesos genéricos". 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 Informática, Universidad de Aarhus . Consultado el 29 de diciembre de 2007 .
4. Baeten, JCM; Middelburg, California (2000). "Álgebra de procesos con temporización: tiempo real y tiempo discreto": 627–684. CiteSeerX 10.1.1.42.729 .  {{cite journal}}: Citar diario requiere |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 conferencias sobre informática. vol. 668. Springer Berlín 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 la traza". En Diekert, V.; Rozenberg, G. (eds.). El Libro de las Huellas . Singapur: World Scientific. págs. 3–41. ISBN 981-02-2058-8. Archivado desde el original (PostScript) el 13 de junio de 2011 . Consultado el 29 de abril de 2009 .

Otras lecturas

• 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 del 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 de Uso de 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 . 
• 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 )