Gbcast

Gbcast (también conocido como transmisión grupal ) es un protocolo de multidifusión confiable que proporciona una entrega de mensajes ordenada y tolerante a fallas (todo o nada) en un grupo de receptores dentro de una red de máquinas que experimentan fallas. ^{[1] [2] [3]} El protocolo es capaz de resolver Consensus en una red de procesadores no confiables y puede usarse para implementar la replicación de la máquina de estado . ^{[4] [5]} Gbcast se puede utilizar de forma independiente o puede admitir el modelo de ejecución de sincronía virtual , en cuyo caso Gbcast se utiliza normalmente para la gestión de membresía de grupo, mientras que otros protocolos más rápidos a menudo se prefieren para las tareas de comunicación de rutina.

Historia

Introducido en 1985, ^[1] Gbcast fue el primer protocolo de multidifusión confiable ampliamente implementado para implementar la replicación de la máquina de estado con membresía reconfigurable dinámicamente. Aunque este problema se había tratado teóricamente con varios modelos en trabajos anteriores, Gbcast innovó al mostrar que las mismas multidifusiones utilizadas para actualizar los datos replicados dentro de la máquina de estado también se pueden usar para reconfigurar dinámicamente la pertenencia al grupo, que luego puede evolucionar para permitir que los miembros unirse y salir a voluntad, además de ser removido en caso de falla. Esta funcionalidad, junto con un mecanismo de transferencia de estado utilizado para inicializar miembros que se unen, representa la base del modelo de ejecución del grupo de procesos de sincronía virtual .

El término replicación de la máquina de estado fue sugerido por primera vez por Leslie Lamport ^[4] y fue ampliamente adoptado después de la publicación de un estudio escrito por Fred B. Schneider . ^[6] El modelo cubre cualquier sistema en el que algún objeto determinista (una máquina de estado) sea replicado de tal manera que se pueda aplicar una serie de comandos a las réplicas de manera tolerante a fallas. Una máquina de estado reconfigurable es aquella que puede variar su membresía, agregando nuevos miembros o eliminando los antiguos. ^[7] Algunos protocolos de máquina de estado también pueden superar la indisponibilidad temporal de un subconjunto de los miembros actuales sin requerir reconfiguración cuando surgen tales situaciones, incluyendo Gbcast y también Paxos, ^[5] El protocolo ampliamente citado de Lamport para la replicación de máquinas de estado.

La replicación de la máquina de estado está estrechamente relacionada con el problema del consenso distribuido , ^[8] en el que una colección de procesos debe acordar algún resultado de decisión, como el ganador de una elección. En particular, se puede demostrar que cualquier solución al problema de replicación de la máquina de estado también sería capaz de resolver el consenso distribuido. Como consecuencia, los resultados de imposibilidad para el consenso distribuido ^{[9] se} aplican a las soluciones al problema de la replicación de la máquina de estado. Las implicaciones de este hallazgo se discuten en liveness .

Gbcast es algo inusual en el sentido de que la mayoría de las soluciones al problema de replicación de la máquina de estado están estrechamente integradas con la aplicación que se replica. Gbcast, por el contrario, está diseñado como una API de multidifusión e implementado por una biblioteca que envía mensajes a los miembros del grupo. Lamport , Malkhi y Zhou señalan que pocos protocolos de multidifusión fiables tienen las propiedades de durabilidad necesarias para implementar correctamente el modelo de máquina de estado. Gbcast presenta las propiedades necesarias. ^[7]

El protocolo Gbcast se describió por primera vez en una publicación de 1985 que discutía la infraestructura que respalda el modelo de sincronía virtual en Isis Toolkit. ^[1] Se proporcionaron detalles adicionales en un artículo de revista posterior de 1987, ^[2]y los desarrolladores de Cornell lanzaron una versión de código abierto del protocolo en noviembre de ese año. Isis utilizó el protocolo principalmente para mantener la membresía de los grupos de procesos, pero también ofreció una API a la que los usuarios finales podían llamar directamente. La tecnología se volvió ampliamente utilizada a partir de 1988, cuando se comercializó el sistema Isis y se dispuso de soporte. El soporte comercial para el sistema terminó en 1998 cuando Stratus Computer, entonces la matriz de Isis Distributed Systems, se reorientó exclusivamente a las soluciones de hardware para la industria de las telecomunicaciones.

Ejemplos de sistemas que utilizaron Isis en entornos de producción incluyen la Bolsa de Valores de Nueva York, donde se empleó durante aproximadamente una década para administrar una infraestructura de informes configurable, tolerante a fallas y autorreparable para el piso de negociación, para transmitir cotizaciones e informes comerciales de los sistemas de "back office" utilizados por la central para la visualización del techo. El sistema de control de tráfico aéreo francés sigue utilizando Isis; desde 1996, el sistema se ha empleado para crear grupos de estaciones de trabajo tolerantes a fallas para que los utilicen los controladores de tránsito aéreo y para transmitir de manera confiable las actualizaciones de enrutamiento entre los centros de control de tránsito aéreo; con el tiempo, la tecnología francesa también ha sido adoptada por otros sistemas ATC europeos. El AEGIS de la Marina de los EE. UU. Ha utilizado a Isis desde 1993 para respaldar una infraestructura de comunicación confiable y autorreparable.Isis también tenía varios cientos de otros usuarios de producción en los ámbitos financiero, de telecomunicaciones, control de procesos, SCADA y otros dominios de infraestructura crítica. Se pueden encontrar más detalles en.^[3]

Planteamiento del problema

El problema fundamental resuelto por Gbcast es el siguiente: se nos da un conjunto inicial de miembros del grupo y deseamos admitir una abstracción de multidifusión, permitiendo que los miembros del grupo envíen mensajes que codifiquen varios comandos o solicitudes. El protocolo debe acordar los mensajes a entregar, y su orden, de modo que si algún miembro del grupo envía un mensaje, todos los miembros del grupo que no fallan recibirán ese mensaje y en el mismo orden con respecto a otros. mensajes entregados.

El conjunto de miembros del grupo cambia cada vez que un miembro falla o se une, y Gbcast también se utiliza para mantener la pertenencia al grupo mediante multidifusiones especiales que se envían a la aplicación como eventos de "nueva vista", pero que también ajustan la lista de miembros del grupo que se mantiene. por la biblioteca de protocolo Gbcast. Por tanto, la aplicación ve una serie de vistas de membresía que comienzan con una "vista inicial" cuando un miembro del grupo en particular se une, y luego evolucionan con el tiempo, y que se ordenan con respecto a otros eventos de cambio de vista y mensajes de multidifusión. Estas multidifusiones se entregan a todos los miembros que no han fallado enumerados en la vista durante la cual se programa la entrega, una propiedad que se conoce como sincronía virtual .

Las particiones de red pueden dividir un grupo en dos o más subgrupos disjuntos, creando el riesgo de un comportamiento de cerebro dividido , en el que algunos miembros del grupo toman una decisión (tal vez, lanzar el cohete) sin saber que alguna otra partición del grupo ha tomado una decisión diferente. , decisión contradictoria. Gbcast ofrece protección contra esta amenaza: el protocolo asegura que el progreso ocurra solo en una única partición primaria del grupo. Por lo tanto, si surge una partición de red, como máximo un subgrupo de miembros continuará operando, mientras que el otro seguramente se detendrá y se apagará.

Si un miembro fallido se recupera (o si un fallo de partición provocó que algún miembro se detectara incorrectamente como defectuoso y, por lo tanto, se elimine de la vista), después de que se restablezca la comunicación, ese miembro puede volver a unirse. Se usa un número de encarnación para evitar la ambigüedad: un contador que se incrementará cada vez que un proceso se une al grupo y se trata como parte del identificador del proceso. Cualquier tupla dada (ID de procesador, ID de proceso, número de encarnación) se une al grupo como máximo una vez, luego permanece en el grupo hasta que falla o se ve obligada a irse porque se agotó el tiempo de espera.

Cualquier sistema reconfigurable dinámicamente, incluidos Gbcast y Paxos, puede entrar en estados desde los que no es posible seguir avanzando. Por ejemplo, esto podría suceder si los procesos operativos se eliminan incorrectamente de la configuración y luego ocurren demasiados bloqueos reales dentro de los miembros restantes de la vista. En tales situaciones, la infraestructura de administración del centro de datos es responsable de reiniciar toda la aplicación. Esto contrasta con el comportamiento de los Paxos no reconfigurables ( vainilla ), que pueden tolerar interrupciones de duración ilimitada y luego se reanudarán una vez que haya suficientes miembros del grupo accesibles, sin la intervención de la infraestructura de gestión. Los siguientes términos se utilizan en la descripción detallada del protocolo.

Procesos

• Los procesos se ejecutan en procesadores que operan a una velocidad arbitraria.
• Los procesos pueden experimentar fallas de bloqueo (detención).
• Un proceso se identifica de forma única por una tupla de tres: (ID de procesador, ID de proceso, número de encarnación).
• Los procesos con almacenamiento estable pueden volver a unirse al protocolo después de fallas (siguiendo un modelo de falla de recuperación de fallas), luego de incrementar el número de encarnación.
• Los procesos no se confabulan, mienten o intentan de otra manera subvertir el protocolo. (Es decir, las fallas bizantinas ^[10] no ocurren).

La red

• Todos los procesos del sistema pueden enviar mensajes a todos los demás procesos del sistema.
• Los mensajes se envían de forma asincrónica: no hay límite de tiempo en la entrega de mensajes.
• Los mensajes se pueden perder, reordenar o duplicar.
• Los mensajes se entregan sin corrupción.

Estos son supuestos débiles: una red que nunca entrega ningún mensaje los satisfaría (diríamos que tal red está experimentando una falla de particionamiento completa y permanente ). Las condiciones de red necesarias para que Gbcast garantice el progreso se analizan a continuación. En la práctica, Gbcast se utiliza normalmente en centros de datos; estos tienen redes que pueden experimentar fallas transitorias, pero en las que las fallas de partición son raras y generalmente afectan solo a pequeños subconjuntos de los nodos. Por lo tanto, para fines de análisis, asumimos un entorno de red más severo que el que se produciría en las implementaciones reales.

Para simplificar la presentación, asumimos que se emplea un esquema de reconocimiento / retransmisión similar a TCP , creando la ilusión de un canal de mensajes confiable, secuenciado y no repetitivo entre cada par de procesos. Se produce un tiempo de espera si esta abstracción de canal vuelve a intentarlo repetidamente y no puede obtener un acuse de recibo para algún mensaje. Usando los mismos canales similares a TCP, también podemos admitir una capacidad de 1 a todos, mediante la cual un solo proceso envía algún mensaje a través de sus canales a todos los demás miembros de alguna vista de algún grupo. Esto se hace mapeando la solicitud 1 a todos en múltiples mensajes 1 a 1. Tenga en cuenta que estos canales de uno a todos carecen de garantía de atomicidad: si el remitente falla mientras se envía un mensaje, podría llegar solo a algunos de los destinos.

Grupos de procesos y vistas

Gbcast se define con respecto a un "grupo de procesos": un conjunto de procesos. En un sistema implementado, dicho grupo puede tener un nombre (como un nombre de archivo), una forma de contactar inicialmente al grupo y otros atributos, como parámetros de control de flujo. Sin embargo, este tipo de detalles se omiten aquí por brevedad.

El término vista de membresía es una lista de miembros, ordenados por rango por edad (determinada por la vista en la que cada miembro se unió al grupo más recientemente) y con lazos rotos por una regla de orden lexicográfico.

La pertenencia inicial al grupo la especifica un agente externo y define la primera vista de pertenencia del grupo.

Las vistas de membresía posteriores surgen al aplicar comandos de agregar y quitar y se identifican por el número de secuencia.

Las nuevas vistas se informan a los procesos que pertenecen a la vista mediante eventos de "nueva vista". La aplicación se notifica a través de una llamada ascendente (una llamada desde la biblioteca a un controlador definido por el programa de aplicación).

Mensajes de multidifusión

Los miembros de una vista pueden solicitar que los mensajes de multidifusión se envíen a un grupo de procesos sin conocer la membresía que se aplicará en el momento de la entrega.

El protocolo Gbcast realiza estas operaciones con una serie de garantías, que se comentan a continuación.

La entrega se realiza por llamada a la aplicación, que puede realizar cualquier acción que solicite el mensaje.

Roles

Gbcast se entiende mejor en términos de un conjunto de roles.

Solicitud

Una aplicación corresponde a un programa que se puede ejecutar en uno o más procesadores. Luego, cada proceso de solicitud se une a uno o más grupos de procesos.

Un proceso de aplicación que pertenece a un grupo inicia nuevas multidifusiones invocando Gbcast. Se considera que el protocolo ha terminado cuando todos los miembros del grupo objetivo han reconocido la entrega del mensaje o han sido detectados como defectuosos, a través de un mecanismo que se explica a continuación.

Los mensajes entrantes de Gbcast se envían a través de llamadas ascendentes, al igual que las notificaciones de cambio de vista.

Como se señaló anteriormente, los miembros de un grupo observan la misma secuencia de llamadas ascendentes comenzando cuando se unen inicialmente: una vista inicial y luego una secuencia de nuevas vistas y mensajes de multidifusión. Todos los miembros de un grupo reciben una multidifusión en particular en la misma vista, y la multidifusión se entrega a todos los miembros que no han fallado en esa vista.

Líder

El líder de un grupo se define con respecto a alguna vista del grupo y es el miembro con el rango más bajo en la vista. Como se señaló, el rango está ordenado por edad (los miembros mayores tienen un rango más bajo) y los lazos se rompen usando un tipo lexicográfico.

Detección de fallas

Todos los componentes del sistema pueden participar en la función de "detectar" fallas. La detección es distinta de la notificación de la falla (que se produce a través de una nueva vista y se ordena con respecto a las entregas de mensajes).

La abstracción de canal soportada por la capa de red detecta fallas por tiempos de espera. (Observe que, en el modelo de red, un proceso que intenta enviar un mensaje a un proceso de destino bloqueado siempre experimentará un tiempo de espera, pero también es posible que la abstracción del canal pueda informar erróneamente de un proceso operativo como defectuoso si los mensajes se retrasan debido a una falla. falla transitoria de partición).

Cualquier proceso que experimente un tiempo de espera puede declarar que el punto final del canal asociado ha fallado.

Si un proceso se entera de una falla para alguna tupla (ID de procesador, ID de proceso, número de encarnación), incluye esa información en el siguiente mensaje saliente en todos los canales.

Un proceso que considera que algún otro proceso ha fallado rechazará los mensajes de la encarnación fallida, respondiendo "has fallado". (Es decir, procesa chismes sobre fallas y evita a los miembros fallidos del grupo).

Un mensaje entrante de una nueva encarnación de un proceso fallido se trata como un mensaje de un proceso "nuevo".

Proceso fallido

Cualquier miembro de la vista actual que se haya detectado como fallido se considera un proceso fallido .

Un proceso operativo que aprende que se considera que ha fallado (al intentar comunicarse con algún otro proceso que rechaza el mensaje, "evitándolo" por lo tanto) puede salir del sistema, o puede aumentar su número de encarnaciones y volver a unirse.

Nuevo líder

Si cada proceso de menor rango en la vista actual es un proceso fallido, entonces el siguiente proceso no fallido de mayor rango se designa como el nuevo líder.

El nuevo líder debe ejecutar un protocolo, que se analiza a continuación, para convertirse en líder.

Quórumes

Los quórums se utilizan para garantizar las propiedades de seguridad de Gbcast asegurando que haya una única secuencia acordada globalmente de vistas de grupo y mensajes de multidifusión y evitando el progreso en más de una partición si un grupo se fragmenta en dos o más particiones (subconjuntos disjuntos de miembros que pueden comunicarse con otros miembros de sus subconjuntos, pero no con miembros de otros subconjuntos). Los quórumes se definen para una vista específica.

Dada la vista i con n miembros {A, B, C….}, Un quórum de la vista es cualquier subconjunto mayoritario de los miembros de esa vista. Tenga en cuenta que esto contrasta con la forma en que se define el término en los sistemas que tienen una membresía subyacente estática: para Gbcast, el tamaño del quórum cambiará con el tiempo a medida que cambia la membresía de un grupo y se definen nuevas vistas.

Propiedades de seguridad y vitalidad

Para garantizar la seguridad, Gbcast define tres propiedades de seguridad y garantiza que se mantengan, independientemente del patrón de fallas:

No trivialidad

Solo se entregan las multidifusiones realmente enviadas por algún miembro del grupo. Si un proceso recibe un mensaje de un miembro del grupo que considera que ha fallado, rechazará esos mensajes.

Consistencia

Si algún miembro de una vista entrega una multidifusión (o informa una nueva vista) en algún orden en relación con otras multidifusiones, entonces todos los demás miembros de la misma vista que entregan el mismo mensaje (o informan la misma vista) lo harán en el mismo pedido.

Vivacidad condicional

Si multidifusión M se envía en algún punto de vista y el remitente permanece operativo y, a continuación, finalmente, todos los miembros de ese punto de vista (con la excepción de cualquier accidente que se entregarán) M . La vida útil no se puede garantizar en todas las condiciones, por lo que imponemos una condición adicional: requerimos esta propiedad solo mientras que muchos procesos sigan sin ser defectuosos (discutiremos esto más adelante).

Gbcast básico

Este protocolo es el que se utiliza en condiciones normales.

Recuerde que en Gbcast, cada proceso operativo tiene una vista actual y cada vista define un líder. Sólo un proceso que se crea líder en la vista actual puede iniciar una nueva multidifusión; otros miembros deben retransmitir multidifusiones enviándolos al líder, a través de conexiones 1 a 1, y luego esperando que el líder ejecute el protocolo.

Si el líder falla mientras algún miembro que no es el líder está intentando retransmitir una multidifusión, el remitente debe determinar el estado de su solicitud pendiente. Esto se logra de la siguiente manera: Observe que los miembros observan la entrega de sus propias multidifusiones. En consecuencia, si se define una nueva vista en la que el líder anterior ha fallado, o bien se ha entregado la multidifusión (en cuyo caso el remitente lo sabe porque era uno de los receptores), o la entrega de la nueva vista le permite concluir que el líder no pudo transmitir el mensaje pendiente, y que debería ser reenviado pidiéndole al nuevo líder que lo transmita (no trivialidad).

Preparar paso

El líder propone alguna secuencia de uno o más mensajes de multidifusión utilizando la capa de red confiable de 1 a todos para enviar el mensaje o mensajes a los miembros de la vista más actual, identificando cada uno por medio de un número de secuencia entero. Los números de secuencia se restablecen a 1 a medida que se define cada nueva vista (a través de un tipo especial de multidifusión, como se explica a continuación). Un líder "habla consigo mismo", participando en el protocolo al igual que los demás miembros. Durante la recuperación (que se analiza a continuación), un nuevo líder puede volver a proponer alguna vista o mensaje propuesto previamente, ya que el nuevo líder intenta completar los protocolos que el antiguo líder podría haber comenzado pero no pudo completar. Cuando esto ocurre, el nuevo líder respetará la secuencia original y volverá a proponer la vista o el mensaje idénticos.

Paso de promesa

Cada destinatario conserva una copia de los mensajes y responde con la promesa de entregarlos (dicha promesa se cumplirá siempre que el destinatario siga siendo miembro de la vista de grupo, pero si el destinatario falla, es posible que la promesa no llevarse a cabo). Durante la recuperación, un destinatario puede recibir una solicitud de preparación duplicada para el mismo mensaje. Si se vuelve a proponer algún mensaje con el mismo número de secuencia, el destinatario simplemente repite su promesa.

Comprometerse paso

El líder recopila mensajes de promesa hasta que, para cada miembro del grupo, tiene un mensaje de promesa o se ha producido un tiempo de espera que hace que el líder sospeche que el miembro correspondiente es defectuoso (recuerde que en este último caso, el líder evitará al miembro sospechoso , y debido a que el subsistema de envío de mensajes lleva esta información a cuestas en los siguientes mensajes que envía, cualquier proceso que reciba un mensaje posterior del líder también comenzará a evitar a estos nuevos miembros sospechosos).

Si el líder recibe promesas de un quórum de miembros, según se define con respecto a la vista en la que está ejecutando el protocolo, envía una solicitud de confirmación . Si el líder carece de quórum y, por lo tanto, sospecha de más de la mayoría de los miembros del grupo, nunca más podrá progresar y, por lo tanto, el líder termina (el programa de aplicación puede volver a unirse al grupo usando un nuevo nombre de proceso, pero más progreso por este proceso en la vista anterior, bajo el nombre de proceso anterior, es imposible).

Tenga en cuenta que el líder también puede haberse enterado de fallas durante la fase de preparación o la fase de propuesta.

En la fase de preparación, es posible que algunos miembros de la vista no hayan reconocido la solicitud propuesta, en cuyo caso el canal del líder a esos miembros habrá experimentado tiempos de espera. El líder los habrá marcado como miembros fallidos.

Además, puede darse el caso de que al recibir los mensajes de promesa en la fase de promesa, el líder se haya enterado de miembros fallidos que fueron detectados por otros miembros del grupo. Por lo tanto, al comienzo de la fase de confirmación, el líder tiene un quórum de promesas junto con una lista posiblemente vacía de miembros de vista fallidos.

Por lo tanto, el líder envía el mensaje "Confirmar" a los miembros no fallidos de la vista, junto con una propuesta para un evento de cambio de vista que eliminará los miembros fallidos de la vista, combinando así un paso de confirmación y un paso propuesto. en una sola acción. Recuerde que después de que se produzca la detección de fallas, el primer mensaje para cada miembro del grupo incluirá esa información de detección de fallas y que los miembros evitan a los miembros fallados. Por lo tanto, los miembros que se enteran de una falla comienzan instantáneamente a evitar a los miembros fallidos, y el líder da el paso adicional de iniciar un protocolo de cambio de vista (que luego tomará algún tiempo en completarse).

Si una propuesta cambió la vista agregando miembros, el líder envía la nueva vista a los miembros que se unen; se convierte en su vista inicial, y luego pueden participar en cualquier ejecución posterior del protocolo.

Durante la recuperación, un participante puede recibir una confirmación duplicada para un mensaje confirmado previamente. Si es así, entra en la fase de entrega, pero no vuelve a enviar el mensaje ni lo ve a la aplicación.

Paso de entrega

Si un miembro recibe un mensaje de confirmación, envía los mensajes asociados o las nuevas vistas a la aplicación, en el orden en que fueron propuestos por el líder. El líder se entera de que este paso ha tenido éxito cuando se reciben los reconocimientos utilizados por el canal confiable 1 a 1.

Flujo de mensajes: Gbcast básico, caso más simple

(Tamaño de quórum = 2, vista1 = {A, B, C})

Capa de solicitud de miembros líderes de miembros AABCABC | | | | | | | | X --------> | | | | | | | Solicite que el líder envíe una multidifusión M | X ---------> | -> | -> | | | | Proponer (1.1: M) (Vista 1, secuencia 1, mensaje M) | | <--------- X - X - X | | | Promesa (1.1) | X ---------> | -> | -> | | | | Comprometerse (1.1) | | <---------X--X--X------> M-> M-> M Comprometido (1.1); Entrega M | | | | | | | |

Casos de error en Gbcast básico

Los casos de error más simples son aquellos en los que uno o más miembros fallan, pero el quórum permanece activo. En el siguiente ejemplo, el grupo consta de {A, B, C} con A desempeñando el papel de líder. C falla durante la fase de promesa y un tiempo de espera se produce dentro del canal fiable del líder de proceso C . Por lo tanto, el líder compromete la entrega de M, pero simultáneamente inicia un protocolo para eliminar a C del grupo, que se compromete, creando la nueva vista {A, B}. Si C no ha fallado realmente, ahora puede reincorporarse al grupo pero con un nuevo número de encarnación: en efecto, C debe reincorporarse como C '. Cualquier mensaje de C a A o B será rechazado desde el instante en que cada uno se entere de la aparente falla: C será rechazado por A y B.

Flujo de mensajes: Gbcast básico, falla de un miembro que no sea el líder

(Tamaño de quórum = 2, vista1 = {A, B, C})

Capa de solicitud de miembros líderes de miembros AABCABC | | | | | | | | X --------> | | | | | | | Solicitud (M) | X ---------> | -> | -> | | | | Proponer (1.1: M) | | | | * | | * !! C FALLAS !! | | <--------- X - X | | Promesa (1.1) | X ---------> | -> | | | Comprometerse (1.1); Proponer (1.2: "eliminar C") | | <---------X--X---------> M-> M Comprometido (M); Entrega M; Promesa (1.2) | X ---------> | -> | -> | | | Comprometerse (1.2); | | <---------X--X--X------> V-> V Comprometido (1.2); Entrega vista2 = {A, B} | | | | | |

Tenga en cuenta que el compromiso y la nueva propuesta (y la notificación de error superpuesta) se combinan en un solo mensaje. Esto asegura que cualquier proceso que comete una acción después de que se haya detectado una nueva falla, aprenda simultáneamente de esa falla y evitará el proceso asociado, y que el proceso se eliminará rápidamente de la vista. Si C no se ha bloqueado, puede volver a unirse aumentando su número de encarnación (por lo que ahora se llama C ') y luego solicitando que el líder lo agregue nuevamente al grupo. Se agregará a la lista de miembros con su nuevo nombre y tendrá el rango más alto (porque es el miembro más joven) entre los miembros de la vista.

Flujo de mensajes: Gbcast básico, agregar miembros {D, E, F}, falla de un miembro que no sea el líder

En el ejemplo que se muestra a continuación, a un grupo que inicialmente contiene miembros {A, B, C} se le pide que agregue {D, E, F}, pero el miembro C falla durante el protocolo. Las solicitudes de cambio de membresía se tratan como un tipo especial de multidifusión y la secuencia de eventos es la misma. Por lo tanto, el ejemplo es casi idéntico al anterior, pero ahora se entregan a la aplicación una serie de nuevos eventos de vista. (Tamaño de quórum = 2, vista1 = {A, B, C})

Capa de solicitud de miembros líderes de miembros AABCDEFABCDEF | | | | | | | | | | | X --------> | | | | | | | | | | Solicitud ("agregar D, E, F") | X ---------> | -> | -> | | | | | | | Proponer (1.1: "agregar D, E, F") | | | | * | | * | | | !! C FALLAS !! | | <--------- X - X | | | | | Promesa (1.1) | X ---------> | -> | | | | | | Comprometerse (1.1); Proponer (2.1: "eliminar C") | | <---------X--X-----X--X--X------> V-> V ----> V-> V-> V Comprometido (1.1); Entregar vista2 = {A, B, C, D, E, F}; Promesa (2.1) | X ---------> | -> | ----> | -> | -> | | | | | | Comprometerse (2.1) | | <---------X--X-----X--X--X------> V-> V ----> V-> V-> V Comprometidos (2,1); Entregar vista3 = {A, B, D, E, F} | | | | | | | | | | | |

Al final del protocolo, la nueva vista activa es view3 = {A, B, D, E, F} y el nuevo tamaño de quórum es 3. Pero observe que había una vista "intermedia", view2 = {A, B , C, D, E, F} con un tamaño de quórum de 4. Si el líder no hubiera recibido 4 promesas para la fase de propuesta que eliminó C, no habría podido ejecutar la fase de confirmación para view3. Esto ilustra una política básica: el quórum necesario para confirmar una nueva vista siempre se basa en el tamaño de la vista anterior.

Protocolo de adquisición, utilizado cuando el líder falla

El siguiente caso de fracaso es cuando un líder falla, lo que resulta en un nuevo líder. Para asumir el cargo de líder, el nuevo líder primero ejecuta un protocolo de adquisición, y luego el nuevo líder puede ejecutar Gbcast básico como se indicó anteriormente. El protocolo de adquisición es el siguiente:

Paso de consulta

El nuevo líder envía un 1-a- n mensaje de interrogar a los miembros que no podido aprender de los mensajes que han prometido entregar.

Paso de lista de promesas

Cada destinatario envía la lista actual de mensajes prometidos al líder. Si un destinatario carece de su vista inicial, envía una solicitud de vista inicial al líder.

El nuevo líder espera hasta que haya recibido una lista de promesas de cada uno de los miembros con los que se puso en contacto o hasta que haya agotado el tiempo. Si se produce un tiempo de espera, el nuevo líder sospecha del miembro en cuestión y lo evitará, al igual que cualquier otro miembro con el que contacte. Finalmente, propondrá una opinión que excluya a estos miembros rechazados, como se explica más adelante.

Repita si es necesario

El nuevo líder examina la lista de promesas en busca de mensajes de cambio de membresía que agreguen nuevos miembros. Si alguno está presente, itera la fase de consulta y la fase de recopilación de la lista de promesas, enviando consultas a los nuevos miembros. Esto, a su vez, podría conducir al descubrimiento de propuestas adicionales que sumen aún más miembros. El proceso termina cuando cada miembro (actual o propuesto para ser agregado) ha respondido con una lista de promesas o ha sido sospechoso por el nuevo líder.

Comprobar quórumes

Al final de la fase de investigación, el líder ha recibido respuestas de lista de promesas de algunos de los procesos con los que se puso en contacto; ahora se sospechará de cualquier miembro que no responda. El nuevo líder construye una lista de vistas propuestas. Para avanzar al siguiente paso de la propuesta de adquisición, el nuevo líder debe haber recibido un quórum de respuestas de cada uno de los puntos de vista comprometidos o propuestos en esta lista. Si no ha recibido un quórum de respuestas para cualquier punto de vista comprometido o propuesto en la lista, el nuevo líder no ha podido asumir el cargo de líder y nunca tendrá éxito. Termina el protocolo y debe volver a unirse al sistema como un nuevo miembro, utilizando un nuevo número de encarnación de proceso.

Comience como nuevo líder

Habiendo verificado con éxito los quórumes, el nuevo líder se convierte en líder. Ahora puede ejecutar el protocolo básico. Vuelve a proponer los mensajes prometidos o los cambios de vista, en el orden en que los aprendió de las listas de promesas, siguiéndolos con un nuevo comando de cambio de vista que elimina al antiguo líder y a cualquier otro miembro que no haya respondido durante la fase de consulta. . Si algún miembro respondió, durante la fase de lista de promesas, que carece de su vista inicial, el nuevo líder envía la vista inicial apropiada a ese miembro.

Líderes en duelo

Es posible que las listas de promesas incluyan dos o más propuestas distintas para el mismo espacio. Esto sucede (solo) si un primer líder A se separó del sistema, pero no obstante hizo una propuesta X que fue vista solo por un pequeño grupo de miembros (sin quórum). Entonces, un nuevo líder B asumió el mando con éxito, pero no se enteró de la propuesta de A (que no puede haberse comprometido). B ahora propone Y, de nuevo a una pequeña minoría de miembros. Ahora se cree que B ha fallado y C se hace cargo. Es posible que C conozca las propuestas X e Y, para el mismo espacio. C debe ignorar la propuesta asociada con el líder más antiguo, A, pero retener la propuesta asociada con el líder más nuevo, B: en esta situación, la propuesta Xno puede haber logrado un quórum y, por lo tanto, no puede haberse comprometido, mientras que la propuesta Y, hecha por el líder más reciente, podría haberse comprometido (de lo contrario, es decir, si X podría haber alcanzado un quórum, B se habría enterado y, por lo tanto, repitió la propuesta X; por lo tanto, debido a que B no se enteró de X , X no debe haber recibido quórum).

Tenga en cuenta que el protocolo de toma de control de C utiliza un orden determinista entre los líderes A y B para determinar que la propuesta X está condenada al fracaso, porque el líder B debe haber evitado a A para convertirse en líder. A la inversa, C debe asumir que la propuesta Y puede llegar a ser comprometida, incluso si A sospecha que B ha fallado, porque la propuesta Y se cruzó con el paso de traspaso de C. La regla se implementa: numerando los líderes secuencialmente e incluyendo el número de líder en la propuesta. Durante el paso de consulta, un nuevo líder puede usar la propuesta del líder con el número mayor, si recibe propuestas en conflicto para el mismo espacio.

Sospechas de fallas a cuestas en los mensajes salientes

Observe que el nuevo líder cree que el antiguo líder ha fallado y también puede creer que otros miembros han fallado. Por lo tanto, la fase de consulta y la nueva fase de propuesta también pueden llevar mensajes de falla acumulados para uno o más miembros.. Este es un requisito central para el protocolo, porque asegura que esos miembros serán posteriormente rechazados: si se recibe más comunicación de un miembro rechazado, el receptor rechazará esos mensajes. De ello se deduce que si algún miembro ejecuta la fase de lista de promesas para un antiguo líder L, ese miembro no procesará más mensajes de propuesta o compromiso de L. A partir de esto, podemos ver que la lista de promesas recopilada por el nuevo líder estará completa y contendrá todos los mensajes prometidos que posiblemente podrían haber alcanzado un quórum en la vista actual. También puede contener algunos mensajes prometidos adicionales que aún no han alcanzado el quórum.

Flujo de mensajes: Gbcast básico, falla del líder, TakeOver, Gbcast básico del nuevo líder

(Tamaño del quórum = 2, vista 1 = {A, B, C})

Capa de solicitud de miembros líderes de miembros ABABCABC | | | | | | | | X -----> | | | | | | | Solicitud (M) | X ------------> | -> | | | | | Proponer (1.1: M) !! ¡El líder falla durante el envío, la propuesta no llega a C! | * <------------ X —- X | | | | Promesa (1.1) | | * | | * | | !! ¡¡UN (EL LÍDER) HA FALLADO !! | | | | | | !! NUEVO LÍDER: ¡¡B !! | ? ------------> | -> | | | Preguntar ("B se hace cargo porque A ha fallado") | | <------------ X - X | | PromiseLists (1.1: M) | X ------------> | -> | | | Proponer (1.1: M); Proponer (1.2: "eliminar A") | | <------------X--X---------> | | Promesa (1.1); Promesa (1.2) | X ------------> | -> | ---------> | | Comprometerse (1.1); Comprometerse (1.2); | | <------------X--X--------> M; V-> M; V Comprometido (1.1); Comprometidos (1,2); Entrega (M). Entrega vista2 = {B, C}

Flujo de mensajes: Gbcast básico, agregar miembros {D, E, F}, falla del líder

Como ejemplo de un caso más complejo, aquí el líder falla en medio de un compromiso que aumenta el tamaño de la vista.

(Tamaño del quórum = 2, vista 1 = {A, B, C})

Capa de solicitud de miembros líderes de miembros ABABCDEFABCDEF | | | | | | | | | | | | | | X -----> | | | | | | | | | | | | | Solicitud ("agregar D, E, F") | X ------------> | -> | | | | | | | | | | | Proponer (1.1) !! ¡El líder falla durante el envío, la propuesta no llega a C! | * <------------ X —- X | | | | | | | | | | Promesa (1.1) | | * | | | | | * | | | | | !! ¡¡UN (EL LÍDER) HA FALLADO !! | | | | | | | | | | | | !! NUEVO LÍDER: ¡¡B !! | ? ------------> | -> | | | | | | | | | Preguntar ("B se hace cargo porque A ha fallado") | | <------------ X - X | | | | | | | | PromiseLists (1.1: "agregar D, E, F"); | ? ------------- | - | -> | -> | -> | | | | | | Consulta iterada ("B se hace cargo porque A ha fallado") | | <------------ | - | --X - X - X | | | | | PromiseLists (1.1: "agregar D, E, F"); | X ------------> | -> | -> | -> | -> | | | | | | Proponer (1.1: "agregar D, E, F"); Proponer (2.1: "eliminar A") | | <------------ X - X - X - X - X | | | | | Promesa (1.1); Promesa (2.1); | X ------------> | -> | -> | -> | -> | | | | | | Comprometerse (1.1); Comprometerse (2.1); | | <------------X--X-> X-> X-> X --------> V-> V-> V-> V-> V Comprometido (1,1); Comprometidos (2,1); Entrega vista2 = {A, B, C, D, E, F}. Entrega vista3 = {B, C, D, E, F}

En este ejemplo, vemos la iteración de la consulta "en acción": B aprende del protocolo que agrega {D, E, F} en una primera fase de la consulta, por lo que repite la consulta, esta vez contactando a D, E y F. No es necesario repetir la consulta en C, ya que esto simplemente devolvería la misma información obtenida anteriormente.

En este ejemplo, el compromiso final en realidad hace que se entreguen dos vistas en sucesión en los miembros B y C.Aunque las dos propuestas se enviaron al mismo tiempo, el compromiso de view2 requiere una promesa de un quórum de view1, mientras que el compromiso de view3 requiere una respuesta de quórum de los miembros de view2. Aunque el envío de vistas iniciales no se muestra explícitamente en el diagrama, los miembros que se unen no participan en el protocolo 1.1 porque no se unen al grupo hasta la vista2. Observe que en los miembros B y C surge un efecto de canalización: los eventos asociados con view2 ya se están proponiendo incluso cuando los eventos en view1 todavía se están comprometiendo.

Exactitud

Para mostrar que Gbcast satisface la no trivialidad, comenzamos rastreando hacia atrás desde una acción de entrega arbitraria hasta el punto en el que un cliente solicitó el evento correspondiente; Claramente, solo se entregarán los mensajes que se enviaron legítimamente. Sin embargo, la no trivialidad de este protocolo va más allá: también debemos mostrar que los mensajes de un miembro dado se entregan solo mientras ese miembro todavía es un participante en vivo en alguna vista. En consecuencia, analizamos el caso en el que el líder inicia una multidifusión pero luego falla antes de que se entregue. Aquí, el nuevo líder descubre la propuesta pendiente y la ordenará antes del evento de cambio de vista, o el nuevo líder no descubre la propuesta pendiente, en cuyo caso todos los miembros de la nueva vista evitarán cualquier mensaje entrante que llegue tarde. del viejo líder.Por lo tanto, se entrega un mensaje de multidifusión mientras la vista en la que se envió aún está pendiente, o no se entregará en absoluto.

Para establecer la coherencia comenzamos por el análisis del caso en el que solo hay un líder que nunca falla o pierde la conectividad con un quórum. Dado que el líder secuencia los eventos e incluye a cada miembro comenzando con la primera vista que contiene ese miembro, todos los miembros envían mensajes idénticos a partir de la vista en la que se agregaron al sistema.

Cuando un nuevo líder asume el cargo, se requiere la investigación para alcanzar un quórum de miembros para el punto de vista comprometido más reciente. Este quórum necesariamente incluirá al menos un proceso que recibió alguna propuesta que el antiguo líder pudiera haber comprometido. Así, el nuevo líder conocerá cualquier propuesta potencialmente comprometida y la incluirá como prefijo de sus propias nuevas propuestas. De ello se desprende que si algún proceso entrega algún evento, entonces si el sistema avanza, cada miembro superviviente eventualmente entregará ese mismo evento y en el mismo orden.

Podemos demostrar que un miembro que se une recibirá su vista inicial mediante el análisis de los dos casos relevantes. Si el líder no falla, envía la vista inicial en un canal eventualmente confiable. Si el líder falla y algún miembro carece de su punto de vista inicial, el nuevo líder envía ese punto de vista después de recibir la respuesta de la "lista de promesas" a su mensaje de la fase de consulta.

Una partición lógica del grupo es imposible debido a la regla de rechazo. Para comprometer cualquier punto de vista nuevo, el líder anterior debe obtener promesas de un quórum del punto de vista actual. Un nuevo líder, que asuma el mando, conocerá cualquier punto de vista que pudiera haberse comprometido. Por lo tanto, para comprometer su propia vista siguiente propuesta, será necesario interactuar con un quórum de esa vista intermedia, si lo hubiera. En un escenario que podría llevar a la partición, el líder, A, podría haber agotado el tiempo de espera en B y haber creado una secuencia de nuevas vistas y eventos que excluyeron a B. Pero en este caso, la mayoría de las vistas antiguas o intermedias. los miembros habrán aprendido que A cree que B ha fallado y evitarán a B cuando pregunte. En cualquier caso, B no puede obtener quórum y, por lo tanto, no puede avanzar.Un argumento simétrico muestra que si B tiene éxito en definir un nuevo punto de vista que excluya a A, A no podría obtener quórum para cualquier otro punto de vista nuevo que pudiera intentar proponer.

Vivacidad

El protocolo Gbcast avanzará siempre que en todo momento de la ejecución, si la vista v se mantiene en el tiempo t , entonces menos de un quórum de miembros de v fallan (o se sospecha que fallan) dentro de algún subconjunto de los miembros de la vista. Para maximizar el progreso, es importante que los miembros excluidos pero aún activos se reúnan al grupo, de modo que las detecciones de fallas erróneas no hagan que la vista se reduzca de manera persistente. Sin embargo, el protocolo no se recuperará ni avanzará si en algún momento, cada proceso sospecha que más de un quórum de miembros de la visión actual ha fallado.

Esta propiedad es similar pero "más fuerte" que <> W, el "detector de fallas más débil" para lograr consenso, según lo definido por Chandra y Toueg. Para ver esto, considere una ejecución en la que surge un quórum de sospecha mutua "demasiado rápido" para que los procesos que se han excluido erróneamente de la vista se reincorporen a él. Gbcast no progresará y, de hecho, el grupo deberá cerrarse y reiniciarse.

Podría decirse que tales ejecuciones serían poco probables en los tipos de centros de datos donde se usa típicamente Gbcast, pero claramente se pueden construir de manera contradictoria.

Discusión: detección de fallas

El protocolo Gbcast supone que la probabilidad de sospechas de fallas incorrectas será baja; el esquema falla si ocurren sospechas de fallas con frecuencia y a menudo se sospecha que los procesos operativos son defectuosos. Por analogía, considere el protocolo TCP , en el que la falta de recepción de un acuse de recibo provocará eventualmente la interrupción de la conexión. TCP se usa casi universalmente, una tremenda interrupción en la Web resultaría si las conexiones TCP se rompieran con frecuencia cuando ninguno de los extremos ha fallado. Por lo tanto, los tiempos de espera se establecen de forma conservadora. Se requiere una suposición similar para los sistemas que utilizan Gbcast.

Por el contrario, existen otros esquemas de detección de fallas, como el explorado por Chandra y Toueg, que pueden producir altas tasas de sospechas de fallas incorrectas. Algunos protocolos, incluido Paxos, pueden tolerar sospechas de fallas incorrectas sin consecuencias costosas. Si un enfoque es intrínsecamente mejor que el otro está más allá del alcance de esta discusión. Simplemente subrayamos que los enfoques difieren y que Gbcast sería ineficaz si los tiempos de espera se establecen de manera demasiado agresiva.

Un escenario extremo merece una mención adicional: los eventos de partición de red. Los centros de datos y las redes modernos a menudo experimentan eventos en los que una sola máquina y todos los procesos en ella se particionan transitoriamente de un grupo más grande de máquinas que permanecen conectadas entre sí. Dichos casos se tratan como fallas en Gbcast, pero si los miembros supervivientes conectados incluyen un número suficientemente grande de procesos, la mayor parte del sistema simplemente se reconfigurará para excluir al miembro desconectado. Puede volver a conectarse y volver a unirse al grupo más tarde cuando la partición se recupere.

A veces se observa un tipo más extremo de particionamiento en los centros de datos: en esta situación, un conmutador de red puede fallar, provocando que una colección de máquinas (tal vez, un bastidor completo o incluso un contenedor completo) se desconecte de Internet y del resto del centro de datos. En tales casos, uno podría imaginar un grupo en el que todos los miembros comienzan a sospechar de todos los demás miembros; Gbcast no progresará en este caso y la infraestructura de administración necesitaría reiniciar toda la aplicación. Por otro lado, en la mayoría de los grandes centros de datos, los sistemas operativos de las máquinas que experimentan tal falla también se apagan y se reinician solo cuando se restablece la conectividad. Por tanto, en la práctica, el reinicio del sistema es inevitable. Dicho esto, existen protocolos, como Paxos,eso podría sobrellevar tal interrupción si las máquinas mismas permanecieran operativas y luego recuperaran la conectividad adecuada.

El sistema Transis exploró extensiones del protocolo Gbcast que permiten que se formen múltiples particiones, que progresen de forma independiente y luego vuelvan a fusionarse. Este tema, sin embargo, está más allá del alcance de la presente discusión.

Discusión: Líderes en duelo

En el protocolo de Paxos, puede surgir una situación en la que dos o más líderes se "duelan" proponiendo diferentes comandos para el mismo espacio. Esto también puede ocurrir en Gbcast.

En la secuencia normal de eventos, un líder asume el cargo porque el líder anterior ha fallado, se entera de las propuestas que hizo el líder anterior durante la fase de investigación y luego repite esas mismas propuestas, ampliadas con otras nuevas. Así no surge ningún duelo por el contenido de las tragamonedas porque las mismas propuestas se repiten en las mismas tragamonedas.

La situación más cercana a un duelo se ve si el antiguo líder se ha separado de la mayoría y el nuevo líder, que se hace cargo, no puede contactar con algún grupo de miembros (pero obtiene el quórum requerido durante la fase de CONSULTA). En este caso, el nuevo líder puede desconocer algunas propuestas que hizo el antiguo líder, o aún podría emitir, si solo llegan a los miembros con los que el nuevo líder no se puso en contacto.

El mecanismo de huida resuelve tales duelos. Cuando el nuevo líder obtuvo quórum durante la fase de INVESTIGACIÓN, también impidió que el antiguo líder volviera a lograr quórum para cualquier nuevo PROPÓSITO que pudiera iniciar: la mayoría de los miembros ahora rechazan al antiguo líder. Por lo tanto, si el nuevo líder pasa por alto alguna propuesta, es necesariamente una propuesta que no alcanzó un quórum de miembros y no alcanzará un quórum en el futuro. Además, los miembros que conozcan tal propuesta serán rechazados por el nuevo líder, ya que (cuando dejó de esperar a que respondieran a su CONSULTA) considera que han fracasado. Cualquier miembro que se entere de nuevas propuestas del nuevo líder las rechazará también.

El rechazo de líderes en Gbcast ocurre en el orden predeterminado de rangos de líderes: un líder de rango superior solo evita a un líder de rango inferior cuando intenta tomar su lugar. El mecanismo de papeletas de Paxos sirve precisamente para el mismo propósito, pero difiere en permitir que los participantes intenten hacerse cargo repetidamente, cada vez asumiendo una nueva papeleta ("rango"). El resultado es que, por un lado, la degradación del líder de Paxos es reversible y, por el otro, los líderes en duelo teóricamente podrían continuar para siempre.

Equivalencia de bi-simulación a Paxos

Aunque superficialmente es bastante diferente, tras un estudio detenido, se ve que Gbcast es sorprendentemente similar a Paxos. De hecho, Paxos se puede "transformar" en Gbcast con la siguiente secuencia (reversible) de pasos. Por brevedad, describimos estos pasos de manera informal y omitimos una prueba detallada.

Tenga en cuenta que esta transformación no se ocupa de la durabilidad. Gbcast trata el estado duradero como una propiedad de la aplicación, no del protocolo, mientras que Paxos registra eventos en un conjunto de registros de comandos duraderos y, por lo tanto, aún puede recuperar su estado incluso después de que todo el servicio se apaga y reinicia. El comportamiento equivalente con Gbcast implica que la aplicación registre todos los mensajes recibidos, pero ese caso no se considerará aquí.

1. Comience con el protocolo básico de Paxos . Agregue un número de encarnación de proceso para distinguir un proceso de reincorporación de uno que ha sido continuamente miembro de la vista. Imponer un orden basado en la edad a los miembros del grupo, designar al miembro de mayor edad (rompiendo lazos lexicográficos) como líder. Los no líderes emiten solicitudes a través del líder.
2. Ambos protocolos permiten el procesamiento por lotes de solicitudes: Basic Paxos tiene un parámetro de concurrencia, alpha: un líder puede ejecutar simultáneamente un máximo de instancias alfa del protocolo. Gbcast permite al líder proponer múltiples eventos en una sola instancia de protocolo, que pueden ser entregas de mensajes o eventos de visualización.
3. Paxos normalmente no requiere una comunicación ordenada y confiable. Modifique el protocolo para que se ejecute en la abstracción confiable de canales uno a uno (Paxos enviaría un mensaje uno a muchos a través de un conjunto de canales uno a uno). Ahora podemos asumir que cualquier mensaje enviado será recibido y entregado en orden, o que ocurrirá un tiempo de espera en el lado del remitente.
4. El número de ranura de Paxos se convertirá en el número de secuencia de Gbcast. El número de votación de Paxos se transforma, en efecto, en el número de líder proponente que se utiliza para discriminar entre propuestas en conflicto durante el paso de consulta.
5. Defina una categoría de comandos de modificación de vista que operan agregando o quitando procesos de la membresía del grupo. Introduzca un mecanismo de detección de fallas como se usa en Gbcast, pidiendo al líder que elimine cualquier miembro que haya agotado el tiempo de espera. Un miembro eliminado del grupo que restablece la conectividad con el grupo debe volver a unirse con un nuevo número de encarnación. Informar de las visualizaciones por llamadas ascendentes a la aplicación.
6. Basic Paxos puede proponer una multidifusión a solo un quórum de miembros del grupo, por lo tanto, un miembro típico puede tener huecos en su lista de comandos. Por eso, en Paxos, un alumno debe leer un quórum de miembros y fusionar sus listas de comandos. En nuestro protocolo modificado, cualquier multidifusión se propone a todos los miembros no fallidos, mientras que los miembros fallidos se eliminan de la vista. Por lo tanto, a diferencia de Paxos, nuestro protocolo modificado tiene la propiedad de que cualquier miembro en vivo tiene la lista completa de eventos comprometidos. En efecto, el protocolo tiene un quórum de escritura igual al tamaño de la vista de membresía actual y un quórum de lectura de 1. Esto puede ser conveniente cuando se crean aplicaciones que mantienen el estado real de una base de datos u objeto y para las que es inconveniente representar el estado. como una serie de actualizaciones en las listas de comandos que deben fusionarse para conocer la secuencia real de eventos.

Los mismos mecanismos de quórum que definen a Paxos, incluida la consulta que se utiliza cuando un nuevo líder de Paxos asume el cargo, ahora se corresponden precisamente con los pasos de Gbcast. El mecanismo de votación, generalmente visto como el sello distintivo de los protocolos de Paxos, se reduce a un contador que rastrea el orden de sucesión de los líderes. Esta simplificación se debe fundamentalmente a la garantía de que una vez que se sospecha de un líder, este será eliminado de la vista y deberá reincorporarse antes de participar en el protocolo.

De ello se deduce que Gbcast y Paxos se pueden transformar, entre sí, sin cambiar los supuestos y con las mismas propiedades de corrección. Obviamente, los protocolos no se parecen mucho, pero tienen una conexión profunda. De hecho, se puede hacer una afirmación más fuerte: cualquier secuencia de eventos de entrega exhibida por Gbcast también puede surgir en alguna ejecución de Paxos, y viceversa: cualquier secuencia de eventos aprendidos de Paxos también puede surgir en alguna ejecución de Gbcast.

El tipo de prueba descrito anteriormente se denomina formalmente bi-simulación: una muestra que cualquier par (entrada-secuencia, salida-comportamiento) que un protocolo puede exhibir también es posible con el otro protocolo. Observe que al llevar a cabo una bisimulación, las características que admite un protocolo pero que el otro carece pueden ignorarse si no se consideran parte del "comportamiento" que se está estudiando. Por ejemplo, los informes de Gbcast de nuevas vistas (eventos de los que carece Paxos) no se tratan como eventos de salida aquí.

Resumen de diferencias entre Paxos y Gbcast

• Gbcast no tiene un estado duradero: el protocolo no mantiene un registro de eventos en el disco y la durabilidad se trata como una propiedad específica de la aplicación. Por el contrario, Paxos garantiza la durabilidad: después de recuperarse de un apagado completo del sistema, una aplicación de Paxos aún podrá aprender el registro completo de los mensajes recibidos.
• En la fase propuesta, Gbcast debe esperar las respuestas de todos los participantes (o el tiempo de espera máximo y luego sospechar de los restantes), en lugar de avanzar con el quórum más rápido. En Gbcast, el costo de una sospecha de falla es alto y el protocolo puede dejar de avanzar si se sospecha de demasiadas fallas, lo que obliga a una capa de administración a reiniciar todo el grupo de aplicaciones. Por lo tanto, en la práctica, Gbcast requiere configuraciones de tiempo de espera conservadoras en relación con Paxos.
• Con Gbcast, si se produce un error (por ejemplo, se sospecha y se rechaza un proceso operativo), ese proceso debe abandonar (puede volver a unirse con un nombre diferente). Con Paxos, si f> 0, si un proceso no puede participar en una instancia de protocolo, puede continuar participando en instancias de protocolo posteriores sin errores.
• Los miembros operativos de una vista nunca tendrán huecos en sus listas de comandos con Gbcast (cada miembro tiene un estado completo). Los miembros operativos pueden tener lagunas en sus listas de comandos cuando usan Paxos (los estudiantes fusionan un quórum de listas en Paxos para "llenar" estas lagunas).
• Con Paxos, para proponer múltiples comandos usamos alfa> 1, pero en este caso los comandos pueden ser cometidos en un orden diferente al orden en el que fueron iniciados (un caso en el que se ve este escenario problemático involucra a líderes en duelo; el líder A propone comandos a1 y a2, y el líder B propone los comandos b1 y b2; ambos fallan y el líder C, asumiendo el control, termina cometiendo b2, y luego a1: un resultado que podría no ser deseado por las aplicaciones que iniciaron las solicitudes ^[11] ). Con Gbcast, el líder puede iniciar múltiples comandos emitiendo una única propuesta que describe una serie de acciones. El grupo se comprometerá de una vez, de ahí que se respete el orden de iniciación.
• Con Gbcast, se entrega un comando en la vista en la que se inició. Paxos reconfigurable puede enviar un comando en un espacio asociado con una vista de membresía antes de la vista de membresía activa en el momento en que ocurre el compromiso. Por lo tanto, en Paxos, si una aplicación es de alguna manera sensible a la vista, los comandos deben llevar un identificador de vista, de modo que los destinatarios puedan determinar si el comando aún es ejecutable o no.
• Gbcast no requiere que el protocolo se detenga cuando se cambian las configuraciones: la tasa de nuevas propuestas puede ser constante incluso en los cambios de membresía. Para muchas implementaciones de Paxos reconfigurables, este no sería el caso.
• Tanto con Gbcast como con Paxos, la reconfiguración solo es posible si un quórum de la vista anterior es accesible y puede reconocer la nueva vista. Sin embargo, en Paxos, el requisito también se extiende al aprendizaje de los resultados de los comandos propuestos para los espacios asociados con la vista anterior. En la práctica, esto puede hacer que el cálculo de reconfiguración de Paxos se extienda durante un período más largo que para Gbcast, en el que cualquier estado se almacena dentro de la aplicación, no una lista de comandos de larga duración: Paxos no puede descartar el estado asociado con una vista anterior hasta que la nueva vista está activa y las réplicas han aprendido el estado anterior.
• Gbcast no requiere un protocolo de recolección de basura porque, a medida que cada mensaje o vista se confirma y se informa a la aplicación, se puede descartar. Paxos mantiene el estado utilizando un esquema de quórum en los registros de comandos de sus aceptadores, y requiere un protocolo de recolección de basura para liberar estos espacios de comando una vez que se confirma el resultado y todos los alumnos (réplicas) han aprendido el resultado.

Comparación de vitalidad

Tanto Paxos como Gbcast están sujetos al resultado de imposibilidad de FLP. ^[9] Por lo tanto, ninguno de los protocolos puede garantizarse en vivo en todas las condiciones posibles. En el mejor de los casos, podemos hablar de las condiciones bajo las cuales se garantiza la vida, expresadas como predicados sobre el mecanismo de detección de fallas: si se cumple la condición para la vida, entonces el protocolo estará activo. Las condiciones de vida de Basic Paxos y Gbcast son similares pero no idénticas.

En Gbcast, el progreso nunca se reanudará si surge un círculo de sospechas mutuas, como se señaló anteriormente: una vez que surge un quórum de procesos de rechazo mutuo, el mecanismo de rechazo hace que sea imposible para cualquier líder obtener un quórum de promesas.

Con un protocolo de Paxos (sin modificar), este problema no surgirá: una vez que finaliza el nivel excesivo de sospechas mutuas, se reanuda el progreso. Por lo tanto, Paxos avanza con cualquier mecanismo de detección de fallas que satisfaga la condición <> W, incluso si surgen períodos durante los cuales ocurren más de un quórum de sospechas mutuas.

Por ejemplo, si comenzamos con un grupo que contiene {AB, C} y causamos una partición de red extendida, Paxos se reanudaría cuando la partición de red se resuelva, pero Gbcast se cerrará permanentemente y es posible que alguna forma de infraestructura de administración deba reiniciar el sistema. Si es necesario preservar el estado del grupo a lo largo de la falla, dicha infraestructura identificaría al último miembro en fallar y reiniciaría el grupo utilizando algún tipo de punto de control almacenado por ese último miembro.

En las implementaciones de Paxos, es común requerir la intervención de un operador humano para reconfigurar Paxos. En tales entornos, Gbcast puede progresar durante el período en el que Paxos no puede. Suponga que la membresía de un grupo desciende lentamente a menos del quórum del tamaño del grupo original. Gbcast puede seguir funcionando incluso con un solo miembro. Paxos dejaría de progresar durante los períodos en los que menos de un quórum de su opinión esté activo.

Necesidad de transferencia estatal

Los sistemas como Isis que implementan Gbcast generalmente proporcionan un mecanismo de transferencia de estado: en el instante en que se entrega la nueva vista que muestra a algún miembro que se une, algún miembro existente hace un punto de control de su copia del estado del grupo. Esto luego se copia al nuevo miembro, que carga el punto de control como el estado del grupo inicial en el momento en que se unió. (Se pueden usar varios esquemas de copia fuera de banda para precargar algún estado antes de la unión para los casos en que el estado es demasiado grande para transferirlo en el último momento de esta manera). La transferencia de estado es necesaria porque en Gbcast, una vez que un miembro se elimina de un grupo, ya no recibirá actualizaciones. Gbcast suele ser utilizado por aplicaciones que mantienen su estado en la memoria y aplican las actualizaciones una por una a medida que se reciben, por lo que una vez que surge una brecha, una réplica ya no es útil.

Tenga en cuenta que esto contrasta con Paxos. En ese protocolo, pueden surgir brechas como consecuencia del esquema de actualización de quórum básico, que no garantiza que todos los miembros vean todas las actualizaciones y puedan ejecutar capas de paso de mensajes no confiables que quizás nunca entreguen algunos mensajes. El algoritmo de aprendizaje de Paxos lee múltiples historias y las combina para llenar esos vacíos. Por lo tanto, Paxos normalmente superará las fallas transitorias y continuará operando sin eliminar al miembro fallado del grupo. El miembro fallido pierde actualizaciones, pero la transferencia de estado no es necesaria a menos que se esté reconfigurando un grupo.

¿Qué protocolo de replicación de máquina de estado reconfigurable dinámicamente vino primero?

El protocolo Gbcast se publicó a principios de un período en el que se introdujeron varios protocolos de máquina de estado capaces de administrar su propia membresía: Gbcast, replicación con sello de vista (Oki y Liskov ^[12] ), Basic Paxos (Lamport ^[5] ), la sincronía parcial protocolo de Dwork, Lynch y Stockmeyer, ^[13]etc. Entre estos, Gbcast fue el primero en ser publicado, en artículos aparecidos en 1985 y 1987; los demás se publicaron a partir de 1988. Por tanto, se podría argumentar que Gbcast fue realmente el primer protocolo de Paxos. Sin embargo, tal declaración trata a "Paxos" como un término bastante amplio que cubre una familia de protocolos que implementan la replicación de la máquina de estado, todos admiten la reconfiguración dinámica de su membresía y tienen propiedades de corrección idénticas pero varían en sus condiciones de vida. Bajo esta definición, Gbcast es un protocolo Paxos.

Si la equivalencia se formaliza mediante bisimulación, en la que cualquier corrida que pueda exhibir un protocolo también es exhibida por el otro, y en la que las suposiciones realizadas y las condiciones para el progreso son idénticas, la comparación se vuelve más compleja. Según esta definición, Gbcast no es un protocolo de Paxos: aunque cada uno puede exhibir las mismas ejecuciones que el otro (visto únicamente en términos de solicitudes de la aplicación y notificaciones a la aplicación), tienen condiciones de vida similares, pero no idénticas. Sin embargo, este tipo de definición estricta plantea un problema diferente: si uno la adopta, algunas versiones de Paxos no son protocolos de Paxos. Por ejemplo, "Paxos baratos" y "Paxos verticales" no son equivalentes de bisimulación a Paxos básicos. ^[14]

Por lo tanto, la pregunta no tiene respuesta a menos que se la haga más específica, y tiene una respuesta diferente dependiendo de la definición de equivalencia que se utilice.

Ver también

• Paxos (informática)
• Sincronía virtual
• Transmisión atómica
• Consenso (informática)
• Multidifusión confiable

Referencias

1. Birman, Kenneth (diciembre de 1985). Replicación y tolerancia a fallas en el sistema ISIS . Décimo Simposio ACM sobre Principios de Sistemas Operativos. págs. 79–86.
2. Birmano, Kenneth; Joseph, Thomas (febrero de 1987). "Comunicación confiable en presencia de fallas" (PDF) . Transacciones ACM en sistemas informáticos . 5 : 47–76. doi : 10.1145 / 7351.7478 .
3. Birman, Kenneth (julio de 1999). "Una revisión de experiencias con multidifusión confiable". Práctica y experiencia en software . 29 (9): 741–774. doi : 10.1002 / (sici) 1097-024x (19990725) 29: 9 <741 :: aid-spe259> 3.0.co; 2-i . hdl : 1813/7380 .
4. Lamport, Leslie (julio de 1978). "Tiempo, relojes y ordenación de eventos en un sistema distribuido" . Comunicaciones de la ACM . 21 (7): 558–565. doi : 10.1145 / 359545.359563 . Consultado el 2 de febrero de 2007 .
5. Lamport, Leslie (mayo de 1998). "El Parlamento a tiempo parcial" . Transacciones ACM en sistemas informáticos . 16 (2): 133-169. doi : 10.1145 / 279227.279229 . Consultado el 2 de febrero de 2007 .
6. Schneider, Fred (1990). "Implementación de servicios tolerantes a fallas utilizando el enfoque de máquina de estados: un tutorial" (PDF) . Encuestas de computación ACM . 22 (4): 299–319. doi : 10.1145 / 98163.98167 .
7. Lamport, Leslie ; Malkhi, Dahlia ; Zhou, Lidong (marzo de 2010). "Reconfiguración de una máquina de estado". Noticias SIGACT . 41 (1): 63–73. doi : 10.1145 / 1753171.1753191 .
8. Pease, Marshall; Robert Shostak; Leslie Lamport (abril de 1980). "Llegar a un acuerdo en presencia de fallas" . Revista de la Asociación de Maquinaria Informática . 27 (2): 228–234. doi : 10.1145 / 322186.322188 . Consultado el 2 de febrero de 2007 .
9. Fischer, M. (abril de 1985). "Imposibilidad de consenso distribuido con un proceso defectuoso" . Revista de la ACM . 32 (2): 374–382. doi : 10.1145 / 3149.214121 .
10. Lamport, Leslie; Robert Shostak; Marshall Pease (julio de 1982). "El problema de los generales bizantinos" . Transacciones ACM sobre lenguajes y sistemas de programación . 4 (3): 382–401. doi : 10.1145 / 357172.357176 . Consultado el 2 de febrero de 2007 .
11. Birmano, Ken; Dahlia Malkhi; Robbert van Renesse (noviembre de 2011). "Metodología virtualmente síncrona para la replicación dinámica de servicios" (PDF) . Informe técnico de Microsoft Research MSR-2010-151.
12. Oki, Brian; Barbara Liskov (1988). Replicación con sello de visualización: un nuevo método de copia principal para admitir sistemas distribuidos de alta disponibilidad . PODC '88: Actas del séptimo simposio anual de ACM sobre principios de computación distribuida . págs. 8-17. doi : 10.1145 / 62546.62549 .
13. Dwork, Cynthia; Lynch, Nancy; Stockmeyer, Larry (abril de 1988). "Consenso en presencia de sincronía parcial" (PDF) . Revista de la ACM . 35 (2): 288–323. doi : 10.1145 / 42282.42283 .
14. Lamport, Leslie (2012). Comentario inédito .