El algoritmo de Paxos es un algoritmo para llegar a consensos en sistemas distribuidos con cierto grado de tolerancia a fallos. 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 por Leslie Lamport aunque pasó desapercibido hasta 1998 cuando lo publicó en una revista especializada. Desde entonces se han publicado varias mejoras y adaptaciones.
El algoritmo 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.
Básicamente Paxos es un algoritmo para decidir un solo valor en un cluster de nodos. Decidir múltiples valores es una extensión a este algoritmo. Hay una serie de roles que pueden tener los nodos (procesos). En las implementaciones típicas, un mismo proceso puede tener diferentes roles al mismo tiempo. Estos roles son:
Un nodo puede tener varios roles. Por ejemplo un cliente de base de datos puede ser un proponente y también un aprendiz.
Normalmente se considera un cuarto rol llamado Cliente y que es el rol de un nodo (que puede ser externo) que es el que hace la petición de cambio de estado al sistema distribuido (a un proponente) y espera una respuesta
Para que un valor se considere aceptado, tiene que haber cierto quorum de aceptadores. 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 válido sería cualquiera de los tres grupos de aceptadores: {A, B, C}, {A, C, D}, {A, B, D} , {B, C, D}.
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:
Paxos solo funciona si la mayoría de los aceptadores están activos. Si fallan más de (n/2)-1 aceptadores entonces ningún proponente puede obtener suficientes respuestas a sus mensajes 'preparar' y ningún valor será aceptado. Otro punto débil está relacionado con el momento donde los proponentes envían los mensajes. En caso de que tengamos un solo proponente siempre se aceptará el valor mayor. Cuando hay varios proponentes éstos pueden interferir entre ellos. Por ejemplo ya se podría haber escogido una elección mejor que otra que ya ha sido aceptada. A esto se le llama duelo de proponentes. En la práctica este problema normalmente se resuelve eligiendo un coordinador que implemente algún algoritmo de detección de fallos o simplemente usando un backoff exponencial (como usa ethernet )
Supongamos que la decisión consiste en tomar el número mayor. Por tanto una propuesta en una ronda i es considerada como válida si es mayor que el resto de propuestas en esa ronda. Todas aquellas propuestas para esa ronda con números más pequeños son consideradas no válidas.
El sistema funciona con dos fases: Fase de preparación y fase de aceptación. Un proponente no debe iniciar el protocolo si no se puede comunicar con al menos un quorum de aceptadores.
Representaciones gráficas del protocolo.
Vn = mayor(Va, Vb, Vc)
(Reelección no mostrada, una instancia, dos rondas)
Normalmente lo que se requiere es 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).
(Primera estancia con un nuevo líder)
Vm = last of (Va, Vb, Vc)
(Instancias posteriores con el mismo líder
Escribe un comentario o lo que quieras sobre Algoritmo de Paxos (directo, no tienes que registrarte)
Comentarios
(de más nuevos a más antiguos)