Paxos es una familia de protocolos para resolver consensos en una red de procesadores no confiables o falibles. El consenso es el proceso de acordar un resultado entre un grupo de participantes. Este problema se vuelve difícil cuando los participantes o sus comunicaciones pueden experimentar fallas. [1]
Los protocolos de consenso son la base para el enfoque de replicación de máquinas de estado para la computación distribuida, como sugirió Leslie Lamport [2] y estudió Fred Schneider . [3] La replicación de la máquina de estado 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 de 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 tolerante a fallas determinista puede garantizar el progreso en una red asincrónica (un resultado probado en un artículo de Fischer , Lynch y Paterson [6] ), Paxos garantiza la seguridad (consistencia) y las condiciones que podrían impedir que avance. son difíciles de provocar.
Paxos se usa 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 progresar incluso durante los períodos en los que un número limitado de réplicas no responde. También existe un mecanismo para eliminar una réplica que falla permanentemente o para agregar una nueva réplica.
Historia
El tema es anterior al protocolo. En 1988, Lynch , Dwork y Stockmeyer habían demostrado [7] la solubilidad del consenso en una amplia familia de sistemas "parcialmente sincrónicos". 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 transacciones distribuidas. [8] A pesar de este trabajo anterior, 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 de grupo confiables que admiten la pertenencia a grupos dinámicos, por ejemplo , el trabajo de Birman en 1985 y 1987 sobre el protocolo gbcast [9] virtualmente sincrónico . Sin embargo, gbcast es inusual para admitir durabilidad y abordar fallas de particiones. 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 estado. Este punto está elaborado 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 por colisión. Keidar y Shraer han demostrado límites inferiores para este problema. [11] Derecho, [12] una biblioteca de software C ++ para la replicación de máquinas de estado a escala de nube, ofrece un protocolo Paxos que se ha integrado con membresía virtualmente sincrónica autogestionada. Este protocolo coincide con los límites de optimización de Keidar y Shraer, y se asigna de manera eficiente al hardware del centro de datos DMA remoto (RDMA) moderno (pero usa TCP si RDMA no está disponible).
Supuestos
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
- Los procesadores funcionan a velocidades arbitrarias.
- 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 de fallas).
- Los procesadores no se confabulan, mienten o intentan de otra manera subvertir el protocolo. (Es decir, las fallas bizantinas no ocurren. Consulte Paxos bizantinos para obtener una solución que tolera fallas que surgen de un comportamiento arbitrario / malicioso de los procesos).
La red
- Los procesadores pueden enviar mensajes a cualquier otro procesador.
- Los mensajes se envían de forma asincrónica y pueden tardar arbitrariamente en entregarse.
- Los mensajes se pueden perder, reordenar o duplicar.
- Los mensajes se entregan sin corrupción. (Es decir, las fallas bizantinas no ocurren. Consulte Paxos bizantinos para obtener una solución que tolera los mensajes corruptos que surgen de un comportamiento arbitrario / malicioso de los canales de mensajería).
Numero de procesadores
En general, un algoritmo de consenso puede avanzar utilizando procesadores, a pesar de la falla simultánea de cualquier procesadores: [13] en otras palabras, el número de procesos no defectuosos debe ser estrictamente mayor que el número de procesos defectuosos. Sin embargo, usando la reconfiguración, se puede emplear un protocolo que sobreviva cualquier número de fallas totales siempre que no más de F fallen simultáneamente. Para los protocolos de Paxos, estas reconfiguraciones se pueden manejar como configuraciones separadas . [14]
Roles
Paxos describe las acciones de los procesadores por sus roles en el protocolo: cliente, aceptante, proponente, aprendiz y líder. En implementaciones típicas, un solo procesador puede desempeñar una o más funciones al mismo tiempo. Esto no afecta la corrección del protocolo; es habitual fusionar roles para mejorar la latencia y / o la cantidad de mensajes en el protocolo.
- Cliente
- El Cliente envía una solicitud al sistema distribuido y espera una respuesta . Por ejemplo, una solicitud de escritura en un archivo en un servidor de archivos distribuido.
- Aceptador (votantes)
- Los Aceptadores actúan como la "memoria" tolerante a fallos del protocolo. Los aceptadores se agrupan en grupos denominados quórumes. Cualquier mensaje enviado a un Aceptador debe enviarse a un Quórum de Aceptadores. Cualquier mensaje recibido de un Aceptador se ignora a menos que se reciba una copia de cada Aceptador en un Quórum.
- Proponente
- Un Proponente aboga por la solicitud de un cliente, intentando convencer a los Aceptantes de que estén de acuerdo con ella y actuando como coordinador para hacer avanzar el protocolo cuando ocurren conflictos.
- Aprendiz
- Los alumnos actúan como factor de replicación del protocolo. Una vez que los Aceptantes han acordado una solicitud del Cliente, el alumno puede tomar medidas (es decir, ejecutar la solicitud y enviar una respuesta al cliente). Para mejorar la disponibilidad del procesamiento, se pueden agregar alumnos adicionales.
- Líder
- Paxos requiere un Proponente distinguido (llamado líder) para progresar. Muchos procesos pueden creer que son líderes, pero el protocolo solo garantiza el progreso si finalmente se elige uno de ellos. Si dos procesos creen que son líderes, pueden estancar el protocolo al proponer continuamente actualizaciones contradictorias. Sin embargo, las propiedades de seguridad aún se conservan en ese caso.
Quórumes
Los quórums expresan las propiedades de seguridad (o consistencia) de Paxos al garantizar que al menos algún procesador superviviente conserve el conocimiento de los resultados.
Los quórumes se definen como subconjuntos del conjunto de aceptadores de modo que dos subconjuntos cualesquiera (es decir, dos quórumes cualesquiera) comparten al menos un miembro. Normalmente, un Quórum es la mayoría de los Aceptantes participantes. Por ejemplo, dado el conjunto de Aceptadores {A, B, C, D}, un Quórum mayoritario sería cualquiera de los tres Aceptantes: {A, B, C}, {A, C, D}, {A, B, D} , {B, C, D}. De manera más general, se pueden asignar pesos positivos arbitrarios a los aceptadores; en ese caso, un Quórum se puede definir como cualquier subconjunto de Aceptadores con la ponderación de resumen mayor que la mitad de la ponderación total de todos los Aceptadores.
Número de propuesta y valor acordado
Cada intento de definir un valor acordado v se realiza con propuestas que pueden ser aceptadas o no por los Aceptadores. Cada propuesta tiene un número único para un Proponente determinado. Entonces, por ejemplo, cada propuesta puede tener la forma (n, v) , donde n es el identificador único de la propuesta y v es el valor propuesto real. El valor correspondiente a una propuesta numerada se puede calcular como parte de la ejecución del protocolo Paxos, pero no es necesario.
Propiedades de seguridad y vitalidad
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 )
- Solo 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 vivacidad)
- Si se ha propuesto el valor C, eventualmente el alumno L aprenderá algún valor (si suficientes procesadores siguen sin fallar). [dieciséis]
Tenga en cuenta que no se garantiza que Paxos termine y, por lo tanto, no tiene la propiedad de vida. Esto está respaldado por el resultado de imposibilidad de Fischer Lynch Paterson (FLP) [6], que establece que un protocolo de coherencia solo puede tener dos de seguridad , vida útil y tolerancia a fallas . Como el objetivo de Paxos es garantizar la tolerancia a fallos y garantiza la seguridad, no puede garantizar también la vitalidad.
Despliegue típico
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 la operación normal, el líder recibe el comando de un cliente, le asigna un nuevo número de comando i, y luego comienza la i-ésima instancia del algoritmo de consenso enviando mensajes a un conjunto de procesos de aceptación. [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 cubre 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: Fase 1 (que se divide en partes una y b ) y la fase 2 (que se divide en partes a y b ). Vea a continuación la descripción de las fases. Recuerde que asumimos un modelo asíncrono, 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, 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 acuerde, sino solo un número que identifica de manera única este mensaje inicial por parte del proponente (para ser enviado a los aceptantes). El número n debe ser mayor que cualquier número que se usa en cualquiera de los anteriores Preparar mensajes de este solicitante. Luego, envía el mensaje Preparar que contiene n a un Quórum de Aceptadores . Tenga en cuenta que el mensaje Preparar solo contiene el número n (es decir, no tiene que contener, por ejemplo, el valor propuesto, a menudo denotado 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 Aceptadores.
Fase 1b: Promesa
- Cualquiera de los Aceptantes espera un mensaje de Preparación de cualquiera de los Proponentes . Si un Aceptador recibe un mensaje Preparar, el Aceptador debe mirar el número de identificación n del mensaje Preparar 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, para ignorar todas las propuestas futuras que tengan un número menor. que n . Si el Aceptador aceptó una propuesta en algún momento en el 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 a cualquier número de propuesta anterior recibido de cualquier Proponente por el Aceptador) el Aceptador puede ignorar la propuesta recibida. No tiene que responder 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 la mayoría de las promesas de un quórum de aceptantes, debe establecer un valor v para su propuesta. Si alguno de los Aceptantes 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 momento, entonces el Proponente puede elegir el valor que originalmente quería proponer, digamos x . [19]
- El Proponente envía un mensaje Aceptar , (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 Preparar enviado previamente al Aceptadores). Entonces, el mensaje de Aceptar es (n, v = z) o, en caso de que ninguno de los Aceptadores 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!".
Fase 2b: Aceptada
- Si un Aceptador recibe un mensaje de Aceptar, (n, v) , de un Proponente, debe aceptarlo si y solo si aún no ha prometido (en la Fase 1b del protocolo de Paxos) considerar solo las propuestas que tengan un identificador mayor que n .
- Si el Aceptador aún no ha prometido (en la Fase 1b) considerar solo las propuestas que tienen un identificador mayor que n , debe registrar el valor v (del mensaje Aceptar recién recibido ) como el valor aceptado (del Protocolo) y enviar un Mensaje aceptado para el proponente y todos los alumnos (que normalmente pueden ser los propios proponentes).
- De lo contrario, puede ignorar el mensaje o la solicitud de aceptación.
Tenga en cuenta que un Aceptador puede aceptar varias propuestas. Esto puede suceder cuando otro Proponente, sin darse cuenta del nuevo valor que se está decidiendo, inicia una nueva ronda con un número de identificación más alto n . En ese caso, el Aceptador puede prometer y luego aceptar el nuevo valor propuesto aunque haya aceptado otro antes. Estas propuestas pueden incluso tener valores diferentes en presencia de ciertos fallos [ ejemplo necesario ] . Sin embargo, el protocolo de Paxos garantizará que los Aceptadores finalmente se pongan de acuerdo sobre un valor único.
Cuando las rondas fallan
- Rondas fallan cuando varios proponentes envían en conflicto Preparar mensajes, o cuando el proponente no recibe un quórum de respuestas ( promesa o Aceptado ). En estos casos, se debe iniciar otra ronda con un número de propuesta más alto.
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 los Paxos básicos
Los siguientes diagramas representan varios casos / situaciones de la aplicación del protocolo Basic Paxos. Algunos casos muestran cómo el protocolo Basic Paxos se enfrenta 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 hace una propuesta (ya que ningún Aceptador ha aceptado un valor antes en esta ronda).
Paxos básicos sin fallos
En el diagrama a continuación, hay 1 cliente, 1 proponente, 3 aceptantes (es decir, el tamaño del quórum es 3) y 2 alumnos (representados por las 2 líneas verticales). Este diagrama representa el caso de una primera ronda, que tiene éxito (es decir, no falla ningún proceso en la red).
Cliente Proponente Aceptador Aprendiz | | | | | | | X --------> | | | | | | Pedido | X ---------> | -> | -> | | | Preparar (1) | | <--------- X - X - X | | Promesa (1, {Va, Vb, Vc}) | X ---------> | -> | -> | | | ¡Acepta! (1, V) | | <---------X--X--X------> | -> | Aceptado (1, V) | <--------------------------------- X - X Respuesta | | | | | | |
Aquí, V es el último de (Va, Vb, Vc).
Casos de error en Paxos básicos
Los casos de error más simples son la falla de un Aceptador (cuando un Quórum de Aceptadores permanece vivo) y la falla de un Aprendiz redundante. En estos casos, el protocolo no requiere "recuperación" (es decir, aún tiene éxito): no se requieren rondas o mensajes adicionales, como se muestra a continuación (en los siguientes dos diagramas / casos).
Paxos básicos 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 Básico de Paxos aún tiene éxito.
Cliente Proponente Aceptador Aprendiz | | | | | | | X --------> | | | | | | Pedido | X ---------> | -> | -> | | | Preparar (1) | | | | ! | | !! FALLAR !! | | <--------- X - X | | Promesa (1, {Va, Vb, null}) | X ---------> | -> | | | ¡Acepta! (1, V) | | <---------X--X---------> | -> | Aceptado (1, V) | <--------------------------------- X - X Respuesta | | | | | |
Paxos básicos cuando falla un alumno redundante
En el siguiente caso, uno de los alumnos (redundantes) falla, pero el protocolo Básico de Paxos sigue teniendo éxito.
Cliente Proponente Aceptador Aprendiz | | | | | | | X --------> | | | | | | Pedido | X ---------> | -> | -> | | | Preparar (1) | | <--------- X - X - X | | Promesa (1, {Va, Vb, Vc}) | X ---------> | -> | -> | | | ¡Acepta! (1, V) | | <---------X--X--X------> | -> | Aceptado (1, V) | | | | | | ! !! FALLAR !! | <--------------------------------- Respuesta X | | | | | |
Paxos básicos cuando falla un proponente
En este caso, un Proponente falla 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 hay 2 rondas en este caso (las rondas proceden verticalmente, de arriba a abajo).
Cliente Proponente Aceptador Aprendiz | | | | | | | X -----> | | | | | | Pedido | 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 | | | | | | |
Paxos básicos 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 fallar y recuperarse más tarde, 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 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 Aceptador Aprendiz | | | | | | | X -----> | | | | | | Pedido | X ------------> | -> | -> | | | Preparar (1) | | <------------ X - X - X | | Promesa (1, {nulo, nulo, nulo}) | ! | | | | | !! FALLA DEL LÍDER | | | | | | | !! 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, denegado | 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í ...
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 sola 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 lo tanto, es posible omitir la fase 1 para futuras instancias del protocolo con el mismo líder.
Para lograr esto, se incluye el número de ronda I junto con cada valor que se incrementa en cada ronda por el mismo Líder. Multi-Paxos reduce la demora de mensajes sin fallas (propuesta a aprendizaje) de 4 demoras a 2 demoras.
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 básico de Paxos.
Cliente Proponente Aceptador Aprendiz | | | | | | | --- Primera solicitud --- X --------> | | | | | | Pedido | 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).
Multi-Paxos cuando se puede omitir la fase 1
En este caso, las instancias posteriores del protocolo básico de Paxos (representado por I + 1 ) utilizan el mismo líder, por lo que la fase 1 (de estas instancias posteriores del protocolo básico de Paxos), que consiste en las subfases Preparar y Promesa, se omite. Tenga en cuenta que el líder debe ser estable, es decir, no debe bloquearse ni cambiar.
Cliente Proponente Aceptador Aprendiz | | | | | | | --- Siguiendo solicitudes --- X --------> | | | | | | Pedido | X ---------> | -> | -> | | | ¡Acepta! (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 Multi-Paxos consiste en colapsar el rol de los Proponentes, Aceptadores y Aprendices en "Servidores". Entonces, al final, solo hay "Clientes" y "Servidores".
El siguiente diagrama representa la primera "instancia" de un protocolo básico de Paxos, cuando los roles del Proponente, Aceptador y Aprendiz se contraen en un solo rol, llamado "Servidor".
Servidores cliente | | | | --- Primera solicitud --- X --------> | | | Pedido | X-> | -> | Preparar (N) | | <-X - X Promesa (N, I, {Va, Vb}) | X-> | -> | ¡Acepta! (N, I, Vn) | X <> X <> X Aceptado (N, I) | <-------- X | | Respuesta | | | |
Multi-Paxos cuando los roles se colapsan y el líder es estable
En las instancias posteriores del protocolo básico de Paxos, con el mismo líder que en las instancias anteriores del protocolo básico de Paxos, se puede omitir la fase 1.
Servidores cliente X --------> | | | Pedido | X-> | -> | ¡Acepta! (N, I + 1, W) | X <> X <> X Aceptado (N, I + 1) | <-------- X | | Respuesta | | | |
Optimizaciones
Se pueden realizar una serie de optimizaciones para reducir el número de mensajes intercambiados, para mejorar el rendimiento del protocolo, etc. A continuación se describen algunas de estas optimizaciones.
- "Podemos guardar mensajes a costa de un retraso adicional en el mensaje si tenemos un único alumno distinguido que informa a los demás alumnos cuando se entera de que se ha elegido un valor. Los aceptadores envían mensajes Aceptados solo al alumno distinguido. En la mayoría de las aplicaciones, las funciones de líder y alumno distinguido las desempeña el mismo procesador. [22]
- "Un líder puede enviar sus mensajes ¡ Prepara y acepta! Solo a un quórum de aceptantes. Siempre que todos los aceptadores en 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 aceptadores no les importa qué valor se elige. Simplemente responden a los mensajes ¡ Preparar y aceptar! Para asegurarse de que, a pesar de las fallas, solo se pueda elegir un valor. Sin embargo, si un aceptador aprende qué valor se ha elegido, puede almacenar el valor en 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 aceptadores en sus mensajes Accept ! . Un alumno aprenderá que se elige v si recibe mensajes aceptados 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 de 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. 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 de líder se transmita a los proponentes, lo que puede ser costoso. Por lo tanto, podría ser mejor dejar que el El proponente envía su propuesta a todos los coordinadores (en ese caso, solo los coordinadores mismos necesitan saber quién es el líder) [15].
- "En lugar de que cada aceptante 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 al mensaje. [15]
- "Por último, 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 amplía Basic Paxos para tolerar fallas F con procesadores principales F + 1 y procesadores auxiliares F reconfigurando dinámicamente después de cada falla.
Esta reducción en los requisitos del procesador 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 reconfigurar el sistema. Durante los períodos estables, los procesadores auxiliares no participan en el protocolo.
"Con sólo dos procesadores pyq, un procesador no puede distinguir la falla del otro procesador de la falla 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 tomar medidas solo en caso de que p o q falle, después de lo cual no hace nada mientras p o q continúan operando el sistema por sí mismos. 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 aceptores 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:
{Aceptadores}Proponente alumno auxiliar principal| | | | | | -- Fase 2 --X -----------> | -> | -> | | | ¡Acepta! (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 en el mensaje. Fast Paxos permite 2 retrasos en los mensajes, pero requiere que (1) el sistema esté compuesto por aceptadores 3f + 1 para tolerar hasta f fallas (en lugar del clásico 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 puede enviar un ¡Aceptar! mensaje a los Aceptantes directamente. Los Aceptadores responderían como en Paxos Básicos, enviando mensajes Aceptados al líder y a cada Alumno logrando dos retrasos en los mensajes de Cliente a Alumno.
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 la recuperación de colisión ellos mismos. Por lo tanto, la recuperación de colisión descoordinada puede ocurrir en tres retrasos de mensaje (y solo dos retrasos de mensaje si todos los alumnos son también Aceptadores).
Flujo de mensajes: Paxos rápidos, no conflictivos
Aprendiz aceptor líder del cliente | | | | | | | | | X ---------> | -> | -> | -> | | | Cualquiera (N, I, recuperación) | | | | | | | | X -------------------> | -> | -> | -> | | | ¡Acepta! (N, I, W) | | <---------X--X--X--X------> | -> | Aceptado (N, I, W) | <------------------------------------ X - X Respuesta (W) | | | | | | | |
Flujo de mensajes: Paxos rápidos, propuestas conflictivas
Propuestas conflictivas con recuperación coordinada. Nota: el protocolo no especifica cómo manejar la solicitud de cliente descartada.
Aprendiz aceptor líder del cliente | | | | | | | | | | | | | | | | | | | | | | | | | | | !! Propuestas concurrentes en conflicto | | | | | | | | | !! recibido en orden diferente | | | | | | | | | !! por los aceptadores | X --------------? | -? | -? | -? | | | ¡Acepta! (N, I, V) X -----------------? | -? | -? | -? | | | ¡Acepta! (N, I, W) | | | | | | | | | | | | | | | | | | !! Los aceptadores no están de acuerdo con el valor | | | <-------X--X-> | -> | -----> | -> | Aceptado (N, I, V) | | | <------- | <- | <-X--X-----> | -> | Aceptado (N, I, W) | | | | | | | | | | | | | | | | | | !! Detecta colisiones y recupera | | X -------> | -> | -> | -> | | | ¡Acepta! (N + 1, I, W) | | | <-------X--X--X--X-----> | -> | Aceptado (N + 1, I, W) | <--------------------------------- X - X Respuesta (W) | | | | | | | | |
Propuestas conflictivas con recuperación descoordinada.
Aprendiz aceptor líder del cliente | | | | | | | | | | | X -------> | -> | -> | -> | | | Cualquiera (N, I, recuperación) | | | | | | | | | | | | | | | | | | !! Propuestas concurrentes en conflicto | | | | | | | | | !! recibido en orden diferente | | | | | | | | | !! por los aceptadores | X --------------? | -? | -? | -? | | | ¡Acepta! (N, I, V) X -----------------? | -? | -? | -? | | | ¡Acepta! (N, I, W) | | | | | | | | | | | | | | | | | | !! Los aceptadores no están de acuerdo con el valor | | | <-------X--X-> | -> | -----> | -> | Aceptado (N, I, V) | | | <------- | <- | <-X--X-----> | -> | Aceptado (N, I, W) | | | | | | | | | | | | | | | | | | !! Detecta colisiones y recupera | | | <-------X--X--X--X-----> | -> | Aceptado (N + 1, I, W) | <--------------------------------- X - X Respuesta (W) | | | | | | | | |
Flujo de mensajes: Paxos rápidos con recuperación descoordinada, roles colapsados
(roles de aceptor / aprendiz fusionados)
Servidores cliente | | | | | | | | X-> | -> | -> | Cualquiera (N, I, recuperación) | | | | | | | | | | | | !! Propuestas concurrentes en conflicto | | | | | | !! recibido en orden diferente | | | | | | !! por los servidores | X --------? | -? | -? | -? | ¡Acepta! (N, I, V) X -----------? | -? | -? | -? | ¡Acepta! (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) | | | | | | | | | | | | !! Detecta colisiones y recupera | | 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 estado replicada y el protocolo de consenso que lo implementa. [16] El principal descubrimiento involucra optimizaciones de Paxos cuando las propuestas en conflicto pueden aplicarse en cualquier orden. es decir, cuando las operaciones propuestas son operaciones conmutativas para la máquina de estados. En tales casos, las operaciones en conflicto pueden ser aceptadas, evitando las demoras necesarias para resolver los conflictos y proponiendo 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 sea desplazada con ellas se vuelva estable.
Ejemplo
Para ilustrar Paxos generalizados, 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.
Leer un) | Escribe un) | Leer (B) | Escribir (B) | |
---|---|---|---|---|
Leer un) | ||||
Escribe un) | ||||
Leer (B) | ||||
Escribir (B) |
Tenga en cuenta que en 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 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 desplazamiento se produce solo cuando las operaciones se proponen al mismo tiempo.
Flujo de mensajes: Paxos generalizados (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 una discusión completa.
Aprendiz aceptor líder del cliente | | | | | | | | !! Nuevo líder comienza ronda | | X -----> | -> | -> | | | Preparar (N) | | | <----- X- X- X | | Promesa (N, nulo) | | X -----> | -> | -> | | | Phase2Start (N, nulo) | | | | | | | | | | | | | | | | !! Propuestas de desplazamientos concurrentes | X -------? | -----? | -? | -? | | | Proponer (Leer A) X -----------? | -----? | -? | -? | | | Proponer (LeerB) | | X ------ X --------------> | -> | Aceptado (N,) ,> | | | <--------X--X--------> | -> | Aceptado (N,) ,> | | | | | | | | | | | | | | | | !! Sin conflicto, ambos aceptados | | | | | | | | Estable =,> | | | | | | | | | | | | | | | | !! Propuestas concurrentes en conflicto X -----------? | -----? | -? | -? | | | Proponer ( ) ,> | X --------? | -----? | -? | -? | | | Proponer (LeerB) | | | | | | | | | | X ------ X --------------> | -> | Aceptado (N,. ,> | | | <--------X--X--------> | -> | Aceptado (N,) . | | | | | | | | | | | | | | | | !! Conflicto detectado, el líder elige | | | | | | | | orden conmutativo: | | | | | | | | V =) ,>,> | | | | | | | | | | X -----> | -> | -> | | | Phase2Start (N + 1, V) | | | <----- X- X- X --------> | -> | Aceptado (N + 1, V) | | | | | | | | Estable = . ,> | | | | | | | |,> | | | | | | | | | | | | | | | | !! Propuestas más conflictivas X -----------? | -----? | -? | -? | | | Proponer (WriteA) | X --------? | -----? | -? | -? | | | Proponer (Leer A) | | | | | | | | | | X ------ X --------------> | -> | Aceptado (N + 1, . | | | <-------- X- X --------> | -> | Aceptado (N + 1,) . | | | | | | | | | | | | | | | | !! El líder elige el orden: | | | | | | | | W =) ,> | | | | | | | | | | X -----> | -> | -> | | | Phase2Start (N + 2, W) | | | <----- X- X- X --------> | -> | Aceptado (N + 2, W) | | | | | | | | Estable = . ,> | | | | | | | |. ,> | | | | | | | |,> | | | | | | | |
Actuación
El flujo de mensajes anterior nos muestra que los Paxos generalizados pueden aprovechar la semántica de operación para evitar colisiones cuando falla el orden 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 provienen del hecho de que se pueden aceptar múltiples comandos durante una ronda. Esto hace que el protocolo sea más caro que Paxos cuando los conflictos son frecuentes. Es de esperar que dos posibles refinamientos de Paxos generalizados sean posibles para mejorar el tiempo de recuperación. [24]
- Primero, si el coordinador es parte de cada quórum de aceptadores (la ronda N se dice centrada ), luego para recuperarse en la ronda N + 1 de una colisión en la ronda N, el coordinador salta la fase 1 y propone en la fase 2 la secuencia que aceptó en último lugar. 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, propone espontáneamente en la ronda N + 1 una secuencia que sufra ambos (i) la secuencia aceptada en la ronda N por el coordinador y (ii) el mayor prefijo no conflictivo que aceptó en la ronda N. Por ejemplo, si el coordinador y el aceptor aceptaron respectivamente en la ronda N
y ,>Con esta variación, el costo de recuperación es un retraso de un solo mensaje que obviamente es óptimo. Observe aquí que el uso de un quórum único en una ronda no perjudica 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], el aceptador aceptará espontáneamente < WriteB, ReadB, ReadA> en la ronda N + 1. ,>
Paxos bizantinos
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 , por la solución popularizada por Lamport. [26]
Byzantine Paxos [27] introducido por Castro y Liskov agrega un mensaje extra (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 ---------> | -> | -> | | | ¡Acepta! (N, I, V) | | X <> X <> X | | Verificar (N, I, V) - DIFUSIÓ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 aceptor del cliente | | | | | | X -----> | -> | -> | | | ¡Acepta! (N, I, V) | X <> X <> X ------> | -> | Aceptado (N, I, V) - DIFUSIÓ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 mismos Aceptadores también lo sabrán (ya que intercambiaron los mensajes entre ellos en la ronda de transmisión), y los Aceptadores correctos retransmitirán el valor acordado:
Flujo de mensajes: Fast Byzantine Multi-Paxos, falla
Aprendiz aceptor del cliente | | | ! | | !! Un aceptador está defectuoso X -----> | -> | ->! | | ¡Acepta! (N, I, V) | X <> X <> X ------> | -> | Aceptado (N, I, {V, W}) - DIFUSIÓN | | | ! | | !! Los alumnos reciben 2 comandos diferentes | | | ! | | !! Corrija el error de aviso de los aceptadores y elija | X <> X <> X ------> | -> | Aceptado (N, I, V) - DIFUSIÓN | <------------------- X - X Respuesta (V) | | | ! | |
Adaptando Paxos para redes RDMA
Con la aparición 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 de la capa de red, liberando la CPU del 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 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ónicos y eliminar otras fuentes de retraso en la ruta crítica del líder. De esta forma, Derecho puede 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 mapeando las operaciones de envío de mensajes a las operaciones RDMA nativas, hacerlo deja retrasos de ida y vuelta en la ruta crítica. En redes RDMA de alta velocidad, incluso los pequeños retrasos pueden ser lo suficientemente grandes como para evitar la utilización de todo el ancho de banda potencial.
Uso de producción de Paxos
- Google usa el algoritmo de Paxos en su servicio de bloqueo distribuido Chubby para mantener las réplicas consistentes en caso de falla. 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 de OpenReplica utiliza Paxos para mantener las réplicas de un sistema de acceso abierto que permite a los usuarios crear objetos tolerantes a fallas. Proporciona un alto rendimiento a través de rondas simultáneas y flexibilidad a través de cambios dinámicos de membresía.
- IBM supuestamente usa el algoritmo Paxos en su producto IBM SAN Volume Controller para implementar una máquina virtual tolerante a fallas 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. ( Trabajo de investigación original de MIT e IBM )
- Microsoft usa Paxos en el servicio de administración de clústeres de piloto automático de Bing y en clústeres de conmutación por error de Windows Server.
- WANdisco ha implementado Paxos dentro de su tecnología de replicación activa-activa DConE. [29]
- XtreemFS utiliza un algoritmo de negociación de arrendamiento basado en Paxos para una replicación consistente y tolerante a fallas de datos y metadatos de archivos. [30]
- Heroku usa Doozerd, que implementa Paxos para su almacenamiento de datos distribuido consistente.
- Ceph usa Paxos como parte de los procesos de monitoreo para acordar qué OSD están activos y en el clúster.
- La base de datos SQL distribuida de Clustrix utiliza Paxos para la resolución de transacciones distribuidas .
- La base de datos de gráficos Neo4j HA implementa Paxos, reemplazando a Apache ZooKeeper de v1.9
- La base de datos Apache Cassandra NoSQL utiliza Paxos para la función de transacciones ligeras únicamente
- Amazon Elastic Container Services usa Paxos para mantener una vista coherente del estado del clúster
Ver también
- Algoritmo de consenso Chandra-Toueg
- Máquina estatal
- Balsa
Referencias
- ^ Pease, Marshall; Shostak, Robert; Lamport, Leslie (abril de 1980). "Llegar a un acuerdo en presencia de fallas" . Revista de la Asociación de Maquinaria Informática . 27 (2) . Consultado el 2 de febrero de 2007 .
- ^ Lamport, Leslie (julio de 1978). "Tiempo, relojes y ordenación de eventos en un sistema distribuido" . Comunicaciones de la ACM . 21 (7): 558–565. doi : 10.1145 / 359545.359563 . Consultado el 2 de febrero de 2007 .
- ^ 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 .
- ^ Historia del papel de Leslie Lamport
- ^ Lamport, Leslie (mayo de 1998). "El Parlamento a tiempo parcial" . Transacciones ACM en sistemas informáticos . 16 (2): 133-169. doi : 10.1145 / 279227.279229 . Consultado el 2 de febrero de 2007 .
- ^ a b 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 .
- ^ Dwork, Cynthia; Lynch, Nancy; Stockmeyer, Larry (abril de 1988). "Consenso en presencia de sincronía parcial" (PDF) . Revista de la ACM . 35 (2): 288–323. CiteSeerX 10.1.1.13.3423 . doi : 10.1145 / 42282.42283 .
- ^ Oki, Brian; Liskov, Barbara (1988). "Replicación con sello de visualización: un nuevo método de copia principal para admitir sistemas distribuidos de alta disponibilidad" . PODC '88: Actas del séptimo simposio anual de ACM sobre principios de computación distribuida . págs. 8-17. doi : 10.1145 / 62546.62549 .
- ^ Birman, Kenneth; Joseph, Thomas (febrero de 1987). "Comunicación confiable en presencia de fallas". Transacciones ACM en sistemas informáticos : 47–76.
- ^ Lamport, Leslie; Malkhi, Dahlia; Zhou, Lidong (marzo de 2010). "Reconfiguración de una máquina de estado". Noticias SIGACT . 41 (1): 63–73. CiteSeerX 10.1.1.212.2168 . doi : 10.1145 / 1753171.1753191 .
- ^ Keidar, Idit; Shraer, Alexander (2006). "Oportunidad, detectores de fallas y desempeño consensuado". PODC '06: Actas del 25º Simposio Anual de ACM sobre Principios de Computación Distribuida . doi : 10.1145 / 1146381.1146408 .
- ^ a b Jha, Sagar; Behrens, Jonathan; Gkountouvas, Theo; Milano, Matthew; Song, Weijia; Tremel, Edward; van Renesse, Robbert; Zink, Sydney; Birman, Ken (abril de 2019). "Derecho: Replicación de máquinas de estado rápido para servicios en la nube". Transacciones ACM en sistemas informáticos . 36 (2). doi : 10.1145 / 3302258 .
- ^ Lamport, Leslie (2004). "Límites inferiores para el consenso asincrónico" .
- ^ Van Renesse, Robbert; Altinbuken, Deniz (17 de febrero de 2015). "Paxos hecho moderadamente complejo" . Encuestas de computación ACM . 47 (3): 42: 1–42: 36. doi : 10.1145 / 2673577 . ISSN 0360-0300 .
- ^ a b c d e Lamport, Leslie (2005). "Paxos rápidos" .
- ^ a b c d Lamport, Leslie (2005). "Consenso generalizado y Paxos" . Cite journal requiere
|journal=
( ayuda ) - ^ Chandra, Tushar; Griesemer, Robert; Redstone, Joshua (2007). Paxos Made Live: una perspectiva de ingeniería . PODC '07: 26º Simposio ACM sobre Principios de Computación Distribuida . págs. 398–407. doi : 10.1145 / 1281100.1281103 . ISBN 9781595936165.
- ^ Quesada Torres, Luis (2018). El algoritmo de Paxos . Google TechTalks.
- ^ Lamport, Leslie (2001). Paxos Made Simple ACM SIGACT News (Columna de Computación Distribuida) 32 , 4 (Número entero 121, diciembre de 2001) 51-58.
- ^ "Elección de líder, ¿por qué debería importarme?" . Blog elástico . Consultado el 27 de febrero de 2021 .
- ^ I.Gupta, R. van Renesse y KP Birman, 2000, Un protocolo de elección de líder probablemente correcto para grupos grandes, Informe técnico , Universidad de Cornell
- ^ a b c d e Lamport, Leslie; Massa, Mike (2004). "Paxos baratos" . Actas de la Conferencia internacional sobre redes y sistemas fiables (DSN 2004) .
- ^ Turner, Bryan (2007). "La familia de protocolos de consenso de Paxos" .
- ^ Pierre, Sutra; Marc, Shapiro (2011). "Consenso generalizado genuino rápido" (PDF) . SRDS'11: 30º Simposio IEEE sobre sistemas distribuidos confiables .
- ^ Lamport, Leslie; Malkhi, Dahlia; Zhou, Lidong (2009). Paxos verticales y replicación de respaldo primario . Actas del 28º Simposio de ACM sobre Principios de Computación Distribuida . PODC '09. Nueva York, NY, EE.UU .: ACM. págs. 312–313. CiteSeerX 10.1.1.150.1791 . doi : 10.1145 / 1582716.1582783 . ISBN 9781605583969.
- ^ 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 . Consultado el 2 de febrero de 2007 .
- ^ Castro, Miguel; Liskov, Barbara (febrero de 1999). "Tolerancia práctica a fallos bizantinos" (PDF) . Actas del tercer simposio sobre diseño e implementación de sistemas operativos : 173–186 . Consultado el 5 de marzo de 2018 .
- ^ Martin, Jean-Philippe; Alvisi, Lorenzo (julio de 2006). "Consenso bizantino rápido" (PDF) . Transacciones IEEE sobre computación segura y confiable . 3 (3): 202–215. doi : 10.1109 / TDSC.2006.35 . Consultado el 5 de marzo de 2018 .
- ^ Aahlad y col. (2011). “El motor de coordinación distribuida (DConE)” Archivado el 15 de abril de 2016 en Wayback Machine . Libro blanco de WANdisco.
- ^ Kolbeck, Björn; Högqvist, Mikael; Stender, Jan; Hupfeld, Felix (2011). "Flease - Coordinación de arrendamiento sin un servidor de bloqueo" . 25º Simposio internacional de procesamiento paralelo y distribuido de IEEE (IPDPS 2011).
enlaces externos
- Página de inicio de Leslie Lamport
- Paxos simplificado
- Paxos hecho moderadamente complejo
- Revisando el algoritmo de Paxos
- Compromiso de Paxos
- Documento técnico de Google: Servicio de candado distribuido de Chubby
- Informe técnico de Google: Bigtable, un sistema de almacenamiento distribuido para datos estructurados
- Encuesta de algoritmos de Paxos (2007)
- Servicio de replicación abierta OpenReplica
- FTFile: biblioteca de archivos tolerante a fallas
- Biblioteca Isis2 (la primitiva SafeSend es una implementación gratuita y de código abierto de Paxos)
- Mencius - Paxos giratorios circulares para sistemas geo-distribuidos
- WANdisco: soluciones de replicación activa-activa para Hadoop, Subversion y GIT
- libpaxos, una colección de implementaciones de código abierto del algoritmo Paxos
- libpaxos-cpp, una implementación en C ++ del algoritmo de consenso distribuido de paxos
- JBP - Paxos bizantinos de Java
- erlpaxos, Paxos de Erlang
- paxos - Implementación sencilla de paxos en Python y Java
- Manhattan Paxos (mpaxos), Paxos en C, que admite múltiples grupos de paxos y transacciones eficientes entre ellos.
- Agrupación en clústeres con Neo4j
- HT-Paxos
- PaxosStore, implementación de paxos en WeChat
- LWT en Cassandra
- Google TechTalks: el algoritmo de Paxos