Estado global (informática) ⇐ Proyectos de artículos

[Anonymous]

Un '''estado global''' de un sistema distribuido (computación distribuida) es la tupla de todos los estados locales del proceso (proceso (computación)) y el contenido de todos los canales de comunicación (canal de comunicación) en un instante particular. Debido a que los sistemas distribuidos carecen de memoria compartida y de un reloj global, ningún proceso puede observar todos los estados locales y mensajes en tránsito simultáneamente.

Una asamblea ingenua de estados locales recopilados secuencialmente, sin coordinación, produce un estado global que puede no corresponder a ningún estado por el que realmente pasó el sistema. Un mensaje enviado antes de que se registre el estado de un proceso pero recibido después de que el de otro parezca haber desaparecido o duplicado, generando una instantánea lógicamente imposible.

Un estado global es "consistente" si corresponde a un estado por el cual podría haber pasado una posible ejecución del sistema: formalmente, ningún mensaje se registra como recibido a menos que también se registre como enviado. Esta noción, introducida por K. Mani Chandy y Leslie Lamport en 1985, también se expresa como un "corte consistente" del historial de ejecución del sistema. Chandy y Lamport demostraron que se puede alcanzar cualquier estado global consistente desde el estado inicial del sistema, y que se puede alcanzar el estado actual real desde cualquier estado global consistente registrado.

Los estados globales consistentes respaldan la detección de punto muerto, la detección de terminación, la recolección de basura distribuida (recolección de basura (informática)), los puntos de control para la tolerancia a fallas y la depuración distribuida. Son suficientes para evaluar ''predicados estables'', propiedades que una vez verdaderas siguen siendo verdaderas, sin necesidad de que el sistema se detenga.

== Modelo del sistema ==

El modelo adoptado por Chandy y Lamport consiste en un conjunto fijo de
Cada proceso ejecuta una secuencia de tres tipos de eventos: un evento de ''envío'' en un canal saliente, un evento de ''recepción'' en un canal entrante o un evento ''interno'' que cambia el estado local sin comunicarse. El '''estado local''
La relación de sucedido antes de los acontecimientos, introducida por Lamport en 1978, proporciona un orden parcial: evento
== Estado global ==

Un '''estado global''' del sistema es una tupla

:GS = (s_1, s_2, \ldots, s_n,\ M_{12}, M_{13}, \ldots, M_{n(n-1)})

compuesto por un estado local
Como objeto matemático, un estado global no necesita corresponder a ningún instante que fuera simultáneamente observable desde un único punto de vista. Dos procesos pueden tener sus estados locales registrados en diferentes momentos reales, y los mensajes en tránsito durante ese intervalo pueden aparecer en el estado local de ninguno de los procesos.

'''Ejemplo.'''' Considere tres procesos
== Estado global consistente ==

=== La condición de coherencia ===

Un ''historial de ejecución'' del sistema es el conjunto de todos los eventos parcialmente ordenados por la relación de sucedido antes. Un '''corte'''
Un corte es '''consistente''' si por cada evento de recepción en el pasado de
=== Por qué falla la colección ingenua ===

Si un observador registra los estados locales secuencialmente (primero consultando
El recorte correspondiente es inconsistente: la recepción de
=== Teorema de accesibilidad ===

Chandy y Lamport demostraron que se puede alcanzar cualquier estado global consistente registrado durante una ejecución desde el estado inicial de esa ejecución, y que se puede alcanzar el estado real del sistema en el momento en que se completa la grabación desde el estado global consistente registrado. Formalmente, si
El estado registrado no necesita coincidir con ningún estado que existió simultáneamente durante la ejecución, pero representa un estado intermedio válido a través del cual podría haber pasado una posible ejecución del sistema. Esta propiedad hace que el estado registrado sea confiable para verificar las propiedades del sistema (como si existe un punto muerto) sin congelar ni pausar la ejecución.

== Predicados estables ==

Un predicado (lógica) | predicado
Según el teorema de alcanzabilidad, si un predicado estable
Los predicados inestables, aquellos que pueden volverse falsos después de convertirse en verdaderos, no pueden evaluarse de manera confiable a partir de una sola instantánea. La detección de condiciones transitorias, como por ejemplo si un mensaje en particular está actualmente en tránsito, requiere un monitoreo continuo o múltiples observaciones, fuera del alcance de las técnicas basadas en instantáneas.

== Registrar un estado global ==

Registrar un estado global consistente requiere un protocolo coordinado porque los mensajes pueden estar en tránsito cuando se recopilan los estados locales; una colección no coordinada puede producir un corte inconsistente. Cualquier protocolo correcto debe garantizar que el conjunto de estados locales registrados y contenidos del canal satisfaga la condición de coherencia.

El protocolo basado en marcadores de Chandy y Lamport (1985) procede de la siguiente manera: El proceso iniciador registra su propio estado local y envía un mensaje de control especial, un "marcador", en cada canal saliente antes de enviar cualquier mensaje de aplicación adicional en esos canales. cuando un proceso
El protocolo basado en marcadores asume el orden de los canales FIFO. Para sistemas con canales que no son FIFO, el algoritmo Lai-Yang (1987) utiliza la "coloración" de mensajes, etiquetando cada mensaje de aplicación como pre-instantánea o post-instantánea, para evitar la necesidad de marcadores explícitos. El algoritmo de Mattern (1989) utiliza relojes vectoriales para determinar qué mensajes pertenecen a qué instantánea, permitiendo múltiples instantáneas simultáneas sin mensajes de marcador dedicados. nombre="Mattern1989" />

== Aplicaciones ==

Los estados globales consistentes y la propiedad de predicado estable que respaldan se han aplicado en la investigación y la práctica de sistemas distribuidos.

Un punto muerto distribuido es un ciclo de procesos, cada uno de los cuales espera un recurso retenido por el siguiente; esta es una propiedad estable. Registrar un estado global consistente y verificar el gráfico de espera registrado para los ciclos detecta un punto muerto sin falsos negativos: si existe un ciclo en el estado registrado, existe en el estado actual real por estabilidad. La terminación, sin ningún proceso activo ni mensajes en tránsito, es estable. Una instantánea global consistente en la que todos los estados del proceso están inactivos y todos los estados del canal están vacíos confirma que el cálculo ha finalizado. Un objeto sin referencias activas es elegible para su recopilación; esta propiedad es estable en todos los estados del montón combinados de todos los procesos. Los recolectores de basura basados en instantáneas identifican objetos inalcanzables registrando un estado global consistente de todos los montones de procesos.

El registro periódico de estados globales consistentes crea puntos de recuperación desde los cuales la ejecución puede reiniciarse después de una falla del proceso, sin tener que reproducir la ejecución completa desde el principio. El teorema de accesibilidad garantiza que reiniciar desde un estado consistente registrado conduce a una continuación válida. Las violaciones de aserciones y las fallas invariantes son estables si se formulan como condiciones que, una vez desencadenadas, no se eliminan automáticamente. La reproducción de estados globales consistentes registrados permite al depurador verificar si dichas condiciones se mantuvieron durante una ejecución.

== Extensiones ==

El trabajo posterior ha relajado los supuestos del modelo original de Chandy-Lamport.

'''Canales no FIFO.''' El protocolo original requiere que los canales entreguen los mensajes en orden. Lai y Yang (1987) ampliaron la grabación de instantáneas a canales no FIFO coloreando los mensajes: cada proceso colorea todos los mensajes de aplicación que envía después de registrar su propio estado con un color posterior a la instantánea, lo que permite a los receptores distinguir los mensajes previos a la instantánea de los posteriores sin marcadores. Mattern (1989) logró un resultado similar utilizando relojes vectoriales, que proporcionan a cada mensaje una marca de tiempo suficiente para determinar su relación con la instantánea sin colores ni marcadores explícitos.

'''Sistemas con fallas en el proceso.''' Si un proceso falla durante la grabación de instantáneas, no se puede capturar su estado local; Es posible que los mensajes en tránsito en los canales hacia o desde el proceso fallido nunca se entreguen. Los protocolos de puntos de control coordinados y los esquemas de registro de mensajes amplían la grabación de instantáneas para sistemas tolerantes a fallas al combinar la grabación del estado local con el registro de los mensajes enviados y recibidos, lo que permite la recuperación incluso cuando se pierden algunos estados registrados.

'''Conjuntos de procesos dinámicos'''. Existen variantes para sistemas en los que los procesos pueden unirse o abandonar el cálculo durante la ejecución. Estos protocolos rastrean la membresía del proceso como parte de la instantánea, registrando qué procesos existían en el momento de cada observación estatal local.

== Ver también ==

* Algoritmo Chandy-Lamport
* Algoritmo de instantáneas
* Reloj vectorial
* Marca de tiempo del puerto
* Sucedió antes
* Punto muerto
* Computación distribuida




Computación distribuida
Algoritmos distribuidos
Ciencias de la Computación
Concurrencia (informática)

More details: https://en.wikipedia.org/wiki/Global_st ... r_science)