El cálculo de sistemas de comunicación ( CCS ) es un cálculo de procesos introducido por Robin Milner alrededor de 1980 y el título de un libro que describe el cálculo. Sus acciones modelan comunicaciones indivisibles entre exactamente dos participantes. El lenguaje formal incluye primitivas para describir la composición paralela, la elección entre acciones y la restricción del alcance. CCS es útil para evaluar la corrección cualitativa de las propiedades de un sistema como interbloqueo o bloqueo activo . [1]
Según Milner, "no hay nada canónico en la elección de los combinadores básicos, a pesar de que fueron elegidos con gran atención a la economía. Lo que caracteriza a nuestro cálculo no es la elección exacta de los combinadores, sino más bien la elección de la interpretación y del marco matemático ".
Las expresiones del lenguaje se interpretan como un sistema de transición etiquetado . Entre estos modelos, la bisimilitud se utiliza como equivalencia semántica.
Sintaxis
Dado un conjunto de nombres de acciones, el conjunto de procesos CCS se define mediante la siguiente gramática BNF :
Las partes de la sintaxis son, en el orden indicado anteriormente
- proceso inactivo
- el proceso inactivo es un proceso CCS válido
- acción
- el proceso puede realizar una acción y continuar como el proceso
- identificador de proceso
- escribir para usar el identificador para referirse al proceso (que puede contener el identificador sí mismo, es decir, se permiten definiciones recursivas)
- elección
- el proceso puede proceder como el proceso o el proceso
- composición paralela
- dice que los procesos y existir simultáneamente
- renombrar
- es el proceso con todas las acciones nombradas renombrado como
- restricción
- es el proceso sin acción
Cálculos, modelos e idiomas relacionados
- La comunicación de procesos secuenciales (CSP), desarrollado por Tony Hoare , es un lenguaje formal que surgió en una época similar a la CCS.
- El álgebra de procesos de comunicación (ACP) fue desarrollado por Jan Bergstra y Jan Willem Klop en 1982, y utiliza un enfoque axiomático (al estilo del álgebra universal ) para razonar sobre una clase similar de procesos como CCS.
- El cálculo pi , desarrollado por Robin Milner , Joachim Parrow y David Walker a finales de los 80, amplía el CCS con la movilidad de los enlaces de comunicación, al permitir que los procesos comuniquen los nombres de los propios canales de comunicación.
- PEPA , desarrollado por Jane Hillston, introduce el tiempo de actividad en términos de tasas distribuidas exponencialmente y elección probabilística, lo que permite evaluar las métricas de rendimiento.
- Los sistemas concurrentes de comunicación reversible (RCCS) introducidos por Vincent Danos , Jean Krivine y otros, introducen la reversibilidad (parcial) en la ejecución de los procesos CCS.
Algunos otros idiomas basados en CCS:
- Cálculo de sistemas de radiodifusión
- Especificación de idioma de orden temporal (LOTOS)
- El cálculo de procesos para modelos ecológicos espacialmente explícitos (PALPS) es una extensión de CCS con opciones probabilísticas, ubicaciones y atributos para ubicaciones [2]
- Motor de interpretación del lenguaje Java Orchestration (Jolie) [3]
Modelos que se han utilizado en el estudio de sistemas similares a CCS:
Referencias
- Robin Milner: Un cálculo de sistemas de comunicación , Springer Verlag, ISBN 0-387-10235-3 . 1980.
- Robin Milner, Comunicación y Concurrencia , Prentice Hall, Serie Internacional en Ciencias de la Computación, ISBN 0-13-115007-3 . 1989
- ^ Herzog, Ulrich, ed. (Mayo de 2007). "Abordar los grandes espacios estatales en el modelado de rendimiento" . Métodos formales para la evaluación del desempeño . Apuntes de conferencias en informática. 4486 . Saltador. págs. 318–370. doi : 10.1007 / 978-3-540-72522-0 . ISBN 978-3-540-72482-7. Archivado desde el original el 12 de abril de 2008 . Consultado el 21 de abril de 2009 .
- ^ A Philippou, M Toro, M Antonaki. Simulación y verificación en un cálculo de procesos para modelos ecológicos espacialmente explícitos. Anales científicos de la informática 23 (1). 2014
- ^ Montesi, Fabrizio; Guidi, Claudio; Lucchi, Roberto; Zavattaro, Gianluigi (27 de junio de 2007). "JOLIE: un motor de intérprete de lenguaje de orquestación de Java" . Notas electrónicas en informática teórica . Actas combinadas del Segundo Taller Internacional sobre Coordinación y Organización (CoOrg 2006) y el Segundo Taller Internacional sobre Métodos y Herramientas para Coordinar Sistemas Simultáneos, Distribuidos y Móviles (MTCoord 2006). 181 : 19–33. doi : 10.1016 / j.entcs.2007.01.051 . ISSN 1571-0661 .