Algoritmo de Paxos 1

Algoritmo de PaxosEl algoritmo de Paxos es un algoritmo que nos permite llegar a consensos en sistemas distribuidos. Entendemosconsenso como el proceso de ponerse de acuerdo sobre uno de los resultados entre un grupo de participantes. Esteproblema se hace difcil cuando los participantes o su medio de comunicacin puede experimentar fallos.El protocolo Paxos primero fue publicado en 1989 e incluye una gama de soluciones de compensacin entre elnmero de procesos, el nmero de mensajes con retraso antes de aprender el valor acordado, el nivel de actividad delos participantes, el nmero de mensajes enviados, y los tipos de fallos. Aunque un protocolo de consenso contolerancia a fallos determinista no puede garantizar el progreso en una red asncrona, Paxos garantiza la seguridad(libre de inconsistencia), y las condiciones que podran hacer que no progrese son difciles de ocurrir.Funciona en el modelo de paso de mensajes con asincrona y con menos n/2 fallos (pero no con fallos bizantinos). Elalgoritmo de Paxos garantiza que se llegar a un acuerdo y garantiza la finalizacin si hay un tiempo suficientementelargo sin que ningn proceso reinicie el protocolo.

Contexto: Algoritmos de consensoCuando se habla de consenso en sistemas distribuidos nos referimos a un conjunto de procesos que han de ponersede acuerdo en un valor una vez uno o varios procesos han propuesto cul debera ser este valor.Supongamos que tenemos una coleccin 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 comunicacin es fiable, pero que losprocesos pueden fallar. Para llegar a un consenso, cada proceso pi empieza en el estado de no decisin y propone unvalor vi. Los procesos se comunican unos con otros intercambiando valores. A continuacin, cada proceso fija unvalor en una variable de decisin di. Cuando lo hace, entra en el estado decidido, en el cual ya no se podr cambiardi. Cada una de las ejecuciones de un algoritmo de consenso debera satisfacer las siguientes condiciones: Finalizacin: cada proceso correcto debe acabar asignando un valor a su variable de decisin. 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 decisin ha elegido este valor.

RolesDurante su funcionamiento, Paxos describe las acciones de los procesos mediante una serie de roles establecidos enel protocolo: Cliente, Aceptador, Proponente, Aprendiz y Lder. En las implementaciones tpicas, un mismo procesopuede tener diferentes roles al mismo tiempo. Estos roles son:Cliente

El cliente emite una peticin al sistema distribuido, y espera una respuesta.Proponente

Un proponente media por una peticin del cliente, tratando de convencer a los aceptadores para que se pongande acuerdo sobre el mismo ratificando un valor propuesto, y actan como un coordinador para seguir adelantecon el protocolo cuando se producen conflictos.

AceptadoresLos aceptadores actan como la "memoria" con tolerancia a fallos del protocolo. Los aceptadores se recogenen grupos llamados Qurums. Cualquier mensaje enviado a un aceptador debe ser enviado a un Qurum deaceptadores. Cualquier mensaje recibido de un aceptador se ignora a menos que se reciba una copia de cadaaceptador en un Qurum.

http://es.wikipedia.org/w/index.php?title=Computaci%C3%B3n_distribuida

Algoritmo de Paxos 2

AprendizLos aprendiz actan como el factor de replicacin para el protocolo. Una vez que la peticin del cliente ha sidoacordada por los Aceptadores, el aprendiz puede tomar accin (es decir, ejecutar la peticin y enviar unarespuesta al cliente).

LderPaxos requiere un proponente completo (llamado el lder) para garantizar que el sistema va pasando por lasdiferentes fases y concluye finalmente. Muchos procesos pueden creer que son lder, pero el protocolo slogarantiza el progreso, si uno de ellos es finalmente elegido. Si dos procesos creen que son los lder, puedenparalizar el protocolo de forma continua proponiendo cambios conflictivos.

QurumsLos Qurums expresan las propiedades de seguridad de Paxos, garantizando que al menos algn proceso conserve elconocimiento de los resultados. Los Qurums se definen como subconjuntos del conjunto de aceptadores tales quedos Qurums cualesquiera comparten al menos un miembro. Tpicamente, un Qurum es cualquier mayora deaceptadores participantes. Por ejemplo, dado el conjunto de aceptadores {A, B, C, D}, un Qurum sera cualquierade los tres grupos de aceptadores: {A, B, C}, {A, C, D}, {A, B, D} , {B, C, D}.

SeguridadLa familia Paxos define tres propiedades de seguridad que siempre han de llevarse a cabo para poder garantizar laseguridad, independientemente del patrn de fallos: No trivialidad: Slo valores propuestos se pueden aprender. 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 algn

valor (siempre y cuando existan suficientes procesos funcionando correctamente).

Funcionamiento

Paxos BsicoEsta implementacin es la ms bsica del protocolo de Paxos. Cada instancia del protocolo bsico Paxos decide unnico valor de salida. El protocolo consta de varias fases. Un proponente no debe iniciar el protocolo si no se puedecomunicar con al menos un Qurum de aceptadores.El algoritmo de consenso se estructura en dos fases:

Fase 1

PrepararUn proponente (el lder) crea una propuesta identificada con un nmero N. Este nmero debe ser mayorque cualquier propuesta anterior que utiliza este proponente. Despus, enva un mensaje (peticin)prepara(N) a una Qurum de aceptantes.

PrometerSi un aceptador recibe una peticin de prepara con un nmero N mayor que cualquier otra peticin deprepara que haya respondido hasta ese momento, entonces contesta a la peticin con una promesa de noaceptar ninguna otra propuesta con nmero inferior a N y con el nmero de propuesta mayor (si hayalguna) que ha aceptado.

Algoritmo de Paxos 3

Fase 2

Aceptar peticinSi el proponente recibe una respuesta a su peticin de prepara(N), es decir una promesa de un Qurumde aceptadores. Entonces:

Si cualquier aceptador haba aceptado previamente una propuesta, entonces se enva una peticin deaceptar(N,V) a cada uno de los aceptadores, donde V es el valor del nmero de propuesta mayor entre todaslas respuestas recibidas.

En cambio, si ninguno de los aceptadores haba aceptado una propuesta hasta ese momento, en este caso seenviar una peticin de aceptar(N,V) a cada uno de los aceptadores, donde V es el nuevo valor que hay queaceptar que es elegido por el proponente.

AceptadoSi un aceptador recibe un mensaje de peticin aceptar la propuesta N, debe aceptarlo si y solamente sian no lo ha prometido tener en cuenta slo las propuestas tengan un identificador mayor que N, esdecir, si an no ha respondido a ninguna peticin de prepara(N) (enviar un mensaje de promesa). En estecaso, se debe registrar el valor correspondiente V y enviar un mensaje de aceptado al Proponente y cadaaprendiz. Si no, se puede ignorar la peticin Aceptar.Las fases fallan cuando varios proponentes envan mensajes conflictivos de preparar(N), o cuando elproponente no recibe la respuesta del Qurum (promesa o aceptado). En estos casos, una nuevaiteraccin del protocolo debe iniciarse con un nmero de propuesta superior.Hay que tener en cuenta que cuando un aceptador acepta una solicitud, est reconociendo el liderazgodel proponente. Por lo tanto, Paxos se puede utilizar para seleccionar un lder en un grupo de nodos.Esto es una representacin grfica del protocolo bsico Paxos. Por lo que hay que tener en cuenta quelos valores devueltos en el mensaje Promise son nulas la primera vez que se hace una propuesta, ya queningn aceptador ha aceptado un valor antes en esta iteracin.

Flujo de mensajes: Paxos Bsico

(Primera iteracin completada)

Cliente Proponente Aceptadores Aprendices

| | | | | | |

X---------->| | | | | | Peticin

| X--------->|->|->| | | Prepara(1)

| ||->|->| | | Aceptar!(1,Vn)

| ||->| Aceptado(1,Vn)

|

Algoritmo de Paxos 4

Casos de error en paxos bsico

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

Flujo de mensajes: Paxos bsico, fallo del aceptador

(Tamao del Qurum = 2 Aceptadores)

Cliente Proponente Aceptadores Aprendices

| | | | | | |

X---------->| | | | | | Peticin

| X--------->|->|->| | | Prepara(1)

| | | | ! | | !! FALLO !!

| ||->| | | Aceptar(1,V)

| ||->| Aceptado(1,V)

|| | | | | | Peticin

| X--------->|->|->| | | Prepara(1)

| ||->|->| | | Aceptar(1,V)

| ||->| Aceptado(1,V)

| | | | | | ! !! FALLO !!

|| | | | | | Peticin

| X---------->|->|->| | | Prepara(1)

| || | | | | Aceptar(1,Va)

| ! | | | | |

| | | | | | | !! NUEVO LDER !!

| X---------->|->|->| | | Prepara(2)

| ||->|->| | | Aceptar(2,V)

| ||->| Aceptado(2,V)

|

Algoritmo de Paxos 5

| | | | | | |

Multi-PaxosLa implementacin ms comn de Paxos requiere un flujo continuo de los valores acordados que actan comocomandos para una mquina de estado distribuido. Si cada comando es el resultado de una nica instancia delprotocolo bsico de Paxos, obtendramos una gran cantidad de gasto.Si el proceso que acta como lder es relativamente estable, la fase 1 sera innecesaria. Por lo tanto, es posible omitirla fase 1 para futuras instancias del protocolo con el mismo lder.Para lograr esto, el nmero de instancia I es incluido junto con cada valor. Multi-Paxos reduce el retraso de losmensajes 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 lder)

Cliente Proponente Aceptadores Aprendices

| | | | | | | --- Primera peticin ---

X---------->| | | | | | Peticin

| X--------->|->|->| | | Prepara(N)

| ||->|->| | | Aceptar(N,I,Vm)

| ||->| Aceptado(N,I,Vm)

|| | | | | | Peticin

| X--------->|->|->| | | Aceptar(N,I+1,W)

| ||->| Aceptado (N,I+1,W)

|

Fuentes y contribuyentes del artculo 6

Fuentes y contribuyentes del artculoAlgoritmo de Paxos Fuente: http://es.wikipedia.org/w/index.php?oldid=72179858 Contribuyentes: Fixertool, Ikrespo, Miketanis, 8 ediciones annimas

LicenciaCreative Commons Attribution-Share Alike 3.0//creativecommons.org/licenses/by-sa/3.0/

Algoritmo de PaxosContexto: Algoritmos de consensoRolesQurums

SeguridadFuncionamientoPaxos BsicoFase 1Fase 2Flujo de mensajes: Paxos Bsico Casos de error en paxos bsico

Multi-PaxosFlujo de mensajes: Multi-Paxos, inicio Flujo de mensaje: estado estacionario Multi-Paxos colapsado

Referencias

Licencia