Modelos de Concurrencia y Cálculos de Procesos
Los modelos de concurrencia y los cálculos de procesos ofrecen descripciones formales de cómo los procesos independientes se ejecutan, comunican y sincronizan.
Definition
Un cálculo de procesos es un álgebra formal para describir sistemas concurrentes como procesos comunicantes, con operadores para composición paralela, comunicación y elección, y equivalencias que determinan cuándo dos procesos se comportan de la misma manera.
Scope
Este tema abarca los modelos algebraicos de computación concurrente: CSP de Hoare y CCS de Milner, el pi-cálculo para procesos móviles cuya topología de comunicación cambia, y el modelo de actor de paso de mensajes asíncrono. Aborda las primitivas de comunicación y sincronización, las equivalencias de comportamiento como la bisimulación, y el contraste entre la concurrencia de memoria compartida y la de paso de mensajes.
Core questions
- ¿Cómo se pueden describir algebraicamente los procesos concurrentes comunicantes?
- ¿Cuándo son dos procesos concurrentes conductualmente equivalentes?
- ¿Cómo se compara el paso de mensajes con la concurrencia de memoria compartida?
- ¿Cómo se modelan las estructuras de comunicación dinámicas, como en el pi-cálculo?
Key theories
- Procesos Secuenciales Comunicantes (CSP)
- El CSP de Hoare modela la concurrencia a través de procesos que se sincronizan en eventos de comunicación compartidos, proporcionando una base para los lenguajes de paso de mensajes y una teoría de refinamiento de procesos.
- CCS y bisimulación
- El Cálculo de Sistemas Comunicantes de Milner ofrece un álgebra de procesos con una noción precisa de equivalencia de comportamiento, la bisimulación, para razonar sobre cuándo los procesos son intercambiables.
- El pi-cálculo
- Milner, Parrow y Walker extendieron los cálculos de procesos a la movilidad, permitiendo que los propios canales de comunicación se pasen como mensajes para que la estructura de conexión evolucione dinámicamente.
Clinical relevance
Los cálculos de procesos y el modelo de actor sustentan el diseño de lenguajes y marcos concurrentes y distribuidos construidos sobre el paso de mensajes, y proporcionan herramientas formales para especificar y verificar protocolos. La bisimulación y el refinamiento ofrecen criterios precisos para un comportamiento concurrente correcto.
History
La teoría de la concurrencia maduró a finales de la década de 1970 con el CSP de Hoare y el CCS de Milner, mientras que el modelo de actor de Hewitt (1973) ofreció una alternativa de paso de mensajes asíncrono. El pi-cálculo en 1992 capturó la movilidad de los procesos. Estos cálculos influyeron en los lenguajes de paso de mensajes y en las bibliotecas de concurrencia, y siguen siendo fundamentales para la verificación de protocolos.
Debates
- Memoria compartida versus paso de mensajes
- Una cuestión de diseño fundamental es si la concurrencia debe organizarse en torno a un estado mutable compartido con sincronización o en torno a procesos aislados que intercambian mensajes, siendo los cálculos de procesos y el modelo de actor defensores de esta última opción.
Key figures
- C. A. R. Hoare
- Robin Milner
- Carl Hewitt
- Joachim Parrow
- David Walker
Related topics
Seminal works
- hoare1978
- milner1989
- milner1992
- hewitt1973
Frequently asked questions
- ¿Qué es la bisimulación?
- La bisimulación es una equivalencia entre procesos que se mantiene cuando cada uno puede igualar los pasos observables del otro indefinidamente, formalizando la idea de que dos procesos concurrentes exhiben el mismo comportamiento.
- ¿Qué añade el pi-cálculo sobre los cálculos anteriores?
- El pi-cálculo modela la movilidad al permitir que los canales de comunicación se envíen como mensajes, de modo que la topología de quién puede hablar con quién puede cambiar durante la ejecución, capturando sistemas dinámicos y reconfigurables.