stringtranslate.com

Paxos (informática)

Paxos es una familia de protocolos para resolver consensos en una red de procesadores falibles o poco confiables. El consenso es el proceso de acordar un resultado entre un grupo de participantes. Este problema se complica cuando los participantes o sus comunicaciones pueden experimentar fallas. [1]

Los protocolos de consenso son la base del enfoque de replicación de máquinas de estados para la computación distribuida , como lo sugiere Leslie Lamport [2] y lo analizó Fred Schneider . [3] La replicación de la máquina de estados es una técnica para convertir un algoritmo en una implementación distribuida tolerante a fallas. Las técnicas ad hoc pueden dejar sin resolver casos importantes de fallas. El enfoque de principios propuesto por Lamport et al. garantiza que todos los casos se manejen de forma segura.

El protocolo Paxos se presentó por primera vez en 1989 y recibió el nombre de un sistema de consenso legislativo ficticio utilizado en la isla de Paxos en Grecia, donde Lamport escribió que el parlamento tenía que funcionar "a pesar de que los legisladores entraban y salían continuamente de la Cámara parlamentaria". [4] Posteriormente se publicó como artículo de revista en 1998. [5]

La familia de protocolos Paxos incluye un espectro de compensaciones entre la cantidad de procesadores, la cantidad de retrasos en los mensajes antes de conocer el valor acordado, el nivel de actividad de los participantes individuales, la cantidad de mensajes enviados y los tipos de fallas. Aunque ningún protocolo de consenso determinista tolerante a fallos puede garantizar el progreso en una red asíncrona (un resultado demostrado en un artículo de Fischer , Lynch y Paterson [6] ), Paxos garantiza la seguridad (consistencia) y las condiciones que podrían impedirle avanzar. Son difíciles de provocar.

Paxos se utiliza normalmente cuando se requiere durabilidad (por ejemplo, para replicar un archivo o una base de datos ), en los que la cantidad de estado duradero podría ser grande. El protocolo intenta avanzar incluso durante los períodos en los que un número limitado de réplicas no responden. También existe un mecanismo para descartar una réplica con error permanente o agregar una nueva réplica.

Historia

El tema es anterior al protocolo. En 1988, Lynch , Dwork y Stockmeyer habían demostrado [7] la solucion del consenso en una amplia familia de sistemas "parcialmente sincrónicos". Paxos tiene fuertes similitudes con un protocolo utilizado para acuerdos en "replicación con sello de vista", publicado por primera vez por Oki y Liskov en 1988, en el contexto de transacciones distribuidas. [8] A pesar de este trabajo previo, Paxos ofreció un formalismo particularmente elegante e incluyó una de las primeras pruebas de seguridad para un protocolo de consenso distribuido tolerante a fallas.

Las máquinas de estado reconfigurables tienen fuertes vínculos con trabajos anteriores sobre protocolos de multidifusión grupal confiables que soportan la membresía dinámica en grupos, por ejemplo el trabajo de Birman en 1985 y 1987 sobre el protocolo gbcast [9] virtualmente sincrónico . Sin embargo, gbcast es inusual en cuanto a soporte de durabilidad y solución de fallas de partición. La mayoría de los protocolos de multidifusión confiables carecen de estas propiedades, que son necesarias para las implementaciones del modelo de replicación de la máquina de estados. Este punto se desarrolla en un artículo de Lamport , Malkhi y Zhou. [10]

Los protocolos de Paxos son miembros de una clase teórica de soluciones a un problema formalizado como un acuerdo uniforme con fallas de choque. Keidar y Shraer han demostrado los límites inferiores de este problema . [11] Derecho, [12] una biblioteca de software C++ para replicación de máquinas de estado a escala de nube, ofrece un protocolo Paxos que se ha integrado con una membresía virtualmente síncrona autoadministrada. Este protocolo coincide con los límites de optimización de Keidar y Shraer y se asigna de manera eficiente al hardware moderno del centro de datos remoto DMA (RDMA) (pero usa TCP si RDMA no está disponible).

Suposiciones

Para simplificar la presentación de Paxos, se hacen explícitos los siguientes supuestos y definiciones. Las técnicas para ampliar la aplicabilidad se conocen en la literatura y no se tratan en este artículo.

Procesadores

Red

Número de procesadores

En general, un algoritmo de consenso puede progresar utilizando procesadores, a pesar del fallo simultáneo de cualquier procesador: [13] en otras palabras, el número de procesos no defectuosos debe ser estrictamente mayor que el número de procesos defectuosos. Sin embargo, al utilizar la reconfiguración, se puede emplear un protocolo que sobreviva cualquier número de fallos totales, siempre que no fallen más de F simultáneamente. Para los protocolos Paxos, estas reconfiguraciones se pueden manejar como configuraciones separadas . [14]

Propiedades de seguridad y vivacidad.

Para garantizar la seguridad (también llamada "consistencia"), Paxos define tres propiedades y garantiza que las dos primeras se mantengan siempre, independientemente del patrón de fallas:

Validez (o no trivialidad )
Sólo se pueden elegir y aprender los valores propuestos. [15]
Acuerdo (o coherencia , o seguridad )
No hay dos alumnos distintos que puedan aprender valores diferentes (o no puede haber más de un valor decidido) [15] [16]
Terminación (o vida)
Si se ha propuesto el valor C, eventualmente el alumno L aprenderá algún valor (si suficientes procesadores permanecen sin fallas). [dieciséis]

Tenga en cuenta que no se garantiza que Paxos finalice y, por lo tanto, no tiene la propiedad de vida. Esto está respaldado por el resultado de imposibilidad (FLP) de Fischer Lynch Paterson [6] que establece que un protocolo de coherencia solo puede tener dos: seguridad , vivacidad y tolerancia a fallas . Como el objetivo de Paxos es garantizar la tolerancia a fallas y garantizar la seguridad, no puede garantizar también la vida.

Implementación típica

En la mayoría de las implementaciones de Paxos, cada proceso participante actúa en tres roles; Proponente, Aceptante y Alumno. [17] Esto reduce significativamente la complejidad del mensaje, sin sacrificar la corrección:

En Paxos, los clientes envían comandos a un líder. Durante la operación normal, el líder recibe el comando de un cliente, le asigna un nuevo número de comando y luego comienza la enésima instancia del algoritmo de consenso enviando mensajes a un conjunto de procesos aceptadores. [dieciséis]

Al fusionar roles, el protocolo "colapsa" en una implementación eficiente de estilo cliente-maestro-réplica, típica de la comunidad de bases de datos. [18] El beneficio de los protocolos Paxos (incluidas las implementaciones con roles fusionados) es la garantía de sus propiedades de seguridad.

El flujo de mensajes de una implementación típica se trata en la sección Multi-Paxos.

Paxos Básicos

Este protocolo es el más básico de la familia Paxos. Cada "instancia" (o "ejecución") del protocolo básico de Paxos decide sobre un único valor de salida. El protocolo se desarrolla en varias rondas. Una ronda exitosa tiene 2 fases: la fase 1 (que se divide en las partes a y b ) y la fase 2 (que se divide en las partes a y b ). Vea a continuación la descripción de las fases. Recuerde que asumimos un modelo asíncrono, por lo que, por ejemplo, un procesador puede estar en una fase mientras que otro procesador puede estar en otra.

Fase 1

Fase 1a: Preparar

Un Proponente crea un mensaje, al que llamamos "Preparar", identificado con un número n . Tenga en cuenta que n no es el valor que se propondrá y tal vez se acordará, sino simplemente un número que identifica de forma única este mensaje inicial del proponente (que se enviará a los aceptantes). El número n debe ser mayor que cualquier número utilizado en cualquiera de los mensajes de Preparación anteriores de este Proponente. Luego, envía el mensaje de preparación que contiene n al menos a un quórum de aceptadores. Tenga en cuenta que el mensaje de preparación sólo contiene el número n (es decir, no tiene que contener, por ejemplo, el valor propuesto, a menudo indicado por v ). El Proponente decide quién está en el Quórum [ ¿cómo? ] . Un Proponente no debe iniciar Paxos si no puede comunicarse con al menos un Quórum de Aceptantes.

Fase 1b: Promesa

Cualquiera de los Aceptantes espera un mensaje de Preparación de cualquiera de los Proponentes . Si un Aceptador recibe un mensaje de Preparación, el Aceptador debe mirar el número de identificador n del mensaje de Preparación recién recibido . Hay dos casos.
Si n es mayor que cada número de propuesta anterior recibido, de cualquiera de los Proponentes, por el Aceptador, entonces el Aceptador debe devolver un mensaje, que llamamos "Promesa", al Proponente, de ignorar todas las propuestas futuras que tengan un número menor. que n . Si el Aceptador aceptó una propuesta en algún momento del pasado, debe incluir el número de propuesta anterior, digamos m , y el valor aceptado correspondiente, digamos w , en su respuesta al Proponente.
De lo contrario (es decir, n es menor o igual que cualquier número de propuesta anterior recibida de cualquier Proponente por el Aceptante), el Aceptador puede ignorar la propuesta recibida. No es necesario que responda en este caso para que Paxos funcione. Sin embargo, en aras de la optimización, enviar una respuesta de denegación ( Nack ) le indicaría al proponente que puede detener su intento de crear consenso con la propuesta n .

Fase 2

Fase 2a: Aceptar

Si un proponente recibe promesas de un quórum de aceptantes, debe establecer un valor v para su propuesta. Si algún Aceptador había aceptado previamente alguna propuesta, entonces habrá enviado sus valores al Proponente, quien ahora debe establecer el valor de su propuesta, v , al valor asociado con el número de propuesta más alto informado por los Aceptadores, llamémoslo z . Si ninguno de los Aceptantes había aceptado una propuesta hasta ese momento, entonces el Proponente puede elegir el valor que originalmente quería proponer, digamos x . [19]
El Proponente envía un mensaje de Aceptación , (n, v) , a un Quórum de Aceptadores con el valor elegido para su propuesta, v, y el número de propuesta n (que es el mismo que el número contenido en el mensaje de Preparación enviado previamente al Aceptadores). Entonces, el mensaje de aceptación es (n, v=z) o, en caso de que ninguno de los Aceptadores haya aceptado previamente un valor, (n, v=x) .

Este mensaje de Aceptar debe interpretarse como una "solicitud", como en "¡Acepte esta propuesta, por favor!".

Fase 2b: Aceptada

Si un Aceptador recibe un mensaje de Aceptación, (n, v) , de un Proponente, debe aceptarlo si y solo si aún no ha prometido (en la Fase 1b del protocolo Paxos) considerar solo propuestas que tengan un identificador mayor que n. .
Si el Aceptador aún no ha prometido (en la Fase 1b) considerar solo propuestas que tengan un identificador mayor que n , debe registrar el valor v (del mensaje de aceptación recién recibido ) como el valor aceptado (del Protocolo) y enviar un Mensaje aceptado para el Proponente y cada Estudiante (que normalmente pueden ser los propios Proponentes. Los Estudiantes aprenderán el valor decidido SÓLO DESPUÉS de recibir mensajes Aceptados de la mayoría de los aceptantes, lo que significa, NO después de recibir solo el PRIMER mensaje de Aceptación).
De lo contrario, puede ignorar el mensaje o solicitud de aceptación.

Tenga en cuenta que el consenso se logra cuando la mayoría de los Aceptadores aceptan el mismo número de identificador (en lugar del mismo valor ). Debido a que cada identificador es exclusivo de un Proponente y solo se puede proponer un valor por identificador, todos los Aceptadores que aceptan el mismo identificador aceptan el mismo valor. Estos hechos dan como resultado algunos escenarios contrarios a la intuición que no afectan la corrección: los Aceptadores pueden aceptar múltiples valores, un valor puede lograr una mayoría entre los Aceptadores (con diferentes identificadores) solo para cambiarse más tarde, y los Aceptadores pueden continuar aceptando propuestas después de una identificador ha alcanzado la mayoría. Sin embargo, el protocolo Paxos garantiza que el consenso es permanente y el valor elegido es inmutable.

Cuando las rondas fallan

Las rondas fallan cuando varios Proponentes envían mensajes de preparación contradictorios o cuando el Proponente no recibe un Quórum de respuestas ( Promesa o Aceptada ). En estos casos se deberá iniciar otra ronda con un número de propuesta mayor.

Paxos se puede utilizar para seleccionar un líder

Observe que un Proponente en Paxos podría proponer "Yo soy el líder" (o, por ejemplo, "El Proponente X es el líder"). [20] Debido al acuerdo y las garantías de validez de Paxos, si es aceptado por un Quórum, ahora se sabe que el Proponente es el líder de todos los demás nodos. Esto satisface las necesidades de la elección del líder [21] porque hay un solo nodo que cree que es el líder y un solo nodo que se sabe que es el líder en todo momento.

Representación gráfica del flujo de mensajes en el Paxos básico.

Los siguientes diagramas representan varios casos/situaciones de aplicación del protocolo Paxos Básico. Algunos casos muestran cómo el protocolo Basic Paxos hace frente a la falla de ciertos componentes (redundantes) del sistema distribuido.

Tenga en cuenta que los valores devueltos en el mensaje de Promesa son "nulos" la primera vez que se realiza una propuesta (ya que ningún Aceptador ha aceptado un valor antes en esta ronda).

Paxos básicos sin fallos

En el siguiente diagrama, hay 1 cliente, 1 proponente, 3 aceptantes (es decir, el tamaño del quórum es 3) y 2 estudiantes (representados por las 2 líneas verticales). Este diagrama representa el caso de una primera ronda que tiene éxito (es decir, ningún proceso en la red falla).

Aquí, V es el último de (Va, Vb, Vc).

Casos de error en Paxos básico

Los casos de error más simples son el fallo de un Aceptador (cuando un Quórum de Aceptadores permanece vivo) y el fallo de un Aprendiz redundante. En estos casos, el protocolo no requiere "recuperación" (es decir, aún tiene éxito): no se requieren rondas ni mensajes adicionales, como se muestra a continuación (en los dos diagramas/casos siguientes).

Paxos básico cuando falla un aceptador

En el siguiente diagrama, uno de los Aceptadores del Quórum falla, por lo que el tamaño del Quórum pasa a ser 2. En este caso, el protocolo Paxos Básico aún tiene éxito.

Cliente Proponente Aceptador Aprendiz | | | | | | | X-------->| | | | | | Pedido | X--------->|->|->| | | Preparar(1) | | | | ! | | !! FALLAR !! | |<---------X--X | | Promesa(1,{Va, Vb, nulo}) | X--------->|->| | | ¡Aceptar!(1,V) | |<---------X--X--------->|->| Aceptado(1,V) |<---------------------------------X--X Respuesta | | | | | |

Paxos básico cuando falla un alumno redundante

En el siguiente caso, uno de los alumnos (redundantes) falla, pero el protocolo Paxos básico aún tiene éxito. 

Cliente Proponente Aceptador Aprendiz | | | | | | | X-------->| | | | | | Pedido | X--------->|->|->| | | Preparar(1) | |<---------X--X--X | | Promesa(1,{Va,Vb,Vc}) | X--------->|->|->| | | ¡Aceptar!(1,V) | |<---------X--X--X------>|->| Aceptado(1,V) | | | | | | ! !! FALLAR !! |<---------------------------------X Respuesta | | | | | |

Paxos básico cuando un proponente falla

En este caso, un Proponente fracasa después de proponer un valor, pero antes de que se llegue a un acuerdo. Específicamente, falla en medio del mensaje de aceptación, por lo que solo un Aceptador del Quórum recibe el valor. Mientras tanto, se elige un nuevo Líder (un Proponente) (pero esto no se muestra en detalle). Tenga en cuenta que en este caso hay 2 rondas (las rondas se realizan verticalmente, de arriba a abajo).

Cliente Proponente Aceptador Aprendiz | | | | | | | X----->| | | | | | Pedido | X------------>|->|->| | | Preparar(1) | |<------------X--X--X | | Promesa(1,{Va, Vb, Vc}) | | | | | | | | | | | | | | !! ¡¡Líder falla durante la transmisión!! | X------------>| | | | | ¡Aceptar!(1,V) | ! | | | | | | | | | | | | !! ¡¡NUEVO LÍDER!! | X--------->|->|->| | | Preparar(2) | |<---------X--X--X | | Promesa(2,{V, nulo, nulo}) | X--------->|->|->| | | ¡Acepta!(2,V) | |<---------X--X--X------>|->| Aceptado(2,V) |<---------------------------------X--X Respuesta | | | | | | |

Paxos básico cuando varios proponentes entran en conflicto

El caso más complejo es cuando varios Proponentes se creen Líderes. Por ejemplo, el líder actual puede fracasar y luego recuperarse, pero los otros Proponentes ya han vuelto a seleccionar un nuevo líder. El líder recuperado aún no se ha enterado de esto e intenta comenzar una ronda en conflicto con el líder actual. En el siguiente diagrama se muestran 4 rondas fallidas, pero podría haber más (como se sugiere en la parte inferior del diagrama).

Cliente Proponente Aceptador Aprendiz | | | | | | | X----->| | | | | | Pedido | X------------>|->|->| | | Preparar(1) | |<------------X--X--X | | Promesa(1,{nulo,nulo,nulo}) | ! | | | | | !! EL LÍDER FALLA | | | | | | | !! NUEVO LÍDER (sabe que el último número fue 1) | X--------->|->|->| | | Preparar(2) | |<---------X--X--X | | Promesa(2,{nulo,nulo,nulo}) | | | | | | | | !! VIEJO LÍDER se recupera | | | | | | | | !! VIEJO LÍDER intenta 2, negado | X------------>|->|->| | | Preparar(2) | |<------------X--X--X | | desnudo(2) | | | | | | | | !! VIEJO LÍDER intenta 3 | X------------>|->|->| | | Preparar(3) | |<------------X--X--X | | Promesa(3,{nulo,nulo,nulo}) | | | | | | | | !! NUEVO LÍDER propone, desestimado | | X--------->|->|->| | | ¡Acepta!(2,Va) | | |<---------X--X--X | | Nack(3) | | | | | | | | !! NUEVO LÍDER intenta 4 | | X--------->|->|->| | | Preparar(4) | | |<---------X--X--X | | Promesa(4,{nulo,nulo,nulo}) | | | | | | | | !! VIEJO LÍDER propone, negado | X------------>|->|->| | | ¡Aceptar!(3,Vb) | |<------------X--X--X | | desnudo(4) | | | | | | | | ... etcétera ...

Paxos básico donde un aceptador acepta dos valores diferentes

En el siguiente caso, un Proponente logra la aceptación del valor V1 por parte de un Aceptante antes de fallar. Un nuevo Proponente prepara a los Aceptadores que nunca aceptaron V1, permitiéndole proponer V2. Luego, V2 es aceptado por todos los Aceptadores, incluido el que inicialmente aceptó V1. 

Proponente Aceptador Aprendiz | | | | | | | X--------->|->|->| | | Preparar(1) |<---------X--X--X | | Promesa(1,{nulo,nulo,nulo}) x--------->| | | | | ¡Aceptar!(1,V1) | | X------------>|->| Aceptado(1,V1) ! | | | | | | !! FALLAR !! | | | | | | X--------->|->| | | Preparar(2) |<---------X--X | | Promesa(2,{nulo,nulo}) X------>|->|->| | | ¡Acepta! (2,V2) |<------X--X--X------>|->| Aceptado(2,V2) | | | | | |

Paxos básicos donde una mayoría de múltiples identificadores es insuficiente

En el siguiente caso, un Proponente logra la aceptación del valor V1 de un Aceptante antes de fallar. Un nuevo Proponente prepara a los Aceptadores que nunca aceptaron V1, permitiéndole proponer V2. Este Proponente puede conseguir que un Aceptador acepte V2 antes de fallar. Un nuevo Proponente encuentra una mayoría que incluye al Aceptante que ha aceptado V1 y debe proponerlo. El Proponente logra que dos Aceptadores lo acepten antes de fallar. En este punto, tres Aceptadores han aceptado V1, pero no para el mismo identificador. Finalmente, un nuevo Proponente prepara a la mayoría que no ha visto el mayor identificador aceptado. El valor asociado al mayor identificador de esa mayoría es V2, por lo que deberá proponerlo. Luego, este Proponente consigue que todos los Aceptadores acepten la V2, logrando un consenso. 

 Proponente Aceptador Aprendiz | | | | | | | | | | | X--------------->|->|->|->|->| | | Preparar(1) |<---------------X--X--X--X--X | | Promesa(1,{nulo,nulo,nulo,nulo,nulo}) x--------------->| | | | | | | ¡Aceptar!(1,V1) | | | | X------------------>|->| Aceptado(1,V1) ! | | | | | | | | | | !! FALLAR !! | | | | | | | | | | X--------------->|->|->|->| | | Preparar(2) |<---------------X--X--X--X | | Promesa(2,{nulo,nulo,nulo,nulo}) X--------------->| | | | | | ¡Acepta! (2,V2) | | | | X--------------->|->| Aceptado(2,V2)  ! | | | | | | | | | !! FALLAR !! | | | | | | | | | X--------->|---->|->|->| | | Preparar(3) |<---------X-----X--X--X | | Promesa(3,{V1,nulo,nulo,nulo}) X--------------->|->| | | | ¡Acepta! (3,V1) | | | | X--X--------->|->| Aceptado(3,V1)  ! | | | | | | | | !! FALLAR !! | | | | | | | | X------>|->|------->| | | Preparar(4) |<------X--X--|--|--X | | Promesa(4,{V1(1),V2(2),nulo}) X------>|->|->|->|->| | | ¡Acepta! (4,V2) | X--X--X--X--X------>|->| Aceptado(4,V2)

Paxos básicos donde los nuevos proponentes no pueden cambiar un consenso existente

En el siguiente caso, un Proponente logra la aceptación del valor V1 de dos Aceptadores antes de fallar. Un nuevo Proponente puede comenzar otra ronda, pero ahora le resulta imposible preparar una mayoría que no incluya al menos un Aceptante que haya aceptado V1. Como tal, aunque el Proponente no ve el consenso existente, su única opción es proponer el valor ya acordado. Los nuevos proponentes pueden aumentar continuamente el identificador para reiniciar el proceso, pero el consenso nunca se puede cambiar. 

Proponente Aceptador Aprendiz | | | | | | | X--------->|->|->| | | Preparar(1) |<---------X--X--X | | Promesa(1,{nulo,nulo,nulo}) x--------->|->| | | | ¡Aceptar!(1,V1) | | X--X--------->|->| Aceptado(1,V1) ! | | | | | | !! FALLAR !! | | | | | | X--------->|->| | | Preparar(2) |<---------X--X | | Promesa(2,{V1,nulo}) X------>|->|->| | | ¡Acepta! (2,V1) |<------X--X--X------>|->| Aceptado(2,V1) | | | | | |

Multi-Paxos

Una implementación típica de Paxos requiere un flujo continuo de valores acordados que actúan como comandos para una máquina de estado distribuida. Si cada comando es el resultado de una única instancia del protocolo Basic Paxos, se produciría una cantidad significativa de gastos generales.

Si el líder es relativamente estable, la fase 1 se vuelve innecesaria. Por tanto, es posible saltarse la fase 1 para futuras instancias del protocolo con el mismo líder.

Para lograr esto, el número de ronda I se incluye junto con cada valor que se incrementa en cada ronda por el mismo Líder. Multi-Paxos reduce el retraso de los mensajes sin fallos (propuesta de aprendizaje) de 4 retrasos a 2 retrasos.

Representación gráfica del flujo de mensajes en los Multi-Paxos.

Multi-Paxos sin fallos

En el siguiente diagrama, solo se muestra una instancia (o "ejecución") del protocolo básico de Paxos, con un líder inicial (un proponente). Tenga en cuenta que un Multi-Paxos consta de varias instancias del protocolo Paxos básico.

Cliente Proponente Aceptador Aprendiz | | | | | | | --- Primera Solicitud --- X-------->| | | | | | Pedido | X--------->|->|->| | | Preparar(N) | |<---------X--X--X | | Promesa(N,I,{Va,Vb,Vc}) | X--------->|->|->| | | ¡Aceptar!(N,I,V) | |<---------X--X--X------>|->| Aceptado(N,I,V) |<---------------------------------X--X Respuesta | | | | | | |

donde V = último de (Va, Vb, Vc).

Multi-Paxos cuando se puede saltar la fase 1

En este caso, las instancias posteriores del protocolo Paxos básico (representado por I+1 ) usan el mismo líder, por lo que la fase 1 (de estas instancias posteriores del protocolo Paxos básico), que consiste en las subfases Preparar y Promesa, se omite. Tenga en cuenta que el líder debe ser estable, es decir, no debe fallar ni cambiar.

Cliente Proponente Aceptador Aprendiz | | | | | | | --- Siguiendo solicitudes --- X-------->| | | | | | Pedido | X--------->|->|->| | | ¡Aceptar!(N,I+1,W) | |<---------X--X--X------>|->| Aceptado(N,I+1,W) |<---------------------------------X--X Respuesta | | | | | | |

Multi-Paxos cuando los roles están colapsados

Un despliegue común de los Multi-Paxos consiste en reducir el papel de los Proponentes, Aceptadores y Alumnos a "Servidores". Entonces, al final, solo existen "Clientes" y "Servidores".

El siguiente diagrama representa la primera "instancia" de un protocolo básico de Paxos, cuando los roles de Proponente, Aceptador y Aprendiz se reducen a un solo rol, llamado "Servidor".

Servidores de clientes | | | | --- Primera Solicitud --- X-------->| | | Pedido | X->|->| Preparar(N) | |<-X--X Promesa(N, I, {Va, Vb}) | X->|->| ¡Aceptar!(N,I,Vn) | X<>X<>X Aceptado(N, I) |<--------X | | Respuesta | | | |

Multi-Paxos cuando los roles colapsan y el líder es estable

En las instancias posteriores del protocolo Paxos básico, con el mismo líder que en las instancias anteriores del protocolo Paxos básico, se puede omitir la fase 1.

Servidores de clientes X-------->| | | Pedido | X->|->| ¡Aceptar!(N,I+1,W) | X<>X<>X Aceptado(N,I+1) |<--------X | | Respuesta | | | |

Optimizaciones

Se pueden realizar varias optimizaciones para reducir la cantidad de mensajes intercambiados, mejorar el rendimiento del protocolo, etc. Algunas de estas optimizaciones se informan a continuación.

"Podemos guardar mensajes a costa de un retraso adicional si tenemos un único alumno distinguido que informa a los demás alumnos cuando descubre que se ha elegido un valor. Luego, los aceptadores envían mensajes aceptados sólo al alumno distinguido. En la mayoría de las aplicaciones, los roles de líder y alumno distinguido los desempeña el mismo procesador [22] .
"Un líder puede enviar sus mensajes ¡Preparar y aceptar! solo a un quórum de aceptantes. Siempre que todos los aceptantes de ese quórum estén trabajando y puedan comunicarse con el líder y los alumnos, no hay necesidad de que los aceptantes que no están en el quórum hagan cualquier cosa [22]
"A los aceptantes no les importa qué valor se elige. Simplemente responden a los mensajes ¡Prepárese y Aceptar! para garantizar que, a pesar de las fallas, solo se pueda elegir un valor único. Sin embargo, si un aceptador se entera del valor que se ha elegido, puede almacenar el valor en el almacenamiento estable y borrar cualquier otra información que haya guardado allí. Si el aceptador recibe más tarde un mensaje Preparar o Aceptar , en lugar de realizar su acción Fase1b o Fase2b, simplemente puede informar al líder del valor elegido [22] .
"En lugar de enviar el valor v, el líder puede enviar un hash de v a algunos aceptantes en sus mensajes ¡Aceptar!. Un alumno aprenderá que se elige v si recibe mensajes aceptados para v o su hash de un quórum de aceptantes. y al menos uno de esos mensajes contiene v en lugar de su hash. Sin embargo, un líder podría recibir mensajes Promise que le indiquen el hash de un valor v que debe usar en su acción Phase2a sin decirle el valor real de v. Esto sucede, el líder no puede ejecutar su acción de Fase2a hasta que se comunique con algún proceso que conozca v." [22]
"Un proponente puede enviar su propuesta sólo al líder y no a todos los coordinadores. Sin embargo, esto requiere que el resultado del algoritmo de selección de líder se transmita a los proponentes, lo que podría resultar costoso. Por lo tanto, sería mejor dejar que el El proponente envía su propuesta a todos los coordinadores (en ese caso, sólo los propios coordinadores necesitan saber quién es el líder).
"En lugar de que cada aceptador envíe mensajes aceptados a cada alumno, los aceptadores pueden enviar sus mensajes aceptados al líder y el líder puede informar a los alumnos cuando se ha elegido un valor. Sin embargo, esto agrega un retraso adicional en el mensaje. [15]
"Finalmente, observe que la fase 1 es innecesaria para la ronda 1. El líder de la ronda 1 puede comenzar la ronda enviando un mensaje ¡Aceptar! con cualquier valor propuesto". [15]

Paxos baratos

Cheap Paxos extiende Basic Paxos para tolerar fallas F con procesadores principales F+1 y procesadores auxiliares F mediante la reconfiguración dinámica después de cada falla.

Esta reducción en los requisitos del procesador se produce a expensas de la vida; Si fallan demasiados procesadores principales en poco tiempo, el sistema debe detenerse hasta que los procesadores auxiliares puedan reconfigurar el sistema. Durante los períodos estables, los procesadores auxiliares no participan en el protocolo.

"Con sólo dos procesadores p y q, un procesador no puede distinguir el fallo del otro procesador del fallo del medio de comunicación. Se necesita un tercer procesador. Sin embargo, ese tercer procesador no tiene que participar en la elección de la secuencia de comandos. Debe tome medidas sólo en caso de que poq falle, después de lo cual no hace nada mientras poq continúa operando el sistema por sí solo. Por lo tanto, el tercer procesador puede ser pequeño/lento/barato, o un procesador dedicado principalmente a otras tareas. ". [22]

Flujo de mensajes: Multi-Paxos baratos

Un ejemplo que involucra tres aceptadores principales, un aceptador auxiliar y un tamaño de quórum de tres, que muestra la falla de un procesador principal y su posterior reconfiguración:

 { Aceptadores }Estudiante auxiliar principal del proponente| | | | | | -- Fase 2 --X----------->|->|->| | | ¡Aceptar!(N,I,V)| | | ! | | --- ¡FALLAR! ---|<-----------X--X--------------->| Aceptado(N,I,V)| | | | | -- Fallo detectado (solo se aceptan 2) --X----------->|->|------->| | ¡Aceptar!(N,I,V) (retransmitir, incluir Aux)|<-----------X--X--------X------>| Aceptado(N,I,V)| | | | | -- Reconfigurar: Quórum = 2 --X----------->|->| | | ¡Aceptar!(N,I+1,W) (Aux no participa)|<-----------X--X--------------->| Aceptado(N,I+1,W)| | | | |

Paxos rápidos

Fast Paxos generaliza Basic Paxos para reducir los retrasos en los mensajes de un extremo a otro. En Basic Paxos, el retraso del mensaje desde la solicitud del cliente hasta el aprendizaje es de 3 retrasos de mensaje. Fast Paxos permite 2 retrasos de mensajes, pero requiere que (1) el sistema esté compuesto por 3f+ 1 aceptadores para tolerar hasta f fallas (en lugar de los clásicos 2f+1), y (2) que el Cliente envíe su solicitud a múltiples destinos .

Intuitivamente, si el líder no tiene ningún valor que proponer, entonces un cliente podría enviar un ¡ Aceptar! mensaje a los Aceptadores directamente. Los Aceptadores responderían como en Paxos Básico, enviando mensajes Aceptados al líder y cada Estudiante logrando dos retrasos en los mensajes de Cliente a Estudiante.

Si el líder detecta una colisión, la resuelve enviando ¡Aceptar! mensajes para una nueva ronda que se aceptan como de costumbre. Esta técnica de recuperación coordinada requiere cuatro retrasos en los mensajes del cliente al alumno.

La optimización final ocurre cuando el líder especifica una técnica de recuperación de antemano, lo que permite a los Aceptadores realizar ellos mismos la recuperación de la colisión. Por lo tanto, la recuperación de colisiones no coordinada puede ocurrir en tres retrasos de mensajes (y sólo dos retrasos de mensajes si todos los Estudiantes también son Aceptadores).

Flujo de mensajes: Paxos rápido, no conflictivo

Cliente Líder Aceptador Aprendiz | | | | | | | | | X--------->|->|->|->| | | Cualquiera(N,I,Recuperación) | | | | | | | | X------------------->|->|->|->| | | ¡Aceptar!(N,I,W) | |<---------X--X--X--X------>|->| Aceptado(N,I,W) |<------------------------------------X--X Respuesta(W) | | | | | | | |

Flujo de mensajes: Fast Paxos, propuestas contradictorias

Propuestas contradictorias con recuperación coordinada. Nota: el protocolo no especifica cómo manejar la solicitud del cliente descartado.

Cliente Líder Aceptador Aprendiz | | | | | | | | | | | | | | | | | | | | | | | | | | | !! Propuestas contradictorias concurrentes | | | | | | | | | !! recibido en diferente orden | | | | | | | | | !! por los aceptantes | X--------------?|-?|-?|-?| | | ¡Aceptar!(N,I,V) X-----------------?|-?|-?|-?| | | ¡Aceptar!(N,I,W) | | | | | | | | | | | | | | | | | | !! Los aceptantes no están de acuerdo con el valor | | |<-------X--X->|->|----->|->| Aceptado(N,I,V) | | |<-------|<-|<-X--X----->|->| Aceptado(N,I,W) | | | | | | | | | | | | | | | | | | !! Detectar colisión y recuperarse | | X------->|->|->|->| | | ¡Aceptar!(N+1,I,W) | | |<-------X--X--X--X----->|->| Aceptado(N+1,I,W) |<---------------------------------X--X Respuesta(W) | | | | | | | | |

Propuestas contradictorias con recuperación descoordinada.

Cliente Líder Aceptador Aprendiz | | | | | | | | | | | X------->|->|->|->| | | Cualquiera(N,I,Recuperación) | | | | | | | | | | | | | | | | | | !! Propuestas contradictorias concurrentes | | | | | | | | | !! recibido en diferente orden | | | | | | | | | !! por los aceptantes | X--------------?|-?|-?|-?| | | ¡Aceptar!(N,I,V) X-----------------?|-?|-?|-?| | | ¡Aceptar!(N,I,W) | | | | | | | | | | | | | | | | | | !! Los aceptantes no están de acuerdo con el valor | | |<-------X--X->|->|----->|->| Aceptado(N,I,V) | | |<-------|<-|<-X--X----->|->| Aceptado(N,I,W) | | | | | | | | | | | | | | | | | | !! Detectar colisión y recuperarse | | |<-------X--X--X--X----->|->| Aceptado(N+1,I,W) |<---------------------------------X--X Respuesta(W) | | | | | | | | |

Flujo de mensajes: Paxos rápidos con recuperación descoordinada y roles colapsados

(roles fusionados de Aceptador/Aprendiz)

Servidores de clientes | | | | | | | | X->|->|->| Cualquiera(N,I,Recuperación) | | | | | | | | | | | | !! Propuestas contradictorias concurrentes | | | | | | !! recibido en diferente orden | | | | | | !! por los servidores | X--------?|-?|-?|-?| ¡Aceptar!(N,I,V) X-----------?|-?|-?|-?| ¡Aceptar!(N,I,W) | | | | | | | | | | | | !! Los servidores no están de acuerdo con el valor | | X<>X->|->| Aceptado(N,I,V) | | |<-|<-X<>X Aceptado(N,I,W) | | | | | | | | | | | | !! Detectar colisión y recuperarse | | X<>X<>X<>X Aceptado(N+1,I,W) |<-----------X--X--X--X Respuesta(W) | | | | | |

Paxos generalizados

El consenso generalizado explora la relación entre las operaciones de la máquina de estados replicada y el protocolo de consenso que la implementa. [16] El descubrimiento principal implica optimizaciones de Paxos cuando se pueden aplicar propuestas contradictorias en cualquier orden. es decir, cuando las operaciones propuestas son operaciones conmutativas para la máquina de estados. En tales casos, se pueden aceptar ambas operaciones en conflicto, evitando los retrasos necesarios para resolver los conflictos y volver a proponer las operaciones rechazadas.

Este concepto se generaliza aún más en secuencias cada vez mayores de operaciones conmutativas, algunas de las cuales se sabe que son estables (y, por lo tanto, pueden ejecutarse). El protocolo rastrea estas secuencias asegurando que todas las operaciones propuestas de una secuencia se estabilicen antes de permitir que cualquier operación que no conmute con ellas se estabilice.

Ejemplo

Para ilustrar Paxos generalizado, el siguiente ejemplo muestra un flujo de mensajes entre dos clientes que se ejecutan simultáneamente y una máquina de estado replicada que implementa operaciones de lectura/escritura en dos registros distintos A y B.

Tenga en cuenta queEn esta tabla se indican operaciones que no son conmutativas.

Una posible secuencia de operaciones:

<1:Leer(A), 2:Leer(B), 3:Escribir(B), 4:Leer(B), 5:Leer(A), 6:Escribir(A)>

Dado que 5:Read(A)conmuta con ambos 3:Write(B)y 4:Read(B), una posible permutación equivalente al orden anterior es la siguiente:

<1:Leer(A), 2:Leer(B), 5:Leer(A), 3:Escribir(B), 4:Leer(B), 6:Escribir(A)>

En la práctica, un viaje se produce sólo cuando las operaciones se proponen al mismo tiempo.

Flujo de mensajes: Paxos generalizado (ejemplo)

No se muestran las respuestas. Nota: las abreviaturas de los mensajes difieren de los flujos de mensajes anteriores debido a las características específicas del protocolo; consulte [23] para obtener una discusión completa.

Cliente Líder Aceptador Aprendiz | | | | | | | | !! Nuevo líder comienza la ronda | | X----->|->|->| | | Preparar(N) | | |<-----X- X- X | | Promesa(N,nula) | | X----->|->|->| | | Fase2Inicio(N,nulo) | | | | | | | | | | | | | | | | !! Propuestas de desplazamientos simultáneos | X------- ?|-----?|-?|-?| | | Proponer (Leer A) X-----------?|-----?|-?|-?| | | Proponer (Leer B) | | X------X-------------->|->| Aceptado(N,<LeerA,LeerB>) | | |<--------X--X-------->|->| Aceptado(N,<LeerB,LeerA>) | | | | | | | | | | | | | | | | !! Sin conflicto, ambos aceptados. | | | | | | | | Estable = <LeerA, LeerB> | | | | | | | | | | | | | | | | !! Propuestas contradictorias concurrentes X-----------?|-----?|-?|-?| | | Proponer(<EscribirB,LeerA>) | X--------?|-----?|-?|-?| | | Proponer (Leer B) | | | | | | | | | | X------X-------------->|->| Aceptado(N,<EscribirB,LeerA> . <LeerB>) | | |<--------X--X-------->|->| Aceptado(N,<LeerB>. <EscribirB,LeerA>) | | | | | | | | | | | | | | | | !! Conflicto detectado, líder elige | | | | | | | | orden conmutativo: | | | | | | | | V = <LeerA, EscribirB, LeerB> | | | | | | | | | | X----->|->|->| | | Fase2Inicio(N+1,V) | | |<-----X- X- X-------->|->| Aceptado(N+1,V) | | | | | | | | Estable = <LeerA, LeerB>. | | | | | | | | <LeerA, EscribirB, LeerB> | | | | | | | | | | | | | | | | !! Propuestas más conflictivas X-----------?|-----?|-?|-?| | | Proponer(EscribirA) | X--------?|-----?|-?|-?| | | Proponer (Leer A) | | | | | | | | | | X------X-------------->|->| Aceptado(N+1,<EscribirA> . <LeerA>) | | |<--------X- X-------->|->| Aceptado(N+1,<LeerA>. <EscribirA>) | | | | | | | | | | | | | | | | !! El líder elige el orden: | | | | | | | | W = <EscribirA, LeerA> | | | | | | | | | | X----->|->|->| | | Fase2Inicio(N+2,W) | | |<-----X- X- X-------->|->| Aceptado(N+2,W) | | | | | | | | Estable = <LeerA, LeerB>. | | | | | | | | <LeerA, EscribirB, LeerB> . | | | | | | | | <EscribirA, LeerA> | | | | | | | |

Actuación

El flujo de mensajes anterior nos muestra que Generalized Paxos puede aprovechar la semántica de operación para evitar colisiones cuando falla el ordenamiento espontáneo de la red. Esto permite que el protocolo sea en la práctica más rápido que Fast Paxos. Sin embargo, cuando ocurre una colisión, Generalized Paxos necesita dos viajes de ida y vuelta adicionales para recuperarse. Esta situación se ilustra con las operaciones WriteB y ReadB en el esquema anterior.

En el caso general, estos viajes de ida y vuelta son inevitables y se deben al hecho de que se pueden aceptar múltiples comandos durante un recorrido. Esto hace que el protocolo sea más caro que Paxos cuando los conflictos son frecuentes. Esperemos que sean posibles dos posibles mejoras de Generalized Paxos para mejorar el tiempo de recuperación. [24]

Paxos bizantino

Paxos también puede extenderse para soportar fallas arbitrarias de los participantes, incluyendo mentiras, fabricación de mensajes, colusión con otros participantes, no participación selectiva, etc. Este tipo de fallas se denominan fallas bizantinas , en honor a la solución popularizada por Lamport. [26]

Byzantine Paxos [27] introducido por Castro y Liskov agrega un mensaje adicional (Verificar) que actúa para distribuir conocimiento y verificar las acciones de los otros procesadores:

Flujo de mensajes: Multi-Paxos bizantino, estado estable

Cliente Proponente Aceptador Aprendiz | | | | | | | X-------->| | | | | | Pedido | X--------->|->|->| | | ¡Aceptar!(N,I,V) | | X<>X<>X | | Verificar(N,I,V) - TRANSMISIÓN | |<---------X--X--X------>|->| Aceptado(N,V) |<---------------------------------X--X Respuesta(V) | | | | | | |

Fast Byzantine Paxos [28] introducido por Martin y Alvisi elimina este retraso adicional, ya que el cliente envía comandos directamente a los Aceptadores.

Tenga en cuenta que el mensaje Aceptado en Fast Byzantine Paxos se envía a todos los Aceptadores y a todos los Estudiantes, mientras que Fast Paxos envía mensajes Aceptados solo a los Estudiantes):

Flujo de mensajes: Multi-Paxos bizantino rápido, estado estable

Aprendiz aceptador de clientes | | | | | | X----->|->|->| | | ¡Aceptar!(N,I,V) | X<>X<>X------>|->| Aceptado(N,I,V) - TRANSMISIÓN |<-------------------X--X Respuesta(V) | | | | | |

El escenario de falla es el mismo para ambos protocolos; Cada alumno espera recibir mensajes idénticos F+1 de diferentes aceptantes. Si esto no ocurre, los propios Aceptadores también lo sabrán (ya que intercambiaron mensajes entre sí en la ronda de transmisión), y los Aceptadores correctos retransmitirán el valor acordado:

Flujo de mensajes: Multi-Paxos bizantino rápido, error

Aprendiz aceptador de clientes | | | ! | | !! Un aceptador está defectuoso X----->|->|->! | | ¡Aceptar!(N,I,V) | X<>X<>X------>|->| Aceptado(N,I,{V,W}) - TRANSMISIÓN | | | ! | | !! Los alumnos reciben 2 comandos diferentes. | | | ! | | !! Corregir Los aceptantes notan el error y eligen | X<>X<>X------>|->| Aceptado(N,I,V) - TRANSMISIÓN |<-------------------X--X Respuesta(V) | | | ! | |

Adaptación de Paxos para redes RDMA

Con el surgimiento de redes de centros de datos confiables de muy alta velocidad que admiten DMA remoto ( RDMA ), ha habido un interés sustancial en optimizar Paxos para aprovechar la descarga de hardware, en la que la tarjeta de interfaz de red y los enrutadores de red brindan confiabilidad y control de congestión en la capa de red, liberando la CPU host para otras tareas. La biblioteca Derecho C++ Paxos es una implementación de Paxos de código abierto que explora esta opción. [12]

Derecho ofrece tanto un Paxos clásico, con durabilidad de datos en secuencias completas de apagado/reinicio, como un Paxos vertical (multidifusión atómica), para replicación en memoria y sincronización de máquina de estado. Los protocolos de Paxos empleados por Derecho debían adaptarse para maximizar la transmisión de datos asincrónica y eliminar otras fuentes de retraso en la ruta crítica del líder. Esto permite a Derecho mantener la velocidad de datos RDMA bidireccional completa. Por el contrario, aunque los protocolos tradicionales de Paxos se pueden migrar a una red RDMA simplemente asignando las operaciones de envío de mensajes a operaciones RDMA nativas, hacerlo deja retrasos de ida y vuelta en la ruta crítica. En las redes RDMA de alta velocidad, incluso los retrasos pequeños pueden ser lo suficientemente grandes como para impedir la utilización de todo el ancho de banda potencial.

Uso de producción de Paxos

Ver también

Referencias

  1. ^ Por favor, Marshall; Shostak, Robert; Lamport, Leslie (abril de 1980). "Llegar a un acuerdo en presencia de fallas". Revista de la Asociación de Maquinaria de Computación . 27 (2): 228–234. doi : 10.1145/322186.322188 . S2CID  6429068 . Consultado el 2 de febrero de 2007 .
  2. ^ 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 . S2CID  215822405 . Consultado el 2 de febrero de 2007 .
  3. ^ 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. CiteSeerX 10.1.1.69.1536 . doi :10.1145/98163.98167. S2CID  678818. 
  4. ^ Historia del periódico de Leslie Lamport
  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 . S2CID  421028 . Consultado el 2 de febrero de 2007 .
  6. ^ ab 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 . S2CID  207660233.
  7. ^ Dtrabajo, Cynthia; Lynch, Nancy; Stockmeyer, Larry (abril de 1988). "Consenso en presencia de sincronía parcial" (PDF) . Revista de la ACM . 35 (2): 288–323. CiteSeerX 10.1.1.13.3423 . doi :10.1145/42282.42283. S2CID  17007235. 
  8. ^ Bueno, Brian; Liskov, Bárbara (1988). "Replicación con sello de vista: 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 informática distribuida . págs. 8-17. doi : 10.1145/62546.62549.
  9. ^ Birmano, Kenneth; José, Thomas (febrero de 1987). "Comunicación confiable ante la presencia de fallas". Transacciones ACM en sistemas informáticos . 5 : 47–76. doi :10.1145/7351.7478. hdl : 1813/6534 . S2CID  11224827.
  10. ^ Lamport, Leslie; Malkhi, Dalia; Zhou, Lidong (marzo de 2010). "Reconfiguración de una máquina de estados". Noticias SIGACT . 41 (1): 63–73. CiteSeerX 10.1.1.212.2168 . doi :10.1145/1753171.1753191. S2CID  15189602. 
  11. ^ Keidar, Idit ; Shraer, Alejandro (2006). "Oportunidad, detectores de fallas y desempeño consensuado". PODC '06: Actas del 25º Simposio anual de ACM sobre principios de informática distribuida . doi :10.1145/1146381.1146408.
  12. ^ ab Jha, Sagar; Behrens, Jonathan; Gkountouvas, Theo; Milán, Mateo; Canción, Weijia; Tremel, Eduardo; van Renesse, Robbert; Zink, Sídney; Birman, Ken (abril de 2019). "Derecho: Replicación rápida de máquinas de estado para servicios en la nube". Transacciones ACM en sistemas informáticos . 36 (2). doi :10.1145/3302258. S2CID  218482757.
  13. ^ Lamport, Leslie (2004). "Límites inferiores para el consenso asincrónico".
  14. ^ Van Renesse, Robbert; Altinbuken, Deniz (17 de febrero de 2015). "Paxos se hizo moderadamente complejo". Encuestas de Computación ACM . 47 (3): 42:1–42:36. doi :10.1145/2673577. ISSN  0360-0300.
  15. ^ ABCDE Lamport, Leslie (2005). "Paxos rápidos".
  16. ^ abcd Lamport, Leslie (2005). "Consenso Generalizado y Paxos". {{cite journal}}: Citar diario requiere |journal=( ayuda )
  17. ^ Chandra, Tushar; Griesemer, Robert; Redstone, Josué (2007). "Paxos hecho vivir". Actas del vigésimo sexto simposio anual de ACM sobre principios de informática distribuida. págs. 398–407. doi :10.1145/1281100.1281103. ISBN 9781595936165. S2CID  207164635.{{cite book}}: Mantenimiento CS1: fecha y año ( enlace )
  18. ↑ Quesada Torres, Luis (2018). El algoritmo de Paxos. Charlas técnicas de Google.
  19. ^ Lamport, Leslie (2001). Paxos Made Simple ACM SIGACT News (Columna de Computación Distribuida) 32 , 4 (Número completo 121, diciembre de 2001) 51-58.
  20. ^ "Elección de líder, ¿por qué debería importarme?". Blog elástico . 13 de septiembre de 2013 . Consultado el 27 de febrero de 2021 .
  21. ^ I. Gupta, R. van Renesse y KP Birman, 2000, Un protocolo de elección de líder probabilísticamente correcto para grupos grandes, Informe técnico , Universidad de Cornell
  22. ^ ABCDE Lamport, Leslie; Massa, Mike (2004). "Paxos baratos". Actas de la Conferencia Internacional sobre Redes y Sistemas Confiables (DSN 2004) .
  23. ^ Turner, Bryan (2007). "La familia de protocolos de consenso de Paxos".
  24. ^ Pedro, Sutra; Marc, Shapiro (2011). "Consenso generalizado rápido y genuino" (PDF) . SRDS'11: 30º Simposio IEEE sobre sistemas distribuidos confiables .
  25. ^ Lamport, Leslie; Malkhi, Dalia; Zhou, Lidong (2009). "Paxos verticales y replicación de respaldo primario". Actas del 28º simposio de ACM sobre principios de informática distribuida . PODC'09. Nueva York, NY, Estados Unidos: ACM. págs. 312–313. CiteSeerX 10.1.1.150.1791 . doi :10.1145/1582716.1582783. ISBN  9781605583969. S2CID  2763624.
  26. ^ Lamport, Leslie; Shostak, Robert; Pease, Marshall (julio de 1982). "El problema de los generales bizantinos". Transacciones ACM sobre lenguajes y sistemas de programación . 4 (3): 382–401. CiteSeerX 10.1.1.64.2312 . doi :10.1145/357172.357176. S2CID  55899582 . Consultado el 2 de febrero de 2007 . 
  27. ^ Castro, Miguel; Liskov, Barbara (febrero de 1999). "Tolerancia práctica a fallas bizantinas" (PDF) . Actas del Tercer Simposio sobre diseño e implementación de sistemas operativos : 173–186 . Consultado el 5 de marzo de 2018 .
  28. ^ Martín, Jean-Philippe; Alvisi, Lorenzo (julio de 2006). "Rápido consenso bizantino" (PDF) . Transacciones IEEE sobre informática segura y confiable . 3 (3): 202–215. doi : 10.1109/TDSC.2006.35 . Consultado el 5 de marzo de 2018 .
  29. ^ Madrigueras, Mike. "El servicio Chubby Lock para sistemas distribuidos débilmente acoplados" (PDF) . OSDI.
  30. ^ Aahlad y otros (2011). “El motor de coordinación distribuida (DConE)” Archivado el 15 de abril de 2016 en Wayback Machine . Libro blanco de WANdisco.
  31. ^ Kolbeck, Björn; Högqvist, Mikael; Stender, enero; Hupfeld, Félix (2011). “Flease - Coordinación de arrendamiento sin Lock Server”. 25º Simposio internacional de procesamiento distribuido y paralelo del IEEE (IPDPS 2011).

enlaces externos