En Paxos, ¿puede un Aceptador aceptar un valor diferente después de haber aceptado uno?

Question

En el algoritmo Multi-Paxos, considere este flujo de mensajes desde el punto de vista de un aceptador:

recibir:Preparar(N)

responder:Promesa(N, nula)

recibir:¡Acepta!(N,V1)

responder:Aceptado(N, V1)

recibir:¡Aceptar!(N+1, V2)

responder:?

¿Cuál debería ser la reacción del aceptor en este caso, según el protocolo?¿Debería responder con Aceptado (N+1, V2), o debería ignorar el segundo Aceptar?

Creo que este caso puede ocurrir en Multi-Paxos cuando un segundo proponente se conecta y cree que es (y siempre fue) líder, por lo tanto envía su Aceptar sin prepararse.O si su preparación simplemente no llegó al aceptador.Si es posible que este caso no suceda, ¿puede explicar por qué?

Answer 1

No estoy de acuerdo con las otras dos respuestas.

1. Multi-Paxos no dice que el líder es el único proponente; esto haría que el sistema tuviera un solo punto de falla . Incluso durante las particiones de red, es posible que el sistema no pueda progresar. Multi-Paxos es una optimización que permite a un solo nodo (el Líder ) omitir algunas fases de preparación. Otros nodos, pensando que el líder está muerto, pueden intentar continuar la instancia en su nombre, pero aún deben usar el protocolo Basic-Paxos completo.

2. Marcar el mensaje de aceptación viola el algoritmo de Paxos. Un aceptador debe aceptar todos los valores a menos que haya prometido no aceptarlos. (Ignorarlo está permitido pero no recomendado; es solo porque los mensajes descartados están permitidos).

3. También existe una elegante solución para esto. El problema está en el número de ronda del líder (N + 1 en la pregunta).

Estas son algunas suposiciones:

• Tiene un esquema tal que los identificadores redondos están separados en todos los nodos (requerido por Paxos de todos modos).
• Tiene una forma de determinar qué nodo es el líder por instancia de Paxos (requerido por Multi-Paxos). El líder puede cambiar de una instancia de Paxos a la siguiente.
  Aparte: El parlamento a tiempo parcial sugiere que esto lo hace el Líder ganando una instancia previa de Paxos (Sección 3.1) y señala que puede seguir siendo Líder mientras viva o sea la más rica (Sección 3.3.1). Tengo un valor ELECT_NEW_LEADER: explícito que se propone a través de Paxos.
• El líder solo salta la fase de preparación en la ronda inicial por instancia; y usa Paxos Básico completo en rondas posteriores.

Con estos supuestos, la solución es muy simple. El líder simplemente elige una ID de ronda realmente baja para su fase de aceptación inicial. Esta identificación (que la llamaré INITIAL_ROUND_ID) puede ser cualquier cosa siempre que sea más baja que la identificación redonda de todos los nodos. Dependiendo de su esquema de elección de identificación, funcionará -1, 0 o Integer.MIN_VALUE.

Funciona porque otro nodo (lo llamaré Stewart) tiene que pasar por el protocolo completo de Paxos para proponer cualquier cosa y su ID de ronda siempre es mayor que INITIAL_ROUND_ID . Hay dos casos a considerar: si los mensajes de aceptación del líder llegaron a cualquiera de los nodos que llegó al mensaje de preparación de Stewart.

Cuando la fase de aceptación del líder no alcanza ningún nodo, el Stewart no recuperará ningún valor en ninguna promesa y podrá continuar como en los Paxos básicos normales.

Y, cuando la fase de aceptación del líder haya alcanzado un nodo, Stewart recuperará un valor en una promesa, que utiliza para continuar el algoritmo, al igual que en Basic-Paxos.

En cualquier caso, debido a que el ID de ronda de Stewart es mayor que INITIAL_ROUND_ID, cualquier mensaje de aceptación lento que un nodo reciba del líder siempre resultará en un Nack.

No existe una lógica especial ni en el Aceptador ni en el Stewart. Y una mínima lógica especial en el líder (es decir, elija un INITIAL_ROUND_ID realmente bajo).

---

Fíjate, si cambiamos la pregunta del OP por un carácter, entonces la auto respuesta del OP es correcta: Nack.

• recibir: preparar (N)
• respuesta: Promesa (N, nulo)
• recibir: aceptar (N, V1)
• respuesta: aceptado (N, V1)
• recibir: aceptar ( N-1 , V2)
• respuesta: Nack (N, V1)

Pero tal como está, su respuesta rompe el algoritmo de Paxos; debería ser Aceptar.

• recibir: preparar (N)
• respuesta: Promesa (N, nulo)
• recibir: aceptar (N, V1)
• respuesta: aceptado (N, V1)
• recibir: aceptar ( N + 1 , V2)
• respuesta: ¡Aceptar! (N + 1, V2)

Answer 2

La corrección de Multi-Paxos está condicionada al requisito de que el líder (es decir., proponente) no cambia entre instancias sucesivas de Paxos.De El parlamento a tiempo parcial Sección 3.1 (El Protocolo del Parlamento de Decretos Múltiples):

Lógicamente, el protocolo parlamentario [a.k.a.Multi-Paxos] utilizó un instancia separada del protocolo completo del Sínodo [también conocido comoPaxos] para cada número de decreto.Sin embargo, un solo presidente [a.k.a.proponente/líder] fue seleccionado para todas estas instancias, y realizó la primera Dos pasos del protocolo una sola vez.
_{[El énfasis añadido es mío.]}

Por lo tanto, Multi-Paxos supone que el caso que usted describe (cuando un segundo proponente se conecta y cree que es (y siempre fue) líder) nunca sucederá.Si tal caso puede ocurrir, entonces no se debe utilizar Multi-Paxos.Con respecto a la segunda posibilidad—cuando la decisión del segundo proponente Prepare no llegó al aceptador: el hecho de que el segundo proponente ya envió un Accept! significa que previamente envió un Prepare eso fue Promised por un quórum de aceptantes.Dado que los aceptantes ya prometieron al primer proponente en la ronda N, entonces el del segundo proponente Prepare debe haber sido enviado antes de la ronda N.Por lo tanto, la final Accept!(N+1,V2) debe tener un contador menos que N.

Editar: También cabe señalar que esta versión del protocolo no es sólida para fracaso bizantino:

[El protocolo del Parlamento Paxon] no tolera fallas arbitrarias y maliciosas, ni garantiza una respuesta en un tiempo limitado.
_{—El parlamento a tiempo parcial, Sección 4.1}

Answer 3

Tal vez una respuesta más simple es observar que este es el caso cuando se aceptó la comando prepare (n + 1) por mayoría que no incluyó al aceptor en cuestión.

para elaborar: una vez que un líder sabe que alguna vez se prometió una mayoría ha prometido (n + 1), luego envía aceptable (n + 1, x) a todos los aceptadores ,e incluso si algunos otros la mayoría de los aceptadores responden con aceptados (N + 1), se ha alcanzado el consenso.

Esto no es ese escenario inusual.

Answer 4

(Respondiendo a mi propia pregunta)

Mi entendimiento actual es que no debería aceptar el valor en N + 1 (es decir, no responder en absoluto o enviar un NACK), lo que obliga al líder a posiblemente comenzar otra ronda con Preparar (si la mayoría no ha alcanzadoconsenso todavía).Después de recibir Prepare (N + 2), responderé con Promise (N + 2, V1) y continuaré como de costumbre.