19 Flashcards
(2 cards)
grales bizantinos
Hay 3 o más grales. que deben decidir si atacan o se retiran. Hay un comandante que envía la orden de ataque/retirada. Los generales pueden ser traicioneros y avisarle a los otros generales lo opuesto de lo que avisó el comandante. Por otro lado, el comandante puede ser traicionero y enviarle órdenes distintas a cada general. El comportamiento traicionero simula las fallas que puede tener un proceso. Los requerimientos en este problema son el agreement (el valor de la variable decided es el mismo en todos los procesos activos), integrity (si el comandante no es traicionero, entonces todos los procesos deben setear su decision variable al valor enviado por el comandante) y termination (eventualmente todos los procesos activos setean su decision variable).
Paxos
Hay 4 tipos de actores: client (realiza request), proposer (recibe requests de clientes y comienza el protocolo; el leader debe ser elegido para evitar starvation), acceptor (recibe propuestas o promesas de los proposers, mantienen el estado del protocolo en almacenamiento estable; el quórum existe cuando la mayoría de acceptors se encuentran vivos), learner (cuando el protocolo llega a un acuerdo, learner ejecuta el request y envía rta. al cliente).
El objetivo de Paxos es lograr que todos los acceptors consensúen un valor v asociado a una propuesta realizada por un proposer.
Las fases del algoritmo son las siguientes:
- fase 0: client realiza un request
- fase 1 - prepare: El proposer crea una propuesta #N donde N es mayor a cualquier propuesta realizada previamente por el Proposer y la envía a los Acceptors esperando obtener Quórum.
- fase 1 - promise: si ID recibido del Proposer es mayor al último recibido, Acceptors prometen rechazar cualquier Requests con ID < N y le envían dicha Promesa al Proposer. Finalmente, los Acceptors no contestan si llega una propuesta no se cumpla que N > N’.
- fase 2 - propose: si el Proposer recibe Promesas de la mayoría, entonces rechaza todos los requests con ID < N y envía Propose con el N recibido por los acceptors y un valor v.
- fase 2 - request: un acceptor, si la promesa todavía es mantenida, anuncia el nuevo valor v enviando accepts a todos los Learners y al Proposer que envió el request inicial. No envía accepts si un ID superior a N fue recibido. El Learner por su parte responde al cliente y se toman acciones respecto del valor acordado
