Mejor respuesta
Este artículo proporciona una explicación y una prueba sorprendentemente claras: http://pdos.csail.mit.edu/6.824/papers/paxos-simple.pdf
Intentaré proporcionar un resumen claro aquí:
El objetivo del El algoritmo de Paxos sirve para que algunos pares lleguen a un acuerdo sobre un valor. Paxos garantiza que si un par cree que la mayoría ha acordado algún valor, la mayoría nunca acordar un valor diferente. El protocolo está diseñado para que cualquier acuerdo deba ir a través de una mayoría de nodos. Cualquier intento futuro de acuerdo, si tiene éxito, también debe pasar por al menos uno de esos nodos. Por lo tanto: Cualquier nodo que proponga después de que se haya tomado una decisión debe comunicarse con un nodo en la mayoría. El protocolo garantiza que aprenderá las ag basarse en el valor de esa mayoría.
Así es como funciona:
Supongamos que tenemos 3 nodos, A, B y C. A le gustaría proponer el valor «Foo».
El algoritmo opera en 3 fases. En cada fase, se debe alcanzar la afirmación de la mayoría de los nodos.
Primero, tenemos la fase de preparación. A envía una solicitud de preparación a A, B y C. Paxos se basa en números de secuencia para lograr sus garantías. La solicitud de preparación le pide a un nodo que prometa: «Nunca aceptaré ninguna propuesta con un número de secuencia menor que el de la solicitud de preparación». Los nodos responden con cualquier valor que hayan acordado previamente (si corresponde). (Y esto es de suma importancia): El nodo A debe proponer el valor que recibe con el número de secuencia más alto. Esta acción proporciona la garantía de que se conservarán los valores acordados previamente.
A continuación, tenemos la fase de aceptación. A envía una solicitud de aceptación a A, B y C. La solicitud de aceptación indica: » ¿Aceptas foo? » Si el número de secuencia adjunto no está por debajo de lo que el nodo había prometido previamente o la solicitud que el nodo ha aceptado previamente, aceptará el nuevo valor y número de secuencia.
Si el nodo A recibe acepta de la mayoría de los nodos, se decide el valor. Esta ronda de Paxos nunca estará de acuerdo con otro valor.
La tercera fase no es estrictamente necesaria, pero es crucial optimización en cualquier implementación de Paxos producida. Después de que A recibe la mayoría de las aceptaciones, envía mensajes decididos a A, B y C. Estos mensajes permiten que todos los pares sepan que se ha elegido un valor y aceleran el final del proceso de decisión.
Sin este mensaje, los demás compañeros tendrían que intentar proponer un valor para conocer el acuerdo. En la fase de preparación, se enterarían del valor acordado previamente. Una vez que el acuerdo llegara a su conclusión, el nodo reconocería el acuerdo.
He pasado por alto algunos aspectos clave aquí:
- Todos los números de secuencia deben aumentar monótonamente y ser únicos por nodo . Es decir, A y B no pueden enviar un mensaje con el número de secuencia k. Todos los mensajes enviados en el protocolo incluyen números de secuencia. Un nodo debe rastrear la solicitud de aceptación más alta que ha visto, así como el valor más alto que ha prometido en la fase de preparación.
- Condiciones de falla. Es muy posible que una ronda de Paxos falle. En caso de falla, un nodo simplemente intenta proponer nuevamente con un número de secuencia más alto.
- Condiciones de terminación. La versión de Paxos que he descrito no necesariamente termina. Se requieren algunos ajustes para una prueba formal de terminación.
Respuesta
Dado que Paxos logra el consenso, también se puede usar para replicar escrituras en una base de datos distribuida, ya que puede garantizar un orden coherente de eventos entre todos los nodos de un grupo. Chubby de Google usa Paxos para entregar archivos de gran coherencia. De aquí es de donde surge la confusión. ¿Cuál es entonces la relación entre la sincronía de vistas y los paxos si ambos pueden usarse para la replicación?
Poca historia: Lamport introdujo el concepto de replicación de máquinas de estado a principios de los 80. La replicación de la máquina de estado significa que un sistema entrega eventos en el mismo orden a todos los nodos y se procesan de manera determinista garantizando estados consistentes en todos los nodos del grupo. Sin embargo, en el momento en que se introdujo este concepto, implicaba todo tipo de suposiciones, incluida la sincronización de la red.Entonces, la replicación de la máquina de estado simplemente siguió siendo una herramienta teórica sin uso práctico. La sincronización de vistas se introdujo en este punto y tenía como objetivo lograr la coherencia al no hacer tales suposiciones. El objetivo era tener un sistema práctico que brindara tales garantías.
La publicación de Paxos se realizó mientras el trabajo sobre sincronía de vista estaba en curso. Paxos podría lograr la replicación de la máquina de estado, ya que las réplicas ahora podrían acordar el orden de ejecución de las solicitudes de los clientes utilizando este algoritmo de consenso. Paxos no hizo suposiciones de red síncrona o fallas. Paxos también proporcionó un protocolo de membresía grupal. Las diferencias que ahora permanecían entre la sincronía de vistas y Paxos estaban solo en la forma en que se formularon las abstracciones. Ambos proporcionan membresía dinámica y manejan fallas de manera similar. Las diferencias están realmente solo en el modelo. Algunas diferencias que se pueden destacar son:
- Virtual Synchrony tiene un protocolo de membresía de grupo simple en comparación con Paxos. La sincronización virtual ejecuta la membresía de grupo como un servicio separado.
- Paxos puede progresar en ciertos casos de partición donde la sincronización virtual bloquea.
- La sincronización virtual es más rápida que los Paxos contemporáneos.
Ambos sistemas han evolucionado y convergido . En la forma actual, es muy difícil establecer diferencias significativas entre los dos.
Lalith explica claramente el protocolo de Sincronía Virtual y señala acertadamente que Paxos o cualquier otra variante de consenso puede usarse en la sincronía de vista. Paxos, además del consenso, proporciona membresía grupal y otras características que la sincronización virtual ya proporciona. Dado que tanto la sincronía virtual como Paxos brindan las mismas garantías y se desarrollaron aproximadamente al mismo tiempo, la especificación de sincronía virtual no utiliza Paxos para el consenso. Sin embargo, el modelo de sincronía virtual usa el protocolo de envío totalmente ordenado (también conocido como ABCAST) para lograr la transmisión atómica y otro protocolo para actualizar las vistas de grupo, y estos pueden verse como la variante de consenso que usa.
Puede ser interesante notar que el modelo de tiempo de ejecución de ISIS-2 combina el modelo de Paxos con el modelo de sincronía virtual, no por consenso sino para factorizar la membresía de grupo como un servicio separado en Paxos. Esto hace que Paxos sea más rápido en los casos en que la membresía no cambia dinámicamente. Al combinar Virtual Synchrony y Paxos, ISIS2 puede omitir ciertos pasos que los Paxos típicos deben realizar. En esencia, Paxos y Virtual Synchrony son modelos diferentes para lograr la misma funcionalidad y pueden combinarse entre sí para lograr variantes u optimizaciones.