La indeterminación en el cálculo concurrente se ocupa de los efectos de la indeterminación en el cálculo concurrente . La computación es un área en la que la indeterminación está adquiriendo cada vez mayor importancia debido al aumento masivo de la concurrencia debido a las redes y al advenimiento de las arquitecturas informáticas de múltiples núcleos . Estos sistemas informáticos hacen uso de árbitros que dan lugar a la indeterminación .
Patrick Hayes [1973] argumentó que la "habitual distinción nítida que se hace entre los procesos de computación y deducción es engañosa". Robert Kowalski desarrolló la tesis de que la computación podía ser subsumida por la deducción y citó con aprobación "La computación es deducción controlada", que atribuyó a Hayes en su artículo de 1988 sobre la historia temprana de Prolog. Contrariamente a Kowalski y Hayes, Carl Hewitt afirmó que la deducción lógica era incapaz de llevar a cabo computación concurrente en sistemas abiertos [ cita requerida ] .
Hewitt [1985] y Agha [1991], y otros trabajos publicados, argumentaron que los modelos matemáticos de concurrencia no determinaban cálculos concurrentes particulares de la siguiente manera: El modelo de Actor hace uso del arbitraje (a menudo en forma de árbitros nocionales ) para determinar qué mensaje es el siguiente en el orden de llegada de un Actor al que se le envían múltiples mensajes simultáneamente. Esto introduce indeterminación en el orden de llegada. Dado que los órdenes de llegada son indeterminados, no se pueden deducir de la información previa solo mediante la lógica matemática. Por lo tanto, la lógica matemática no puede implementar el cálculo concurrente en sistemas abiertos.
Los autores afirman que, aunque la lógica matemática no puede, en su opinión, implementar la concurrencia general, puede implementar algunos casos especiales de computación concurrente, por ejemplo, computación secuencial y algunos tipos de computación paralela, incluido el cálculo lambda .
Según Hewitt, en términos concretos para los sistemas de Actor, normalmente no podemos observar los detalles por los cuales se determina el orden de llegada de los mensajes para un Actor. Intentar hacerlo afecta los resultados e incluso puede llevar la indeterminación a otro lugar. Por ejemplo, véase metaestabilidad en electrónica y árbitros . En lugar de observar los aspectos internos de los procesos de arbitraje de los cálculos de Actor, esperamos los resultados. La indeterminación en los árbitros produce indeterminación en los Actores. La razón por la que esperamos los resultados es que no tenemos otra alternativa debido a la indeterminación.
Es importante tener claro el fundamento de la afirmación publicada sobre la limitación de la lógica matemática. No se trataba simplemente de que los actores no pudieran, en general, implementarse en la lógica matemática. La afirmación publicada era que, debido a la indeterminación de la base física del modelo de actores, ningún tipo de lógica matemática deductiva podía escapar de la limitación. Esto se volvió importante más adelante, cuando los investigadores intentaron extender Prolog (que tenía cierta base en la programación lógica ) al cálculo concurrente mediante el paso de mensajes. (Véase la sección siguiente).
¿Qué dice la teoría matemática de actores sobre esto? Un sistema cerrado se define como aquel que no se comunica con el exterior. La teoría del modelo de actores proporciona los medios para caracterizar todos los cálculos posibles de un sistema de actores cerrado utilizando el teorema de representación [Hewitt 2007] de la siguiente manera:
- La denotación matemática denotada por un sistema cerrado S se encuentra construyendo aproximaciones cada vez mejores a partir de un comportamiento inicial llamado ⊥ S utilizando una progresión de función de aproximación de comportamiento S para construir una denotación (que significa ) para S de la siguiente manera:
De esta manera, el comportamiento de S puede caracterizarse matemáticamente en términos de todos sus comportamientos posibles (incluidos aquellos que implican no determinismo ilimitado).
Por lo tanto, la lógica matemática puede caracterizar (en lugar de implementar) todos los cálculos posibles de un sistema de actor cerrado.
Un sistema de Actor abierto S es uno en el que las direcciones de Actores externos pueden pasarse a S en medio de los cálculos para que S pueda comunicarse con estos Actores externos. Estos Actores externos pueden entonces, a su vez, comunicarse con Actores internos a S utilizando direcciones suministradas a ellos por S. Debido a la limitación de la incapacidad de deducir ordenamientos de llegada, el conocimiento de qué mensajes se envían desde el exterior no permitiría deducir la respuesta de S. Cuando se utilizan otros modelos de sistemas concurrentes (por ejemplo, cálculos de procesos ) para implementar sistemas abiertos, estos sistemas también pueden tener un comportamiento que depende de ordenamientos de tiempo de llegada y, por lo tanto, no pueden implementarse por deducción lógica.
Keith Clark , Hervé Gallaire, Steve Gregory, Vijay Saraswat, Udi Shapiro, Kazunori Ueda, etc. desarrollaron una familia de sistemas de paso de mensajes concurrentes similares a Prolog que utilizaban la unificación de variables compartidas y flujos de estructuras de datos para los mensajes. Este tipo de sistema se utilizó como base del Proyecto Japonés de Quinta Generación (ICOT) .
Carl Hewitt y Gul Agha [1991] argumentaron que estos sistemas concurrentes tipo Prolog no eran ni deductivos ni lógicos: al igual que el modelo Actor, los sistemas concurrentes tipo Prolog se basaban en el paso de mensajes y, en consecuencia, estaban sujetos a la misma indeterminación.
Hewitt sostuvo que se puede aprender una lección básica de Prolog y los sistemas concurrentes similares a Prolog: un modelo universal de computación concurrente está limitado por la existencia de una sobrecarga obligatoria en los mecanismos básicos de comunicación. Este es un argumento en contra de incluir la invocación dirigida por patrones utilizando la unificación y la extracción de mensajes de flujos de estructuras de datos como primitivos fundamentales. Pero compare el estudio de Shapiro sobre lenguajes de programación concurrente similares a Prolog para encontrar argumentos a favor de su inclusión.
El arbitraje es la base de la indeterminación en el modelo de Actor de computación concurrente (ver Historia del modelo de Actor y Teoría del modelo de Actor ). También puede desempeñar un papel en otros modelos de sistemas concurrentes, como los cálculos de procesos .
