Algoritmo de Paxos

El algoritmo de Paxos es un algoritmo que nos permite llegar a consensos en sistemas distribuidos. Entendemos consenso como el proceso de ponerse de acuerdo sobre uno de los resultados entre un grupo de participantes. Este problema se hace difícil cuando los participantes o su medio de comunicación puede experimentar fallos.

El protocolo Paxos primero fue publicado en 1989 e incluye una gama de soluciones de compensación entre el número de procesos, el número de mensajes con retraso antes de aprender el valor acordado, el nivel de actividad de los participantes, el número de mensajes enviados, y los tipos de fallos. Aunque un protocolo de consenso con tolerancia a fallos determinista no puede garantizar el progreso en una red asíncrona, Paxos garantiza la seguridad (libre de inconsistencia), y las condiciones que podrían hacer que no progrese son difíciles de ocurrir.

Funciona en el modelo de paso de mensajes con asincronía y con menos n/2 fallos (pero no con fallos bizantinos). El algoritmo de Paxos garantiza que se llegará a un acuerdo y garantiza la finalización si hay un tiempo suficientemente largo sin que ningún proceso reinicie el protocolo.

Contexto: Algoritmos de consenso

Cuando se habla de consenso en sistemas distribuidos nos referimos a un conjunto de procesos que han de ponerse de acuerdo en un valor una vez uno o varios procesos han propuesto cuál debería ser este valor.^[1]

Supongamos que tenemos una colección de procesos pi(i= 1, 2...N ) los cuales se comunican por paso de mensajes. El objetivo es llegar a consenso aunque haya fallos, por lo que se asume que la comunicación es fiable, pero que los procesos pueden fallar. Para llegar a un consenso, cada proceso pi empieza en el estado de no decisión y propone un valor vi. Los procesos se comunican unos con otros intercambiando valores. A continuación, cada proceso fija un valor en una variable de decisión di. Cuando lo hace, entra en el estado decidido, en el cual ya no se podrá cambiar di. Cada una de las ejecuciones de un algoritmo de consenso debería satisfacer las siguientes condiciones:

Finalización: cada proceso correcto debe acabar asignando un valor a su variable de decisión.

Acuerdo: el valor finalmente decidido por todos los procesos correctos es el mismo.

Integridad: si todos los procesos correctos han propuesto el mismo valor, entonces cualquier proceso correcto en el estado de decisión ha elegido este valor.

Roles

Durante su funcionamiento, Paxos describe las acciones de los procesos mediante una serie de roles establecidos en el protocolo: Cliente, Aceptador, Proponente, Aprendiz y Líder. En las implementaciones típicas, un mismo proceso puede tener diferentes roles al mismo tiempo. Estos roles son:

Cliente: El cliente emite una petición al sistema distribuido, y espera una respuesta.

Proponente: Un proponente media por una petición del cliente, tratando de convencer a los aceptadores para que se pongan de acuerdo sobre el mismo ratificando un valor propuesto, y actúan como un coordinador para seguir adelante con el protocolo cuando se producen conflictos.

Aceptadores: Los aceptadores actúan como la "memoria" con tolerancia a fallos del protocolo. Los aceptadores se recogen en grupos llamados Quórums. Cualquier mensaje enviado a un aceptador debe ser enviado 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.

Aprendiz: Los aprendiz actúan como el factor de replicación para el protocolo. Una vez que la petición del cliente ha sido acordada por los Aceptadores, el aprendiz puede tomar acción (es decir, ejecutar la petición y enviar una respuesta al cliente).

Líder: Paxos requiere un proponente completo (llamado el líder) para garantizar que el sistema va pasando por las diferentes fases y concluye finalmente. Muchos procesos pueden creer que son líder, pero el protocolo sólo garantiza el progreso, si uno de ellos es finalmente elegido. Si dos procesos creen que son los líder, pueden paralizar el protocolo de forma continua proponiendo cambios conflictivos.

Quórums

Los Quórums expresan las propiedades de seguridad de Paxos, garantizando que al menos algún proceso conserve el conocimiento de los resultados. Los Quórums se definen como subconjuntos del conjunto de aceptadores tales que dos Quórums cualesquiera comparten al menos un miembro. Típicamente, un Quórum es cualquier mayoría de aceptadores participantes. Por ejemplo, dado el conjunto de aceptadores {A, B, C, D}, un Quórum sería cualquiera de los tres grupos de aceptadores: {A, B, C}, {A, C, D}, {A, B, D} , {B, C, D}.

Seguridad

La familia Paxos define tres propiedades de seguridad que siempre han de llevarse a cabo para poder garantizar la seguridad, independientemente del patrón de fallos:

No trivialidad: Sólo valores propuestos se pueden aprender.^[2]

Consistencia: El valor aprendido tiene que ser único (es decir, dos aprendices distintos no pueden aprender valores diferentes).

Vitalidad(C, A): Si un aprendiz A propone un valor C, entonces el aprendiz A aprenderá obligatoriamente algún valor (siempre y cuando existan suficientes procesos funcionando correctamente).

Funcionamiento

Paxos Básico

Esta implementación es la más básica del protocolo de Paxos. Cada instancia del protocolo básico Paxos decide un único valor de salida. El protocolo consta de varias fases. Un proponente no debe iniciar el protocolo si no se puede comunicar con al menos un Quórum de aceptadores.^[3]

El algoritmo de consenso se estructura en dos fases:

Fase 1

Preparar: Un proponente (el líder) crea una propuesta identificada con un número N. Este número debe ser mayor que cualquier propuesta anterior que utiliza este proponente. Después, envía un mensaje (petición) prepara(N) a una Quórum de aceptantes.

Prometer: Si un aceptador recibe una petición de prepara con un número N mayor que cualquier otra petición de prepara que haya respondido hasta ese momento, entonces contesta a la petición con una promesa de no aceptar ninguna otra propuesta con número inferior a N y con el número de propuesta mayor (si hay alguna) que ha aceptado.

Fase 2

Aceptar petición

Si el proponente recibe una respuesta a su petición de prepara(N), es decir una promesa de un Quórum de aceptadores. Entonces:

Si cualquier aceptador había aceptado previamente una propuesta, entonces se envía una petición de aceptar(N,V) a cada uno de los aceptadores, donde V es el valor del número de propuesta mayor entre todas las respuestas recibidas.
En cambio, si ninguno de los aceptadores había aceptado una propuesta hasta ese momento, en este caso se enviará una petición de aceptar(N,V) a cada uno de los aceptadores, donde V es el nuevo valor que hay que aceptar que es elegido por el proponente.

Aceptado: Si un aceptador recibe un mensaje de petición aceptar la propuesta N, debe aceptarlo si y solamente si aún no lo ha prometido tener en cuenta sólo las propuestas tengan un identificador mayor que N, es decir, si aún no ha respondido a ninguna petición de prepara(N) (enviar un mensaje de promesa). En este caso, se debe registrar el valor correspondiente V y enviar un mensaje de aceptado al Proponente y cada aprendiz. Si no, se puede ignorar la petición Aceptar.

Las fases fallan cuando varios proponentes envían mensajes conflictivos de preparar(N), o cuando el proponente no recibe la respuesta del Quórum (promesa o aceptado). En estos casos, una nueva iteracción del protocolo debe iniciarse con un número de propuesta superior.

Hay que tener en cuenta que cuando un aceptador acepta una solicitud, está reconociendo el liderazgo del proponente. Por lo tanto, Paxos se puede utilizar para seleccionar un líder en un grupo de nodos.

Esto es una representación gráfica del protocolo básico Paxos. Por lo que hay que tener en cuenta que los valores devueltos en el mensaje Promise son nulas la primera vez que se hace una propuesta, ya que ningún aceptador ha aceptado un valor antes en esta iteración.

Flujo de mensajes: Paxos Básico

(Primera iteración completada)

 Cliente   Proponente   Aceptadores    Aprendices
   |           |          |  |  |        |  |
   X---------->|          |  |  |        |  |    Petición
   |           X--------->|->|->|        |  |    Prepara(1)
   |           |<---------X--X--X        |  |    Promesa(1,{Va,Vb,Vc})
   |           X--------->|->|->|        |  |    Aceptar!(1,Vn)
   |           |<---------X--X--X------->|->|    Aceptado(1,Vn)
   |<------------------------------------X--X    Respuesta
   |           |          |  |  |        |  |

Vn = last(Va, Vb, Vc)

Casos de error en paxos básico

En estos casos de error, el protocolo no requiere recuperación. No son necesarios iteraciones o mensajes adicionales, tal y como se muestra a continuación:

Flujo de mensajes: Paxos básico, fallo del aceptador

(Tamaño del Quórum = 2 Aceptadores)

 Cliente   Proponente   Aceptadores    Aprendices
   |           |          |  |  |         |  |
   X---------->|          |  |  |         |  |    Petición
   |           X--------->|->|->|         |  |    Prepara(1)
   |           |          |  |  !         |  |    !! FALLO !!
   |           |<---------X--X            |  |    Promesa(1,{null,null, null})
   |           X--------->|->|            |  |    Aceptar(1,V)
   |           |<---------X--X----------->|->|    Aceptado(1,V)
   |<-------------------------------------X--X    Respuesta
   |           |          |  |            |  |

Flujo de mensajes: Paxos básico, fallo del aprendiz redundante

 Cliente   Proponente   Aceptadores    Aprendices
   |           |          |  |  |         |  |
   X---------->|          |  |  |         |  |    Petición
   |           X--------->|->|->|         |  |    Prepara(1)
   |           |<---------X--X--X         |  |    Promesa(1,{null,null,null})
   |           X--------->|->|->|         |  |    Aceptar(1,V)
   |           |<---------X--X--X-------->|->|    Aceptado(1,V)
   |           |          |  |  |         |  !    !! FALLO !!
   |<-------------------------------------X       Respuesta
   |           |          |  |  |         |

Flujo de mensajes: Paxos básico, fallo del proponente

(Re-elección no mostrada, una instancia, dos rondas)

Cliente   Proponente   Aceptadores    Aprendices
   |         |           |  |  |         |  |
   X-------->|           |  |  |         |  |  Petición
   |         X---------->|->|->|         |  |  Prepara(1)
   |         |<----------X--X--X         |  |  Promesa(1,{null, null, null})
   |         |           |  |  |         |  |
   |         |           |  |  |         |  |  !! FALLO DEL LÏDER DURANTE LA DIFUSIÓN !!
   |         X---------->|  |  |         |  |  Aceptar(1,Va)
   |         !           |  |  |         |  |
   |         |           |  |  |         |  |  !! NUEVO LÍDER !!
   |         X---------->|->|->|         |  |  Prepara(2)
   |         |<----------X--X--X         |  |  Promesa(2,{null, null, null})
   |         X---------->|->|->|         |  |  Aceptar(2,V)
   |         |<----------X--X--X-------->|->|  Aceptado(2,V)
   |<------------------------------------X--X  Respuesta
   |         |           |  |  |         |  |

Multi-Paxos

La implementación más común de Paxos requiere un flujo continuo de los valores acordados que actúan como comandos para una máquina de estado distribuido. Si cada comando es el resultado de una única instancia del protocolo básico de Paxos, obtendríamos una gran cantidad de gasto.

Si el proceso que actúa como líder es relativamente estable, la fase 1 sería innecesaria. Por lo tanto, es posible omitir la fase 1 para futuras instancias del protocolo con el mismo líder.

Para lograr esto, el número de instancia I es incluido junto con cada valor. Multi-Paxos reduce el retraso de los mensajes libres de fallos (del proponente al aprendiz) a la mitad (de 4 a 2 delays).

Flujo de mensajes: Multi-Paxos, inicio

(Primera estancia con un nuevo líder)

 Cliente   Proponente   Aceptadores    Aprendices
   |           |          |  |  |         |  |   --- Primera petición ---
   X---------->|          |  |  |         |  |    Petición
   |           X--------->|->|->|         |  |    Prepara(N)
   |           |<---------X--X--X         |  |    Promesa(N,I,{Va,Vb,Vc})
   |           X--------->|->|->|         |  |    Aceptar(N,I,Vm)
   |           |<---------X--X--X-------->|->|    Aceptado(N,I,Vm)
   |<-------------------------------------X--X    Respuesta
   |           |          |  |  |         |  |

Vm = last of (Va, Vb, Vc)

Flujo de mensaje: estado estacionario Multi-Paxos colapsado

(Instancias posteriores con el mismo líder)

 Cliente   Proponente   Aceptadores    Aprendices
   |           |          |  |  |         |  |    --- Primera petición ---
   X---------->|          |  |  |         |  |    Petición
   |           X--------->|->|->|         |  |    Aceptar(N,I+1,W)
   |           |<---------X--X--X-------->|->|    Aceptado (N,I+1,W)
   |<-------------------------------------X--X    Resppuesta
   |           |          |  |  |         |  |

Véase también

Referencias

↑ Navarro, Leandro (2009). «Sincronización,tolerancia a fallos y replicación». Parámetro desconocido |curly= ignorado (ayuda)
↑ Lamport, Leslie (2005). «Fast Paxos». Parámetro desconocido |curly= ignorado (ayuda)
↑ Lamport, Leslie (2001). Paxos Made Simple ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) 51-58.

[sinc-1] Navarro, Leandro (2009). «Sincronización,tolerancia a fallos y replicación». Parámetro desconocido |curly= ignorado (ayuda)

[fast-2] Lamport, Leslie (2005). «Fast Paxos». Parámetro desconocido |curly= ignorado (ayuda)

[paxos-simple-3] Lamport, Leslie (2001). Paxos Made Simple ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) 51-58.

[1]

[2]

[3]