Paxos (informática)

En 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 ponerse de acuerdo sobre un resultado entre un grupo de participantes. Este problema se complica cuando los participantes o sus comunicaciones pueden sufrir fallos. ^{[ 1 ]}

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

El protocolo de Paxos se presentó por primera vez en 1989 y recibió su nombre de un sistema ficticio de consenso legislativo utilizado en la isla griega de Paxos , donde Lamport escribió que el parlamento debía funcionar "aunque 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 abarca un espectro de compensaciones entre el número de procesadores, el número de retrasos en los mensajes antes de conocer el valor acordado, el nivel de actividad de los participantes individuales, el número de mensajes enviados y los tipos de fallos. Si bien ningún protocolo de consenso tolerante a fallos determinista 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 impedir su progreso son difíciles de provocar.

Paxos se suele utilizar cuando se requiere durabilidad (por ejemplo, para replicar un archivo o una base de datos ), donde la cantidad de estado persistente puede ser grande. El protocolo intenta avanzar incluso durante los períodos en que un número limitado de réplicas no responde. También existe un mecanismo para descartar una réplica que ha fallado permanentemente o para añadir una nueva.

En 1988, Lynch , Dwork y Stockmeyer demostraron la resolubilidad del consenso en una amplia familia de sistemas "parcialmente síncronos". ^{[ 7 ]} Paxos tiene similitudes con un protocolo utilizado para el acuerdo en la "replicación con marca de vista", publicado por primera vez por Oki y Liskov en 1988, en el contexto de transacciones distribuidas. ^{[ 8 ]} Paxos ofreció un formalismo elegante e incluyó una de las primeras pruebas de seguridad para un protocolo de consenso distribuido tolerante a fallos.

Las máquinas de estado reconfigurables tienen vínculos con trabajos previos sobre protocolos de multidifusión de grupo confiables que admiten la pertenencia dinámica a grupos, por ejemplo, el trabajo de Birman en 1985 y 1987 sobre el protocolo gbcast virtualmente síncrono ^{[ 9 ]} . gbcast es poco común en cuanto a la durabilidad y el manejo de fallas de particionamiento. La mayoría de los protocolos de multidifusión confiables no poseen estas propiedades, las cuales son necesarias para las implementaciones del modelo de replicación de máquinas de estado. Este punto se analiza en un artículo de Lamport , Malkhi y Zhou ^{[ 10 ] .}

Los protocolos Paxos pertenecen a una clase teórica de soluciones a un problema formalizado como acuerdo uniforme con fallos por caída. Keidar y Shraer demostraron cotas inferiores para este problema . ^{[ 11 ]} Derecho, ^{[ 12 ]} una biblioteca de software en C++ para la replicación de máquinas de estado a escala de nube, ofrece un protocolo Paxos integrado con membresía virtualmente síncrona autogestionada. Este protocolo cumple con las cotas de optimalidad de Keidar y Shraer y se adapta eficientemente al hardware moderno de centros de datos con DMA remoto (RDMA) . Utiliza TCP si RDMA no está disponible.

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

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

Validez (o no trivialidad )

Solo se pueden elegir y aprender los valores propuestos. ^{[ 15 ]}

Acuerdo (o coherencia , o seguridad )

No puede haber dos aprendices distintos aprender 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 aprendiz L aprenderá algún valor (si quedan suficientes procesadores sin fallas). ^{[ 16 ]}

Cabe destacar que Paxos no garantiza la terminación y, por lo tanto, carece de la propiedad de vivacidad. Esto se confirma con el resultado de imposibilidad de Fischer-Lynch-Paterson (FLP) ^{[ 6 ]} , que establece que un protocolo de consistencia solo puede tener dos de las siguientes propiedades: seguridad , vivacidad y tolerancia a fallos . Dado que el objetivo de Paxos es garantizar la tolerancia a fallos y la seguridad, no puede garantizar también la vivacidad.

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 y le asigna un nuevo número de comando.${\displaystyle i}$y luego comienza el${\displaystyle i}$^la instancia del algoritmo de consenso mediante el envío de mensajes a un conjunto de procesos aceptadores. ^{[ 16 ]}

Al fusionar roles, el protocolo "colapsa" en un despliegue eficiente de estilo cliente-maestro-réplica, típico 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 describe 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 Paxos básico determina un único valor de salida. El protocolo se desarrolla en varias rondas. Una ronda exitosa consta de dos fases: la fase 1 (dividida en partes a y b ) y la fase 2 (también dividida en partes a y b ). A continuación se describe cada fase. Cabe recordar que se asume un modelo asíncrono, por lo que, por ejemplo, un procesador puede estar en una fase mientras otro se encuentra en otra.

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 Paxos básico gestiona el fallo de ciertos componentes (redundantes) del sistema distribuido.

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

Paxos básico sin fallos

En el diagrama a continuación, hay 1 Cliente, 1 Proponente, 3 Aceptadores (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 exitosa (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 sencillos son el fallo de un Aceptador (cuando un Quórum de Aceptadores permanece activo) y el fallo 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 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 sigue funcionando correctamente.

Cliente Proponente Aceptador Aprendiz | | | | | | | X-------->| | | | | | Solicitud | X--------->|->|->| | | Preparar(1) | | | | ! | | !! FALLO !! | |<---------X--X | | Promise(1,{Va, Vb, null}) | X--------->|->| | | ¡Aceptar!(1,V) | |<---------X--X--------->|->| Aceptado(1,V) |<---------------------------------X--X Respuesta | | | | | | 

Paxos básico cuando falla un aprendiz redundante

En el siguiente caso, uno de los aprendices (redundantes) falla, pero el protocolo Paxos básico sigue funcionando correctamente.

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

Paxos básico cuando falla un proponente

En este caso, un proponente falla tras proponer un valor, pero antes de que se alcance el acuerdo. Concretamente, 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) (aunque esto no se muestra en detalle). Cabe destacar que hay dos rondas (que se suceden verticalmente, de arriba abajo).

Cliente Proponente Aceptador Aprendiz | | | | | | | X----->| | | | | | Solicitud | X------------>|->|->| | | Preparar(1) | |<------------X--X--X | | Promise(1,{Va, Vb, Vc}) | | | | | | | | | | | | | | !! El líder falla durante la transmisión !! | X------------>| | | | | ¡Aceptar!(1,V) | ! | | | | | | | | | | | | ¡¡NUEVO LÍDER!! | X--------->|->|->| | | Preparar(2) | |<---------X--X--X | | Promise(2,{V, null, null}) | X--------->|->|->| | | ¡Aceptar!(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 se da cuando varios proponentes se consideran líderes. Por ejemplo, el líder actual puede fracasar y luego recuperarse, pero los demás proponentes ya han elegido a un nuevo líder. El líder recuperado aún no se ha enterado y trata de iniciar una ronda en conflicto con el líder actual. En el diagrama a continuación, se muestran cuatro rondas fallidas, pero podría haber más (como se sugiere al pie del diagrama).

Cliente Proponente Aceptador Aprendiz | | | | | | | X----->| | | | | | Solicitud | X------------>|->|->| | | Preparar(1) | |<------------X--X--X | | Promise(1,{null,null,null}) | ! | | | | | !! EL LÍDER FALLA | | | | | | | !! NUEVO LÍDER (sabe que el último número fue 1) | X--------->|->|->| | | Preparar(2) | |<---------X--X--X | | Promise(2,{null,null,null}) | | | | | | | | !! EL VIEJO LÍDER se recupera | | | | | | | | !! EL VIEJO LÍDER intenta 2, rechazado | X------------>|->|->| | | Preparar(2) | |<------------X--X--X | | Nack(2) | | | | | | | | !! EL VIEJO LÍDER intenta 3 | X------------>|->|->| | | Preparar(3) | |<------------X--X--X | | Promise(3,{null,null,null}) | | | | | | | | !! El NUEVO LÍDER propone, niega | | X--------->|->|->| | | ¡Aceptar!(2,Va) | | |<---------X--X--X | | Nack(3) | | | | | | | | !! NUEVO LÍDER intenta 4 | | X--------->|->|->| | | Preparar(4) | | |<---------X--X--X | | Promise(4,{null,null,null}) | | | | | | | | !! El VIEJO LÍDER propone, niega | X------------>|->|->| | | ¡Aceptar!(3,Vb) | |<------------X--X--X | | Nack(4) | | | | | | | | ... y así sucesivamente ... 

Paxos básico donde un aceptador acepta dos valores diferentes.

En el siguiente caso, un Proponente logra que un Aceptador acepte el valor V1 antes de fallar. Un nuevo Proponente prepara a los Aceptadores que nunca aceptaron V1, lo que le permite proponer V2. Entonces, V2 es aceptado por todos los Aceptadores, incluido el que inicialmente aceptó V1.

Proponente Aceptador Aprendiz | | | | | | | X--------->|->|->| | | Preparar(1) |<---------X--X--X | | Promise(1,{null,null,null}) x--------->| | | | | ¡Aceptar!(1,V1) | | X------------>|->| Aceptado(1,V1) ¡¡ | | | | | | !! ¡¡FALLO!! | | | | | | X--------->|->| | | Preparar(2) |<---------X--X | | Promise(2,{null,null}) X------>|->|->| | | ¡Aceptar!(2,V2) |<------X--X--X------>|->| Aceptado(2,V2) | | | | | | 

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

En el siguiente caso, un Proponente logra la aceptación del valor V1 por parte de un Aceptador antes de fallar. Un nuevo Proponente prepara a los Aceptadores que nunca aceptaron V1, lo que le permite proponer V2. Este Proponente logra que un Aceptador acepte V2 antes de fallar. Un nuevo Proponente encuentra una mayoría que incluye al Aceptador que aceptó 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 identificador aceptado de mayor valor. El valor asociado al identificador de mayor valor en esa mayoría es V2, por lo que debe proponerlo. Este Proponente logra entonces que todos los Aceptadores acepten V2, alcanzando así el consenso.

 Proponente Aceptador Aprendiz | | | | | | | | | | | X--------------->|->|->|->|->| | | Preparar(1) |<---------------X--X--X--X--X | | Promise(1,{null,null,null,null,null}) x--------------->| | | | | | | ¡Aceptar!(1,V1) | | | | X------------------>|->| Aceptado(1,V1) ¡¡ | | | | | | | | | | !! ¡¡FALLO!! | | | | | | | | | | X--------------->|->|->|->| | | Preparar(2) |<---------------X--X--X--X | | Promise(2,{null,null,null,null}) X--------------->| | | | | | ¡Aceptar!(2,V2) | | | | X--------------->|->| Aceptado(2,V2) ¡¡ | | | | | | | | | !! ¡¡FALLO!! | | | | | | | | | X--------->|---->|->|->| | | Preparar(3) |<---------X-----X--X--X | | Promise(3,{V1,null,null,null}) X--------------->|->| | | | ¡Aceptar!(3,V1) | | | | X--X--------->|->| Aceptado(3,V1) ¡¡ | | | | | | | | !! ¡¡FALLO!! | | | | | | | | X------>|->|------->| | | Preparar(4) |<------X--X--|--|--X | | Promise(4,{V1(1),V2(2),null}) X------>|->|->|->|->| | | ¡Aceptar!(4,V2) | X--X--X--X--X------>|->| Aceptado(4,V2) 

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

En el siguiente caso, un Proponente logra la aceptación del valor V1 por parte de dos Aceptadores antes de fallar. Un nuevo Proponente puede iniciar otra ronda, pero ahora le resulta imposible preparar una mayoría que no incluya al menos un Aceptador que haya aceptado V1. Por lo tanto, aunque el Proponente no vea el consenso existente, su única opción es proponer el valor ya acordado. Los nuevos Proponentes pueden incrementar continuamente el identificador para reiniciar el proceso, pero el consenso nunca podrá modificarse.

Proponente Aceptador Aprendiz | | | | | | | X--------->|->|->| | | Preparar(1) |<---------X--X--X | | Promise(1,{null,null,null}) x--------->|->| | | | ¡Aceptar!(1,V1) | | X--X--------->|->| Aceptado(1,V1) ¡¡ | | | | | | !! ¡¡FALLO!! | | | | | | X--------->|->| | | Preparar(2) |<---------X--X | | Promise(2,{V1,null}) X------>|->|->| | | ¡Aceptar!(2,V1) |<------X--X--X------>|->| Aceptado(2,V1) | | | | | | 

Un despliegue típico 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 sobrecarga considerable.

Si el líder es relativamente estable, la fase 1 resulta innecesaria. Por lo tanto, es posible omitir la fase 1 en futuras instancias del protocolo con el mismo líder.

Para lograr esto, se incluye el número de ronda I junto con cada valor, el cual es incrementado en cada ronda por el mismo Líder. Multi-Paxos reduce el retraso del mensaje sin fallos (desde la propuesta hasta el aprendizaje) de 4 retrasos a 2 retrasos.

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

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

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

Servidores cliente X-------->| | | Solicitud | X->|->| ¡Aceptar!(N,I+1,W) | X<>X<>X Aceptado(N,I+1) |<--------X | | Respuesta | | | | 

Se pueden realizar diversas optimizaciones para reducir el número de mensajes intercambiados, mejorar el rendimiento del protocolo, etc. A continuación se describen algunas de estas optimizaciones.

Podemos ahorrar mensajes a costa de un retraso adicional al tener un único aprendiz distinguido que informe a los demás aprendices cuando detecte que se ha elegido un valor. Los aceptadores envían entonces mensajes de aceptación únicamente al aprendiz distinguido. En la mayoría de las aplicaciones, las funciones de líder y aprendiz distinguido las desempeña el mismo procesador. ^{[ 22 ]}

"Un líder puede enviar sus mensajes de ¡Prepárate y acepta! solo a un quórum de aceptadores. Siempre que todos los aceptadores de ese quórum estén trabajando y puedan comunicarse con el líder y los aprendices, no es necesario que los aceptadores que no pertenecen al quórum hagan nada. ^{[ 22 ]}

"A los aceptadores no les importa qué valor se elija. Simplemente responden a los mensajes Prepare y Accept! para asegurar que, a pesar de los fallos, solo se pueda elegir un único valor. Sin embargo, si un aceptador descubre qué valor se ha elegido, puede almacenarlo en memoria estable y borrar cualquier otra información que haya guardado allí. Si el aceptador recibe posteriormente un mensaje Prepare o Accept!, en lugar de realizar su acción Phase1b o Phase2b, 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 aceptadores en sus mensajes Accept!. Un aprendiz sabrá que v ha sido elegido si recibe mensajes Accepted para v o su hash de un quórum de aceptadores, 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 indicarle el valor real de v. Si eso sucede, el líder no puede ejecutar su acción Phase2a hasta que se comunique con algún proceso que conozca v." ^{[ 22 ]}

"Un proponente puede enviar su propuesta solo 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 cual podría ser costoso. Por lo tanto, podría ser mejor permitir que el proponente envíe su propuesta a todos los coordinadores. (En ese caso, solo los coordinadores necesitan saber quién es el líder). ^{[ 15 ]}

En lugar de que cada receptor envíe mensajes de aceptación a cada aprendiz, los receptores pueden enviar sus mensajes de aceptación al líder, y este puede informar a los aprendices cuando se haya elegido un valor. Sin embargo, esto añade un retraso adicional en la transmisión de mensajes. ^{[ 15 ]}

"Finalmente, 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 Accept! con cualquier valor propuesto." ^{[ 15 ]}

Cheap Paxos extiende Basic Paxos para tolerar F fallos con F+1 procesadores principales y F procesadores auxiliares, reconfigurándose dinámicamente después de cada fallo.

Esta reducción en los requisitos de procesamiento se logra a expensas de la disponibilidad; si fallan demasiados procesadores principales en un corto período de 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 solo dos procesadores, p y q, uno de ellos no puede distinguir entre el fallo del otro y el fallo del medio de comunicación. Se necesita un tercer procesador. Sin embargo, este tercer procesador no tiene por qué participar en la elección de la secuencia de comandos. Debe actuar únicamente en caso de que falle p o q, tras lo cual no hace nada mientras p o q continúan operando el sistema por sí solos. Por lo tanto, el tercer procesador puede ser pequeño, lento o económico, o bien un procesador dedicado principalmente a otras tareas." ^{[ 22 ]}

 { Aceptadores } Proponente Principal Auxiliar Aprendiz | | | | | | -- Fase 2 -- X----------->|->|->| | | ¡Aceptar!(N,I,V) | | | ! | | --- ¡FALLO! --- |<-----------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 fallos (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 nada valioso que proponer, un cliente podría enviar un mensaje de «¡Acepto!» directamente a los Aceptadores. Estos responderían como en Paxos básico, enviando mensajes de «Aceptado» al líder y a cada Aprendiz, logrando así dos retrasos de mensaje entre el Cliente y el Aprendiz.

Si el líder detecta una colisión, la resuelve enviando mensajes de "Aceptar" para una nueva ronda, los cuales se aceptan como de costumbre. Esta técnica de recuperación coordinada requiere cuatro retrasos de mensajes entre el cliente y el aprendiz.

La optimización final se produce cuando el líder especifica una técnica de recuperación con antelación, lo que permite a los Aceptadores realizar la recuperación de la colisión por sí mismos. De este modo, la recuperación de colisiones no coordinada puede producirse en tres retrasos de mensajes (y en solo dos retrasos si todos los Aprendices también son Aceptadores).

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

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

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

Servidores cliente | | | | | | | | X->|->|->| Cualquiera(N,I,Recuperación) | | | | | | | | | | | | !! Propuestas contradictorias simultáneas | | | | | | !! recibido en diferente orden | | | | | | !! por los servidores | X--------?|-?|-?|-?| ¡Aceptar!(N,I,V) X-----------?|-?|-?|-?| ¡Aceptar!(N,I,W) | | | | | | | | | | | | !! Los servidores no están de acuerdo en el valor | | X<>X->|->| Aceptado(N,I,V) | | |<-|<-X<>X Aceptado(N,I,W) | | | | | | | | | | | | !! Detectar colisión y recuperar | | 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 principal descubrimiento implica optimizaciones de Paxos cuando las propuestas conflictivas pueden aplicarse en cualquier orden, es decir, cuando las operaciones propuestas son conmutativas para la máquina de estados. En tales casos, ambas operaciones conflictivas pueden aceptarse, evitando las demoras necesarias 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 realiza un seguimiento de estas secuencias, asegurándose de que todas las operaciones propuestas de una secuencia se estabilicen antes de permitir que cualquier operación que no conmute con ellas se estabilice.

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

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

Cliente Líder Aceptador Aprendiz | | | | | | | | !! Nuevo líder comienza ronda | | X----->|->|->| | | Preparar(N) | | |<-----X- X- X | | Promise(N,null) | | X----->|->|->| | | Phase2Start(N,null) | | | | | | | | | | | | | | | | !! Propuestas de desplazamiento simultáneo | X------- ?|-----?|-?|-?| | | Proponer(LeerA) X-----------?|-----?|-?|-?| | | Proponer(LeerB) | | X------X-------------->|->| Aceptado(N,<LeerA,LeerB>) | | |<--------X--X-------->|->| Aceptado(N,<LeerB,LeerA>) | | | | | | | | | | | | | | | | !! Sin conflicto, ambos aceptados | | | | | | | | Estable = <LeerA, LeerB> | | | | | | | | | | | | | | | | !! Propuestas contradictorias simultáneas X-----------?|-----?|-?|-?| | | Proponer(<EscribirB,LeerA>) | X--------?|-----?|-?|-?| | | Proponer(LeerB) | | | | | | | | | | X------X-------------->|->| Aceptado(N,<WriteB,ReadA> . <ReadB>) | | |<--------X--X-------->|->| Aceptado(N,<LeerB> . <EscribirB,LeerA>) | | | | | | | | | | | | | | | | !! Conflicto detectado, el líder elige | | | | | | | | orden conmutativo: | | | | | | | | V = <LeerA, EscribirB, LeerB> | | | | | | | | | | X----->|->|->| | | Phase2Start(N+1,V) | | |<-----X- X- X-------->|->| Aceptado(N+1,V) | | | | | | | | Estable = <LeerA, LeerB> . | | | | | | | | <LeerA, EscribirB, LeerB> | | | | | | | | | | | | | | | | !! Más propuestas contradictorias X-----------?|-----?|-?|-?| | | Proponer(EscribirA) | X--------?|-----?|-?|-?| | | Proponer(LeerA) | | | | | | | | | | X------X-------------->|->| Aceptado(N+1,<WriteA> . <ReadA>) | | |<--------X- X-------->|->| Aceptado(N+1,<LeerA> . <EscribirA>) | | | | | | | | | | | | | | | | !! El líder elige el orden: | | | | | | | | W = <WriteA, ReadA> | | | | | | | | | | X----->|->|->| | | Phase2Start(N+2,W) | | |<-----X- X- X-------->|->| Aceptado(N+2,W) | | | | | | | | Estable = <LeerA, LeerB> . | | | | | | | | <LeerA, EscribirB, LeerB> . | | | | | | | | <EscribirA, LeerA> | | | | | | | | 

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

La Paxos bizantina ^{[ 27 ]} introducida por Castro y Liskov agrega un mensaje extra (Verificar) que actúa para distribuir conocimiento y verificar las acciones de los otros procesadores:

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

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

Cliente Aceptador Aprendiz | | | ! | | !! Un receptor está defectuoso X----->|->|->! | | ¡Aceptar!(N,I,V) | X<>X<>X------>|->| Aceptado(N,I,{V,W}) - TRANSMISIÓN | | | ! | | !! Los alumnos reciben 2 comandos diferentes | | | ! | | !! Los aceptadores correctos notan un 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 de alta velocidad y gran fiabilidad que admiten DMA remoto ( RDMA ), ha habido un gran interés en optimizar Paxos para aprovechar la descarga de hardware, en la que la tarjeta de interfaz de red y los enrutadores de red proporcionan fiabilidad y control de la congestión de la capa de red, liberando así la CPU del host para otras tareas. La biblioteca Derecho C++ Paxos es una implementación de código abierto de Paxos que explora esta opción. ^{[ 12 ]}

Derecho ofrece tanto un Paxos clásico, con durabilidad de datos tras ciclos completos de apagado/reinicio, como un Paxos vertical (multidifusión atómica), para replicación en memoria y sincronización de máquinas de estado. Los protocolos Paxos empleados por Derecho debían adaptarse para maximizar la transmisión asíncrona de datos y eliminar otras fuentes de retardo en la ruta crítica del líder. De este modo, Derecho puede mantener la velocidad de datos RDMA bidireccional completa. En cambio, si bien los protocolos Paxos tradicionales pueden migrarse a una red RDMA simplemente asignando las operaciones de envío de mensajes a operaciones RDMA nativas, esto genera retardos de ida y vuelta en la ruta crítica. En redes RDMA de alta velocidad, incluso pequeños retardos pueden ser lo suficientemente grandes como para impedir la utilización de todo el ancho de banda potencial.

• Google utiliza el algoritmo Paxos en su servicio de bloqueo distribuido Chubby para mantener la coherencia de las réplicas en caso de fallo. ^{[ 29 ]} Chubby es utilizado por Bigtable, que ahora está en producción en Google Analytics y otros productos.
• Google Spanner y Megastore utilizan internamente el algoritmo Paxos.
• El servicio de replicación OpenReplica utiliza Paxos para mantener réplicas de un sistema de acceso abierto que permite a los usuarios crear objetos tolerantes a fallos. Ofrece un alto rendimiento mediante rondas concurrentes y flexibilidad gracias a los 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 que se utiliza para ejecutar los componentes de configuración y control de los servicios de virtualización de almacenamiento que ofrece 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 fallos y consistente de datos y metadatos de archivos. ^{[ 33 ]}
• Heroku utiliza Doozerd, que implementa Paxos para su almacenamiento de datos distribuido y consistente.
• Ceph utiliza Paxos como parte de los procesos de monitorización para determinar qué OSD están activos y forman parte del clúster.
• La base de datos SQL distribuida MariaDB Xpand utiliza Paxos para la resolución de transacciones distribuidas . ^{[ 34 ]}
• La base de datos de grafos Neo4j HA implementa Paxos, reemplazando a Apache ZooKeeper a partir de la versión 1.9.
• La base de datos NoSQL Apache Cassandra utiliza Paxos únicamente para la función de transacciones ligeras. ^{[ 35 ]}
• La base de datos NoSQL ScyllaDB utiliza Paxos para transacciones ligeras. ^{[ 36 ]}
• Amazon Elastic Container Services utiliza Paxos para mantener una vista coherente del estado del clúster. ^{[ 37 ]}
• Amazon DynamoDB utiliza el algoritmo Paxos para la elección de líder y el consenso. ^{[ 38 ]}

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