Paxos (informática)

Paxos es una familia de protocolos para resolver el consenso en una red de procesadores poco fiables o falibles. El consenso es el proceso de llegar a un acuerdo sobre un resultado entre un grupo de participantes. Este problema se vuelve difícil cuando los participantes o sus comunicaciones pueden experimentar fallos. ^[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 sugirió Leslie Lamport ^[2] y analizó Fred Schneider ^[3] . La replicación de máquinas de estados es una técnica para convertir un algoritmo en una implementación distribuida y tolerante a fallas. Las técnicas ad hoc pueden dejar casos importantes de fallas sin resolver. El enfoque basado en principios propuesto por Lamport et al. garantiza que todos los casos se manejen de manera segura.

El Protocolo de Paxos fue presentado por primera vez en 1989 y recibió su nombre de un sistema ficticio de consenso legislativo utilizado en la isla de Paxos en Grecia, donde Lamport escribió que el parlamento tenía que funcionar "aunque los legisladores entraran y salieran 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 demoras 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 tolerante a fallas determinista puede garantizar el progreso en una red asincrónica (un resultado demostrado en un artículo de Fischer , Lynch y Paterson ^[6] ), Paxos garantiza la seguridad (consistencia) y las condiciones que podrían evitar que avance son difíciles de provocar.

Paxos se utiliza generalmente 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 períodos en los que una cantidad limitada de réplicas no responden. También hay un mecanismo para eliminar una réplica que falló permanentemente o para agregar una nueva réplica.

El tema es anterior al protocolo. En 1988, Lynch , Dwork y Stockmeyer habían demostrado la capacidad de solución del consenso en una amplia familia de sistemas "parcialmente sincrónicos". ^[7] Paxos tiene fuertes similitudes con un protocolo utilizado para el acuerdo en la "replicación con sello de vista", publicado por primera vez por Oki y Liskov en 1988, en el contexto de las transacciones distribuidas. ^[8] A pesar de este trabajo previo, Paxos ofrecía un formalismo particularmente elegante e incluía 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 previos sobre protocolos de multidifusión de grupo confiables que admiten la membresía de grupo dinámica, por ejemplo, el trabajo de Birman en 1985 y 1987 sobre el protocolo gbcast virtualmente sincrónico ^[9] . Sin embargo, gbcast es inusual en cuanto a la compatibilidad con la durabilidad y la resolución de fallas de particionamiento. 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 máquinas de estado. Este punto se desarrolla en un artículo de Lamport , Malkhi y Zhou. ^[10]

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

Para simplificar la presentación de Paxos, se explicitan los siguientes supuestos y definiciones. En la literatura se conocen técnicas para ampliar su aplicabilidad, que no se abordan en este artículo.

• Los procesadores funcionan a una velocidad arbitraria.
• Los procesadores pueden experimentar fallas.
• Los procesadores con almacenamiento estable pueden volver a unirse al protocolo después de fallas (siguiendo un modelo de falla de recuperación ante caídas).
• Los procesadores no se confabulan, mienten ni intentan subvertir el protocolo de ninguna otra forma. (Es decir, no se producen fallas bizantinas . Consulte Paxos bizantino para obtener una solución que tolere las fallas que surgen del comportamiento arbitrario o malintencionado de los procesos).

• Los procesadores pueden enviar mensajes a cualquier otro procesador.
• Los mensajes se envían de forma asincrónica y su entrega puede tardar un tiempo arbitrario.
• Los mensajes pueden perderse, reordenarse o duplicarse.
• Los mensajes se envían sin corrupción. (Es decir, no se producen errores bizantinos. Consulte Paxos bizantino para obtener una solución que tolera los mensajes corruptos que surgen del comportamiento arbitrario o malintencionado de los canales de mensajería).

En general, un algoritmo de consenso puede avanzar utilizando procesadores, a pesar de la falla simultánea 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, utilizando la reconfiguración, se puede emplear un protocolo que sobreviva a cualquier número total de fallas siempre que no más de F fallen simultáneamente. Para los protocolos Paxos, estas reconfiguraciones se pueden manejar como configuraciones separadas . ^[14]${\estilo de visualización n=2F+1}$${\estilo de visualización F}$

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

Validez (o no trivialidad )

Sólo los valores propuestos pueden ser elegidos y aprendidos. ^[15]

Acuerdo (o consistencia , o seguridad )

No pueden aprender dos estudiantes distintos valores diferentes (o no puede haber más de un valor decidido). ^{[15] [16]}

Terminación (o vitalidad)

Si se ha propuesto el valor C, entonces eventualmente el alumno L aprenderá algún valor (si quedan suficientes procesadores sin fallas). ^[16]

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

En la mayoría de las implementaciones de Paxos, cada proceso participante actúa en tres roles: Proponente, Aceptador y Aprendiz. ^[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 el funcionamiento normal, el líder recibe el comando de un cliente, le asigna un nuevo número de comando y luego inicia la ^instancia del algoritmo de consenso enviando mensajes a un conjunto de procesos aceptadores. ${\estilo de visualización i}$${\estilo de visualización i}$^[16]

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 cubre en la sección Multi-Paxos.

Este protocolo es el más básico de la familia Paxos. Cada "instancia" (o "ejecución") del protocolo básico Paxos decide un único valor de salida. El protocolo se desarrolla en varias rondas. Una ronda exitosa tiene 2 fases: fase 1 (que se divide en las partes a y b ) y 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 asincrónico, por lo que, por ejemplo, un procesador puede estar en una fase mientras que otro procesador puede estar en otra.

Un Proponente crea un mensaje, al que llamamos Preparar. El mensaje se identifica con un número único, n , que debe ser mayor que cualquier número utilizado previamente en un mensaje Preparar por este Proponente. Tenga en cuenta que n no es el valor que se va a proponer; es simplemente un identificador único de este mensaje inicial del Proponente. De hecho, el mensaje Preparar no necesita contener el valor propuesto (que a menudo se indica con v ).

El Proponente elige al menos un Cuórum de Aceptantes ^{[ ¿cómo? ]} y les envía el mensaje de Preparación que contiene n . Un Proponente no debe iniciar Paxos si no puede comunicarse con suficientes Aceptantes para constituir un Cuórum.

Los Aceptantes esperan un mensaje de Preparación de cualquiera de los Proponentes. Cuando un Aceptante recibe un mensaje de Preparación, debe examinar el número de identificador, n , de ese mensaje. Existen dos casos:

1. Si n es mayor que el número de cada propuesta anterior recibida por el Aceptante (de cualquier Proponente), entonces el Aceptante debe devolver un mensaje (llamado Promesa ) al Proponente, indicando que el Aceptante ignorará todas las propuestas futuras numeradas menores o iguales a n . La Promesa debe incluir el número más alto entre las Propuestas que el Aceptante aceptó previamente, junto con el valor aceptado correspondiente.
2. Si n es menor o igual que cualquier número de propuesta anterior recibida por el Aceptante, este no necesita responder y puede ignorar la propuesta. Sin embargo, por motivos de optimización, enviar una respuesta de rechazo o de reconocimiento negativo ( NAK ) le indicaría al Proponente que puede detener su intento de crear consenso con la propuesta n .

Si un Proponente recibe Promesas de un Quórum de Aceptantes, necesita establecer un valor v para su propuesta. Si algún Aceptante 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 Aceptantes, llamémoslo z . Si ninguno de los Aceptantes había aceptado una propuesta hasta este punto, 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 Aceptantes 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 a los Aceptantes). Por lo tanto, el mensaje de Aceptación es (n, v=z) o, en caso de que ninguno de los Aceptantes haya aceptado previamente un valor, (n, v=x) .

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

Si un Aceptante recibe un mensaje de Aceptación, (n, v) , de un Proponente, debe aceptarlo si y solo si no ha prometido ya (en la Fase 1b del protocolo Paxos) considerar solo propuestas que tengan un identificador mayor que n .

Si el Aceptante no ha prometido ya (en la Fase 1b) considerar únicamente las propuestas que tengan un identificador mayor que n , debería registrar el valor v (del mensaje de Aceptación que acaba de recibir ) como el valor aceptado (del Protocolo), y enviar un mensaje de Aceptación al Proponente y a cada Aprendiz (que normalmente pueden ser los propios Proponentes). Los Aprendices aprenderán el valor decidido solo después de recibir mensajes de Aceptación de una mayoría de aceptantes, es decir, 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 una mayoría de los Aceptantes acepta el mismo número de identificador (en lugar del mismo valor ). Debido a que cada identificador es único para un Proponente y solo se puede proponer un valor por identificador, todos los Aceptantes que aceptan el mismo identificador aceptan el mismo valor. Estos hechos dan lugar a algunos escenarios contraintuitivos que no afectan la corrección: los Aceptantes pueden aceptar múltiples valores, un valor puede lograr una mayoría entre los Aceptantes (con diferentes identificadores) solo para cambiarse más tarde, y los Aceptantes pueden continuar aceptando propuestas después de que un identificador haya logrado una mayoría. Sin embargo, el protocolo Paxos garantiza que el consenso sea permanente y que el valor elegido sea inmutable.

Las rondas fallan cuando varios proponentes envían mensajes de preparación conflictivos o cuando el proponente no recibe un quórum de respuestas ( Promesa o Aceptación ). En estos casos, se debe iniciar otra ronda con un número de propuesta más alto.

Tenga en cuenta que un Proponente en Paxos podría proponer "Soy el líder" (o, por ejemplo, "El Proponente X es el líder"). ^[20] Debido a las garantías de acuerdo y validez de Paxos, si es aceptado por un Quórum, entonces el Proponente es ahora conocido como el líder por todos los demás nodos. Esto satisface las necesidades de elección de líder ^[21] porque hay un solo nodo que cree que es el líder y un solo nodo conocido como el líder en todo momento.

Los siguientes diagramas representan varios casos/situaciones de aplicación del protocolo Basic Paxos. 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 Aceptante ha aceptado un valor antes en esta ronda).

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

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

Los casos de error más simples son la falla de un Aceptador (cuando un Cuórum de Aceptadores permanece activo) y la falla de un Aprendiz redundante. En estos casos, el protocolo no requiere "recuperación" (es decir, sigue teniendo éxito): no se requieren rondas ni mensajes adicionales, como se muestra a continuación (en los próximos dos diagramas/casos).

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 básico de Paxos aún tiene éxito.

Cliente Proponente Aceptante Aprendiz
   | | | | | | |
   X-------->| | | | | | Solicitud
   | X--------->|->|->| | | Preparar(1)
   | | | | ! | | !! ¡¡FALLÓ!!
   | |<---------X--X | | Promesa(1,{Va, Vb, null})
   | X--------->|->| | | ¡Acepta!(1,V)
   | |<---------X--X--------->|->| Aceptado(1,V)
   |<---------------------------------X--X Respuesta
   | | | | | |

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

Cliente Proponente Aceptante Aprendiz
   | | | | | | |
   X-------->| | | | | | Solicitud
   | X--------->|->|->| | | Preparar(1)
   | |<---------X--X--X | | Promesa(1,{Va,Vb,Vc})
   | X--------->|->|->| | | ¡Acepta!(1,V)
   | |<---------X--X--X------>|->| Aceptado(1,V)
   | | | | | | !! ¡¡FALLÓ!!
   |<---------------------------------X Respuesta
   | | | | | |

En este caso, un Proponente falla después de proponer un valor, pero antes de que se llegue al acuerdo. En concreto, falla en medio del mensaje de Aceptación, por lo que solo un Aceptante del Quórum recibe el valor. Mientras tanto, se elige un nuevo Líder (un Proponente) (pero esto no se muestra en detalle). Nótese que en este caso hay 2 rondas (las rondas se desarrollan verticalmente, de arriba hacia abajo).

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

El caso más complejo es cuando varios Proponentes creen ser Líderes. Por ejemplo, el líder actual puede fallar 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 dado cuenta de esto e intenta comenzar una ronda en conflicto con el líder actual. En el diagrama a continuación, se muestran 4 rondas fallidas, pero podría haber más (como se sugiere en la parte inferior del diagrama).

Cliente Proponente Aceptante Aprendiz
   | | | | | | |
   X----->| | | | | | Solicitud
   | X------------>|->|->| | | Preparar(1)
   | |<------------X--X--X | | Promesa(1,{nulo,nulo,nulo})
   | ! | | | | | !! EL LÍDER FALLA
   | | | | | | | !! NUEVO LÍDER (sabe que el último número era 1)
   | X--------->|->|->| | | Preparar(2)
   | |<---------X--X--X | | Promesa(2,{nulo,nulo,nulo})
   | | | | | | | | !! VIEJO LÍDER se recupera
   | | | | | | | | !! VIEJO LÍDER intenta 2, rechazado
   | X------------>|->|->| | | Preparar(2)
   | |<------------X--X--X | | Nack(2)
   | | | | | | | | !! VIEJO LÍDER intenta 3
   | X------------>|->|->| | | Preparar(3)
   | |<------------X--X--X | | Promesa(3,{nulo,nulo,nulo})
   | | | | | | | | | !! NUEVO LÍDER propone, denegado
   | | 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, denegado
   | X------------>|->|->| | | ¡Acepta!(3,Vb)
   | |<------------X--X--X | | Nack(4)
   | | | | | | | | | ... y así sucesivamente ...

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 Aceptantes que nunca aceptaron V1, lo que le permite proponer V2. Luego, V2 es aceptado por todos los Aceptantes, incluido el que inicialmente aceptó V1.

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

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 Aceptantes que nunca aceptaron V1, lo que le permite proponer V2. Este Proponente logra que un Aceptante 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 Aceptantes lo acepten antes de fallar. En este punto, tres Aceptantes han aceptado V1, pero no para el mismo identificador. Finalmente, un nuevo Proponente prepara la mayoría que no ha visto el identificador aceptado más grande. El valor asociado con el identificador más grande en esa mayoría es V2, por lo que debe proponerlo. Este Proponente luego logra que todos los Aceptantes acepten V2, logrando el consenso.

  Proponente Aceptante Aprendiz
 | | | | | | | | | | |
 X---------------->|->|->|->|->| | | Preparar(1)
 |<----------------X--X--X--X--X | | Promesa(1,{nulo,nulo,nulo,nulo,nulo})
 x--------------->| | | | | | | ¡Aceptar!(1,V1)
 | | | | X------------------>|->| Aceptado(1,V1)
 ! | | | | | | | | | | | !! ¡¡FALLÓ!!
    | | | | | | | | | |
    X---------------->|->|->|->| | | Preparar(2)
    |<---------------X--X--X--X | | Promesa(2,{nulo,nulo,nulo,nulo})
    X--------------->| | | | | | ¡Aceptar!(2,V2)
    | | | | X--------------->|->| Aceptado(2,V2)
    ! | | | | | | | | | | !! ¡¡FALLÓ!!
       | | | | | | | | |
       X--------->|---->|->| | | Preparar(3)
       |<---------X-----X--X--X | | Promesa(3,{V1,nulo,nulo,nulo})
       X---------------->|->| | | | ¡Acepta!(3,V1)
       | | | | X--X--------->|->| Aceptado(3,V1)
       ! | | | | | | | | | !! ¡¡FALLÓ!!
          | | | | | | | |
          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)

En el siguiente caso, un Proponente logra la aceptación del valor V1 de dos Aceptantes antes de fallar. Un nuevo Proponente puede iniciar otra ronda, pero ahora es imposible para ese proponente preparar una mayoría que no incluya al menos un Aceptante que haya aceptado V1. Por lo tanto, aunque el Proponente no vea el consenso existente, la única opción del Proponente 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 Aceptante Aprendiz
 | | | | | | |
 X--------->|->|->| | | Preparar(1)
 |<---------X--X--X | | Promesa(1,{nulo,nulo,nulo})
 x--------->|->| | | | ¡Aceptar!(1,V1)
 | | X--X--------->|->| Aceptado(1,V1)
 ! | | | | | | !! ¡¡FALLÓ!!
    | | | | | |
    X--------->|->| | | Preparar(2)
    |<---------X--X | | Promesa(2,{V1,null})
    X------>|->|->| | | ¡Aceptar!(2,V1)
    |<-------X--X--X------>|->| Aceptado(2,V1)
    | | | | | |

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

Si el líder es relativamente estable, la fase 1 se vuelve innecesaria. Por lo tanto, es posible omitir 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 del mensaje sin fallas (propuesta a aprendizaje) de 4 retrasos a 2 retrasos.

En el siguiente diagrama, se muestra solo 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 básico de Paxos.

Cliente Proponente Aceptante Aprendiz
   | | | | | | | --- Primera petición ---
   X-------->| | | | | | Solicitud
   | X--------->|->|->| | | Preparar(N)
   | |<---------X--X--X | | Promesa(N,I,{Va,Vb,Vc})
   | X--------->|->|->| | | ¡Acepta!(N,I,V)
   | |<---------X--X--X------>|->| Aceptado(N,I,V)
   |<---------------------------------X--X Respuesta
   | | | | | | |

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

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

Cliente Proponente Aceptante Aprendiz
   | | | | | | | --- Siguiendo solicitudes ---
   X-------->| | | | | | Solicitud
   | X--------->|->|->| | | ¡Acepta!(N,I+1,W)
   | |<---------X--X--X------>|->| Aceptado(N,I+1,W)
   |<---------------------------------X--X Respuesta
   | | | | | | |

Una implementación habitual de Multi-Paxos consiste en reducir el papel de los Proponentes, Aceptantes y Estudiantes a “Servidores”. De esta forma, al final, solo quedan “Clientes” y “Servidores”.

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

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

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

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

Se pueden realizar una serie de optimizaciones para reducir la cantidad de mensajes intercambiados, mejorar el rendimiento del protocolo, etc. A continuación se informan algunas de estas optimizaciones.

"Podemos ahorrar mensajes a costa de un retraso de mensaje adicional si tenemos un único aprendiz distinguido que informa a los demás aprendices cuando descubre que se ha elegido un valor. Los aceptantes envían entonces mensajes aceptados sólo al aprendiz distinguido. En la mayoría de las aplicaciones, los roles de líder y aprendiz distinguido los desempeña el mismo procesador. ^[22]

"Un líder puede enviar sus mensajes de ¡Preparación y aceptación! sólo a un quórum de aceptadores. Mientras todos los aceptadores de ese quórum estén trabajando y puedan comunicarse con el líder y los alumnos, no hay necesidad de que los aceptadores que no están en el quórum hagan nada. ^[22]

"A los aceptantes no les importa qué valor se elige. Simplemente responden a los mensajes ¡Preparar! y ¡Aceptar! para asegurarse de que, a pesar de los fallos, sólo se pueda elegir un único valor. Sin embargo, si un aceptante se entera de qué valor se ha elegido, puede almacenar el valor en un almacenamiento estable y borrar cualquier otra información que haya guardado allí. Si el aceptante recibe más tarde un mensaje ¡Preparar ! o ¡Aceptar!, en lugar de realizar su acción de Fase 1b o Fase 2b, puede simplemente 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 de ¡Aceptación!. Un aprendiz aprenderá que v es elegido si recibe mensajes de Aceptación 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 de Promesa que le indiquen el hash de un valor v que debe usar en su acción de Fase2a sin indicarle el valor real de v. Si eso 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 en lugar de a todos los coordinadores. Sin embargo, esto requiere que el resultado del algoritmo de selección del líder se transmita a los proponentes, lo que puede resultar costoso. Por lo tanto, podría ser mejor dejar que el proponente envíe su propuesta a todos los coordinadores. (En ese caso, sólo los propios coordinadores necesitan saber quién es el líder.) ^[15]

"En lugar de que cada aceptante envíe mensajes de aceptación a cada alumno, los aceptantes pueden enviar sus mensajes de aceptación 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]

"Por último, observe que la fase 1 no es necesaria para la ronda 1. El líder de la ronda 1 puede comenzar la ronda enviando un mensaje de ¡Aceptar! con cualquier valor propuesto". ^[15]

Paxos barato extiende Paxos básico 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 de los requisitos de los procesadores se produce a expensas de la vitalidad: si fallan demasiados procesadores principales en poco tiempo, el sistema debe detenerse hasta que los procesadores auxiliares puedan reconfigurarlo. 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 entre un fallo del otro procesador y un 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 actuar sólo en caso de que p o q falle, después de lo cual no hace nada mientras p o q continúa operando el sistema por sí solo. El tercer procesador puede ser, por tanto, un procesador pequeño/lento/barato, o un procesador dedicado principalmente a otras tareas". ^[22]

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 la reconfiguración posterior:

            { Aceptantes }
Proponente Principal Auxiliar Aprendiz
| | | | | | -- Fase 2 --
X----------->|->|->| | | ¡Acepta!(N,I,V)
| | | ! | | --- ¡FALLÓ! ---
|<-----------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)
| | | | |

Fast Paxos generaliza Basic Paxos para reducir los retrasos de mensajes de extremo a extremo. En Basic Paxos, el retraso de mensajes desde la solicitud del cliente hasta el aprendizaje es de 3 retrasos de mensajes. 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 2f+1 clásicos) y (2) 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 mensaje de ¡Acepto! directamente a los Aceptantes. Los Aceptantes responderían como en Paxos Básico, enviando mensajes de Aceptación al líder y a cada Aprendiz, logrando así dos retrasos en el mensaje del Cliente al Aprendiz.

Si el líder detecta una colisión, la resuelve enviando mensajes de ¡Aceptación! 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 Estudiante.

La optimización final se produce cuando el líder especifica una técnica de recuperación de antemano, lo que permite que los aceptadores realicen la recuperación de colisión por sí mismos. Por lo tanto, la recuperación de colisión no coordinada puede ocurrir en tres retrasos de mensajes (y solo dos retrasos de mensajes si todos los aprendices también son aceptadores).

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

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

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

Propuestas contradictorias con una recuperación descoordinada.

Cliente Líder Aceptador Aprendiz
 | | | | | | | | |
 | | X------->|->|->|->| | | Cualquier(N,I,Recuperación)
 | | | | | | | | |
 | | | | | | | | | | !! Propuestas conflictivas concurrentes
 | | | | | | | | | !! recibido en diferente orden
 | | | | | | | | | !! por los Aceptantes
 | X---------------?|-?|-?|-?| | | ¡Acepta!(N,I,V)
 X-----------------?|-?|-?|-?| | | ¡Acepta!(N,I,W)
 | | | | | | | | |
 | | | | | | | | | | !! Los aceptantes no están de acuerdo sobre 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)
 | | | | | | | | |

(roles de Aceptador/Aprendiz fusionados)

Servidores de clientes
 | | | | | |
 | | X->|->|->| Cualquier(N,I,Recuperación)
 | | | | | |
 | | | | | | !! Propuestas conflictivas concurrentes
 | | | | | | !! recibido en diferente orden
 | | | | | | !! por los Servidores
 | X--------?|-?|-?|-?| ¡Acepta!(N,I,V)
 X-----------?|-?|-?|-?| ¡Acepta!(N,I,W)
 | | | | | |
 | | | | | | !! Los servidores no se ponen de acuerdo sobre el valor
 | | X<>X->|->| Aceptado(N,I,V)
 | | |<-|<-X<>X Aceptado(N,I,W)
 | | | | | |
 | | | | | | !! Detecta colisión y recupera
 | | X<>X<>X<>X Aceptado(N+1,I,W)
 |<------------X--X--X--X Respuesta(W)
 | | | | | |

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 involucra optimizaciones de Paxos cuando las propuestas conflictivas podrían aplicarse en cualquier orden, es decir, cuando las operaciones propuestas son operaciones conmutativas para la máquina de estados. En tales casos, las operaciones conflictivas pueden ser aceptadas, evitando los retrasos requeridos para resolver 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 para garantizar que todas las operaciones propuestas de una secuencia se estabilicen antes de permitir que cualquier operación que no conmute con ellas se vuelva estable.

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 estados replicada que implementa operaciones de lectura/escritura en dos registros distintos A y B.

Tenga en cuenta queEn esta tabla se indican las 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 tanto con 3:Write(B)como con 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, el viaje sólo se produce cuando se proponen operaciones simultáneamente.

No se muestran las respuestas. Nota: las abreviaturas de los mensajes difieren de los flujos de mensajes anteriores debido a las particularidades del protocolo; consulte ^[23] para obtener una explicación completa.

Cliente Líder Aceptador Aprendiz
 | | | | | | | | !! Nuevo líder comienza ronda
 | | X----->|->|->| | | Preparar(N)
 | | |<-----X- X- X | | Promesa(N,nulo)
 | | X----->|->|->| | | Phase2Start(N,null)
 | | | | | | | |
 | | | | | | | | | !! Propuestas de desplazamientos simultáneos
 | X------- ?|-----?|-?|-?| | | Proponer(LeerA)
 X-----------?|-----?|-?|-?| | | Proponer(LeerB)
 | | X------X--------------->|->| Aceptado(N,<LecturaA,LecturaB>)
 | | |<--------X--X-------->|->| Aceptado(N,<LecturaB,LecturaA>)
 | | | | | | | |
 | | | | | | | | !! No hay conflicto, se aceptan ambos
 | | | | | | | | Estable = <LecturaA, LecturaB>
 | | | | | | | |
 | | | | | | | | | !! Propuestas concurrentes y contradictorias
 X-----------?|-----?|-?|-?| | | Proponer(<EscrituraB,LecturaA>)
 | X--------?|-----?|-?|-?| | | Proponer(LeerB)
 | | | | | | | |
 | | X------X--------------->|->| Aceptado(N,<EscrituraB,LecturaA> . <LecturaB>)
 | | |<--------X--X-------->|->| Aceptado(N,<LecturaB> . <EscrituraB,LecturaA>)
 | | | | | | | |
 | | | | | | | | !! Conflicto detectado, líder elige
 | | | | | | | | orden conmutativo:
 | | | | | | | | V = <LecturaA, EscrituraB, LecturaB>
 | | | | | | | |
 | | X----->|->|->| | | Fase2Inicio(N+1,V)
 | | |<-----X- X- X-------->|->| Aceptado(N+1,V)
 | | | | | | | | Estable = <LecturaA, LecturaB> .
 | | | | | | | | <LecturaA, EscrituraB, LecturaB>
 | | | | | | | |
 | | | | | | | | | !! Más propuestas conflictivas
 X-----------?|-----?|-?|-?| | | Proponer(WriteA)
 | X--------?|-----?|-?|-?| | | Proponer(LeerA)
 | | | | | | | |
 | | X------X--------------->|->| Aceptado(N+1,<EscrituraA> . <LecturaA>)
 | | |<--------X- X-------->|->| Aceptado(N+1,<LecturaA> . <EscrituraA>)
 | | | | | | | |
 | | | | | | | | !! El líder elige el orden:
 | | | | | | | | W = <EscrituraA, LecturaA>
 | | | | | | | |
 | | X----->|->|->| | | InicioFase2(N+2,W)
 | | |<-----X- X- X-------->|->| Aceptado(N+2,W)
 | | | | | | | | Estable = <LecturaA, LecturaB> .
 | | | | | | | | <LeerA, EscribirB, LeerB> .
 | | | | | | | | <EscrituraA, LecturaA>
 | | | | | | | |

El flujo de mensajes anterior nos muestra que Generalized Paxos puede aprovechar la semántica de operaciones para evitar colisiones cuando falla el orden espontáneo de la red. Esto permite que el protocolo funcione 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 general, estos viajes de ida y vuelta son inevitables y se deben al hecho de que se pueden aceptar múltiples comandos durante una ronda. Esto hace que el protocolo sea más costoso que Paxos cuando los conflictos son frecuentes. Es de esperar que existan dos posibles mejoras de Paxos generalizado para mejorar el tiempo de recuperación. ^[24]

• En primer lugar, si el coordinador es parte de cada quórum de aceptantes (la ronda N se dice centrada ), entonces, para recuperarse en la ronda N+1 de una colisión en la ronda N, el coordinador se saltea la fase 1 y propone en la fase 2 la secuencia que aceptó por última vez durante la ronda N. Esto reduce el costo de recuperación a un solo viaje de ida y vuelta.
• En segundo lugar, si ambas rondas N y N+1 utilizan un quórum centrado único e idéntico, cuando un aceptador detecta una colisión en la ronda N, espontáneamente propone en la ronda N+1 una secuencia que sufije tanto (i) la secuencia aceptada en la ronda N por el coordinador como (ii) el prefijo no conflictivo más grande que aceptó en la ronda N. Por ejemplo, si el coordinador y el aceptador aceptaron respectivamente en la ronda N <WriteB, ReadB> y <ReadB, ReadA>, el aceptador aceptará espontáneamente <WriteB, ReadB, ReadA> en la ronda N+1. Con esta variación, el costo de recuperación es un retraso de un solo mensaje que obviamente es óptimo. Nótese aquí que el uso de un quórum único en una ronda no daña la vitalidad. Esto se debe al hecho de que cualquier proceso en este quórum es un quórum de lectura para la fase de preparación de las próximas rondas. ^[25]

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

Paxos bizantino ^[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:

Cliente Proponente Aceptante Aprendiz
   | | | | | | |
   X-------->| | | | | | Solicitud
   | X--------->|->|->| | | ¡Acepta!(N,I,V)
   | | X<>X<>X | | Verificar(N,I,V) - TRANSMISIÓN
   | |<---------X--X--X------>|->| Aceptado(N,V)
   |<---------------------------------X--X Respuesta(V)
   | | | | | | |

El rápido Paxos bizantino ^[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 Aceptantes y a todos los Estudiantes, mientras que Fast Paxos envía mensajes Aceptados solo a los Estudiantes):

Aprendiz que acepta clientes
   | | | | | |
   X----->|->|->| | | ¡Acepta!(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 F+1 mensajes idénticos de diferentes aceptadores. Si esto no ocurre, los aceptadores también lo sabrán (ya que intercambiaron los mensajes de cada uno en la ronda de transmisión) y los aceptadores correctos volverán a transmitir el valor acordado:

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

Con la aparición de redes de centros de datos confiables y 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 de la capa de red, liberando la CPU del host para otras tareas. La biblioteca Paxos de Derecho C++ 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 a lo largo de 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 estados. Los protocolos Paxos empleados por Derecho necesitaban ser adaptados para maximizar la transmisión asincrónica de datos y eliminar otras fuentes de demora en la ruta crítica del líder. Esto permite a Derecho mantener la tasa de datos RDMA bidireccional completa. Por el contrario, aunque los protocolos Paxos tradicionales se pueden migrar a una red RDMA simplemente asignando las operaciones de envío de mensajes a operaciones RDMA nativas, al hacerlo se dejan demoras de ida y vuelta en la ruta crítica. En redes RDMA de alta velocidad, incluso pequeñas demoras pueden ser lo suficientemente grandes como para evitar la utilización de todo el ancho de banda potencial.

• Google utiliza el algoritmo Paxos en su servicio de bloqueo distribuido Chubby para mantener las réplicas consistentes en caso de falla. ^[29] Chubby es utilizado por Bigtable, que ahora está en producción en Google Analytics y otros productos.
• Google Spanner y Megastore utilizan el algoritmo Paxos internamente.
• El servicio de replicación OpenReplica utiliza Paxos para mantener réplicas para un sistema de acceso abierto que permite a los usuarios crear objetos tolerantes a fallos. Proporciona un alto rendimiento mediante rondas simultáneas y flexibilidad mediante cambios dinámicos de membresía.
• Supuestamente IBM utiliza el algoritmo Paxos en su producto IBM SAN Volume Controller para implementar una máquina virtual tolerante a fallos de propósito general utilizada para ejecutar los componentes de configuración y control de los servicios de virtualización de almacenamiento ofrecidos por el clúster. ^[30]
• Microsoft utiliza Paxos en el servicio de administración de clústeres Autopilot de Bing y en Windows Server Failover Clustering. ^[31]
• WANdisco ha implementado Paxos dentro de su tecnología de replicación activa-activa DConE. ^[32]
• XtreemFS utiliza un algoritmo de negociación de arrendamiento basado en Paxos para la replicación tolerante a fallas y consistente de datos de archivos y metadatos. ^[33]
• Heroku utiliza Doozerd, que implementa Paxos para su almacén de datos distribuido consistente.
• Ceph utiliza Paxos como parte de los procesos de monitorización para acordar qué OSD están activos y en el clúster.
• La base de datos SQL distribuida MariaDB Xpand utiliza Paxos para la resolución de transacciones distribuidas. ^[34]
• La base de datos gráfica HA de Neo4j implementa Paxos, reemplazando a Apache ZooKeeper de la versión 1.9
• La base de datos NoSQL Apache Cassandra utiliza Paxos solo para la función de transacciones livianas. ^[35]
• La base de datos NoSQL ScyllaDB utiliza Paxos para transacciones ligeras. ^[36]
• Amazon Elastic Container Services utiliza Paxos para mantener una visión consistente del estado del clúster. ^[37]
• Amazon DynamoDB utiliza el algoritmo Paxos para la elección de líderes y el consenso. ^[38]

• Problema de dos generales
• Algoritmo de consenso Chandra-Toueg
• Máquina de estados
• Balsa