Conceptos y mecanismos fundamentales

Estados globales consistentes de sistemas distribuidos:[pic 1]

Conceptos y mecanismos fundamentales

Ö¨ zalp Babaoğ˘ lu        Keith Marzullo

Informe técnico UBLCS-93-1

Enero de 1993[pic 2]

Laboratorio de Ciencias de la Computación

Universidad de Bolonia

Piazza di Porta S. Donato, 5 40127 Bolonia (Italia)

Los informes técnicos del Laboratorio de Investigación en Ciencias de la Computación de la Universidad de Bolonia están disponibles a través de FTP anónimo desde el ftp.cs.unibo.it:/pub/TR/UBLCS en formato PostScript comprimido. Los resúmenes están disponibles en el mismo host en el directorio / pub / TR / ABSTRACTS en formato de texto sin formato. Todos los autores locales pueden ser contactados por correo electrónico en la dirección apellido@ cs.unibo.it.

Serie de informes técnicos UBLCS

92-1 Mapeo de cálculos paralelos en sistemas distribuidos en Paralex, por Ö        ¨. Babaoğ˘ lu, L. Alvisi, A.

Amoroso y R. Davoli, enero de 1992. 92-2 Computación científica paralela en sistemas distribuidos: el enfoque Paralex, por L. Alvisi, A.

Amoroso, Ö¨. Babaoğ˘ lu, A. Baronio, R. Davoli y LA Giachini, febrero de 1992.

92-3 Soporte en tiempo de ejecución para el equilibrio dinámico de carga y la depuración en Paralex, por Ö     ¨. Babaoğ˘ lu, L.

Alvisi, S. Amoroso, R. Davoli, LA Giachini, septiembre de 1992. 92-4 Paralex: un entorno

para la programación paralela en sistemas distribuidos, por Ö        ¨. Babaoğ˘ lu, L.

Alvisi, S. Amoroso, R. Davoli, LA Giachini, octubre de 1992. 93-1 Estados globales consistentes de sistemas distribuidos: conceptos y mecanismos fundamentales, por Ö        ¨.

Babaoğ˘ lu y K. Marzullo, enero de 1993. 93-2 Comprender

el compromiso atómico sin bloqueo, por Ö        ¨. Babaoğ˘ lu y S. Toueg, enero de 1993.

Estados globales consistentes de sistemas distribuidos: conceptos y mecanismos fundamentales

Ö¨ zalp Babaoğ˘ lu 1        KeithMarzullo 2

Informe técnico UBLCS-93-1

Enero de 1993

Resumen

Muchos problemas importantes de la computación distribuida admiten soluciones que contienen una fase en la que es necesario detectar alguna propiedad global. Este subproblema puede verse como una instancia de la

Evaluación global de predicados ( GPE) problema donde el objetivo es establecer la verdad de una expresión

booleana cuyas variables pueden referirse al estado global del sistema. Dadas las incertidumbres en los sistemas distribuidos asincrónicos que surgen de los retrasos en la comunicación y las velocidades relativas de los cálculos, la formulación y solución de GPE revelan la mayoría de las sutilezas en el razonamiento global con información imperfecta. En este artículo, usamos GPE como un problema canónico para examinar conceptos y mecanismos que son útiles para comprender los estados globales de los cálculos distribuidos. Ilustramos la utilidad de las técnicas desarrolladas examinando la detección de interbloqueo distribuido y la depuración distribuida como dos instancias de GPE.

[pic 3]

1. Departamento de Matemáticas, Universidad de Bolonia, Piazza Porta S. Donato 5, 40127 Bolonia, Italia. Este autor fue apoyado en parte por la Comisión de Comunidades Europeas en el marco del Proyecto de Investigación Básica del Programa ESPRIT 6360 (BROADCAST), Hewlett-Packard de Italia y el Ministerio de Universidad, Investigación de Italia.

y Tecnología.

1. Departamento de Ciencias de la Computación, 4130 Upson Hall, Universidad de Cornell, Ithaca, Nueva York 14853 EE. UU. Esto

El autor fue apoyado en parte por la Agencia de Proyectos de Investigación Avanzada de Defensa (DoD) bajo la subvención NAG 2–593 de NASA Ames, y por subvenciones de IBM y Siemens. Los puntos de vista, opiniones y hallazgos contenidos en este informe pertenecen a los autores y no deben interpretarse como una posición, política o decisión oficial del Departamento de Defensa.

1. Introducción

1. Introducción

Una gran clase de problemas de computación indistribuida puede plantearse como la ejecución de alguna notificación o reacción cuando el estado del sistema satisface una condición particular. Ejemplos de tales problemas incluyen monitoreo y depuración, detección de estados particulares como interbloqueo y terminación, y adaptación dinámica de la con fi guración de un programa, como para balanceo de carga. Por lo tanto, la capacidad de construir un estado global y evaluar un predicado sobre dicho estado constituye el núcleo de las soluciones a muchos problemas en la computación distribuida.

El estado global de un sistema distribuido es la unión de los estados de los procesos individuales.

Dado que los procesos de un sistema distribuido no comparten la memoria, sino que se comunican únicamente a través del intercambio de mensajes, un proceso que desee construir un estado global debe inferir los componentes remotos de ese estado a través del intercambio de mensajes. Por lo tanto, un problema fundamental en la computación distribuida es asegurar que un estado global construido de esta manera sea significativo.

En los sistemas distribuidos asincrónicos, un estado global obtenido a través de observaciones remotas podría ser obsoleto, incompleto o inconsistente. De manera informal, un estado global es inconsistente si nunca pudo haber sido construido por un observador idealizado que es externo al sistema. Debe quedar claro que las incertidumbres en los retrasos de los mensajes y en las velocidades relativas a las que proceden los cálculos locales impiden que un proceso saque conclusiones sobre el estado global instantáneo del sistema al que pertenece. Si bien el simple aumento de la frecuencia de la comunicación puede ser eficaz para hacer que las visiones locales de un estado global sean más actualizadas y completas, no es suficiente para garantizar que el estado global sea coherente. Asegurar la consistencia de un estado global construido requiere que razonemos tanto sobre el orden en el que los mensajes son observados por un proceso como sobre la información contenida en los mensajes. Para una gran clase de problemas, la coherencia resulta ser una formalización apropiada de la noción de que el razonamiento global con información local es "significativo".

...