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".

Otra fuente de dificultad en los sistemas distribuidos surge cuando procesos separados construyen independientemente estados globales. La variabilidad en los retrasos de los mensajes podría llevar a que estos procesos separados construyan diferentes estados globales para el mismo cálculo. Aunque cada uno de estos estados globales puede ser consistente y los procesos pueden estar evaluando el mismo predicado, los diferentes procesos pueden ejecutar reacciones conflictivas. Este "efecto relativista" es inherente a todos los cálculos distribuidos y limita la clase de propiedades del sistema que pueden detectarse de manera efectiva.

En este artículo, formalizamos y ampliamos los conceptos anteriores en el contexto de un problema abstracto llamado Evaluación global de predicados ( GPE). El objetivo de GPE es determinar si el estado global del sistema satisface algún predicado. Los predicados globales se construyen para codificar las propiedades de interés del sistema en términos de variables de estado. Ejemplos de problemas de sistemas distribuidos donde las propiedades relevantes se pueden codificar como predicados globales incluyen detección de interbloqueo, detección de terminación, detección de pérdida de token, recolección de almacenamiento inalcanzable (basura), puntos de control y reinicio, depuración y, en general, monitoreo y reconfiguración. En este sentido, una solución a GPE puede verse como el núcleo de una solución genérica para todos estos problemas; lo que queda por hacer es la formulación del predicado apropiado

y la construcción de reacciones o notificaciones a ejecutar cuando el

el predicado se satisface.

Comenzamos definiendo un modelo formal para sistemas distribuidos asincrónicos y cálculos distribuidos. Luego examinamos dos estrategias diferentes para resolver GPE. La primera estrategia, introducida en la Sección 5 y perfeccionada en la Sección 13, se basa en un proceso de seguimiento.

que interroga activamente al resto del sistema para construir el estado global. En la Sección 6 damos una definición formal de consistencia de estados globales. La estrategia alternativa, discutida en la Sección 7, hace que el monitor observe pasivamente el sistema para construir sus estados globales. Las secciones 8 a 13 presentan una serie de conceptos y mecanismos necesarios para que las dos estrategias funcionen de manera eficiente. En la Sección 14 identificamos las propiedades que los predicados globales deben satisfacer para resolver problemas prácticos usando GPE. En la Sección 15 abordamos el problema de varios monitores que observan el mismo cálculo. Ilustramos la utilidad de los conceptos y mecanismos subyacentes aplicándolos a la detección de interbloqueos y a la depuración en sistemas distribuidos.

...