A Paxos, un Accettatore può accettare un valore diverso dopo averne già accettato uno?

Question

Nell'algoritmo Multi-Paxos, considera questo flusso di messaggi dal punto di vista di un accettore:

ricevere:Preparare(N)

rispondere:Promessa(N, null)

ricevere:Accetta!(N, V1)

rispondere:Accettato(N, V1)

ricevere:Accetta!(N+1, V2)

rispondere:?

Quale dovrebbe essere la reazione dell'accettore in questo caso, secondo il protocollo?Dovrebbe rispondere con Accepted(N+1, V2) o dovrebbe ignorare il secondo Accept!?

Credo che questo caso possa verificarsi in Multi-Paxos quando un secondo proponente si collega online e crede di essere (ed è sempre stato) leader, quindi invia la sua accettazione senza preparazione.O se il suo Preparato semplicemente non raggiungesse l'accettore.Se questo caso potrebbe non verificarsi, puoi spiegare il motivo?

Answer 1

Non sono d'accordo con entrambe le altre risposte.

1. Multi-Paxos lo fa non dire che il Leader è l'unico proponente; ciò farebbe sì che il sistema abbia un singolo punto di errore.Anche durante le partizioni di rete il sistema potrebbe non essere in grado di avanzare.Multi-Paxos è un'ottimizzazione che consente a un singolo nodo (the Capo) per saltare alcune fasi di preparazione.Altri nodi, pensando che il leader sia morto, possono tentare di continuare l'istanza per suo conto, ma devono comunque utilizzare il protocollo Basic-Paxos completo.

2. Nastrare il messaggio di accettazione viola l'algoritmo di Paxos. Un accettante dovrebbe accettare tutti i valori a meno che non abbia promesso di farlo non accettarla. (Ignorare è consentito ma non consigliato;è solo perché i messaggi persi sono consentiti.)

3. C'è anche una soluzione elegante a questo.Il problema riguarda il numero del round del Leader (N+1 nella domanda).

Ecco alcune ipotesi:

• Hai uno schema tale che gli ID rotondi siano disgiunti su tutti i nodi (richiesto comunque da Paxos).
• Hai un modo per determinare quale nodo è il Leader per istanza Paxos (richiesto da Multi-Paxos).Il Leader è in grado di passare da un'istanza di Paxos alla successiva.
  A parte: Il Parlamento a tempo parziale suggerisce che ciò venga fatto dal Leader che vince una precedente istanza di Paxos (Sezione 3.1) e sottolinea che può rimanere Leader fintanto che è vivo o il più ricco (Sezione 3.3.1).Ho un valore ELECT_NEW_LEADER:<node> esplicito proposto tramite Paxos.
• Il Leader salta solo la fase di Preparazione del iniziale round per istanza;e utilizza i Paxos base completi nei round successivi.

Con questi presupposti la soluzione è molto semplice.Il Leader sceglie semplicemente un ID di round molto basso per la sua fase iniziale di Accettazione.Questo ID (che chiamerò INITIAL_ROUND_ID) può essere qualsiasi cosa purché sia ​​inferiore agli ID rotondi di tutti i nodi.A seconda dello schema di scelta dell'ID, funzionerà -1, 0 o Integer.MIN_VALUE.

Funziona perché un altro nodo (lo chiamerò Stewart) deve passare attraverso l'intero protocollo Paxos per proporre qualsiasi cosa e il suo ID del round è sempre maggiore di INITIAL_ROUND_ID.Ci sono due casi da considerare:se i messaggi di accettazione del leader hanno raggiunto o meno uno dei nodi del messaggio di preparazione di Stewart.

Quando il Leader accetta la fase non ha raggiunge qualsiasi nodo, lo Stewart non riceverà alcun valore in nessuna Promessa e potrà procedere proprio come nel normale Basic-Paxos.

E, quando il Leader accetta la fase ha raggiunto un nodo, lo Stewart recupererà un valore in una promessa, che utilizzerà per continuare l'algoritmo, proprio come in Basic-Paxos.

In entrambi i casi, poiché l'ID del round di Stewart è maggiore di INITIAL_ROUND_ID, qualsiasi messaggio di accettazione lento che un nodo riceve dal leader risulterà sempre in un Nack.

Non esiste una logica speciale né sull'Acceptor né sullo Stewart.E logica speciale minima sul Leader (Viz.scegli un INITIAL_ROUND_ID veramente basso).

---

Nota, se modifichiamo la domanda dell'OP di un carattere, la risposta automatica dell'OP è corretta:Nack.

• ricevere:Preparare(N)
• rispondere:Promessa(N, null)
• ricevere:Accetta!(N, V1)
• rispondere:Accettato(N, V1)
• ricevere:Accettare!(N-1, V2)
• rispondere: Nack(N, V1)

Ma così com’è, la sua risposta rompe l’algoritmo di Paxos;dovrebbe essere Accetta!

• ricevere:Preparare(N)
• rispondere:Promessa(N, null)
• ricevere:Accetta!(N, V1)
• rispondere:Accettato(N, V1)
• ricevere:Accettare!(N+1, V2)
• rispondere: Accetta!(N+1, V2)

Answer 2

La correttezza dei multi-paxos è condizionata sul requisito che il leader ( I.e. , proponente) non cambia tra successive istanze di PAXOS. Da il Part-time parliament Sezione 3.1 (il protocollo del Multi-Decreto Parliament):

.

Logicamente, il protocollo parlamentare [A.K.A. Multi-paxos] usato a istanza separata del protocollo di sinodo completo [A.k.a. Paxos] per ogni decreto numero. Tuttavia, Un unico presidente [A.k.a. Proposito / Leader] è stato selezionato per tutte queste istanze , e ha eseguito il primo Due passi del protocollo solo una volta.
_{[Aggiunta enfasi è mia.]}

Pertanto, Multi-Paxos fa il presupposto che il caso che descrivi, quando un secondo proposito arriva online e crede che sia (e sempre) il leader-non avverrà mai. Se può accadere tale custodia, allora non si dovrebbe usare multi-paxos. Per quanto riguarda la seconda possibilità, quando il Prepare del secondo proposito non ha raggiunto l'accettore, il fatto che il secondo proposito ha già inviato un Accept! significa che in precedenza ha inviato un Prepare Promised da un quorum di accettatori. Poiché gli accettatori hanno già promesso al primo proponente su N rotondo, quindi il PrepareGcode del secondo proposito deve essere stato inviato prima del N tondo. Pertanto, il Accept!(N+1,V2) finale deve avere un contatore inferiore a N.

Modifica: Va notato inoltre che questa versione del protocollo non è robusta da Guasto bizantino :

.

[il protocollo del Parlamento del Paxon] non tollera guasti arbitrari e dannosi, né garantisce una risposta del tempo delimitata.
_{- il Part-Time Parlamento , sezione 4.1}

Answer 3

Forse una risposta più semplice è osservare che questo è il caso in cui il comando Prepara (N + 1) è stato accettato da una maggioranza che non includeva l'accettatore in questione.

Per approfondire: una volta che un leader sa che una certa maggioranza ha promesso (N + 1), invia quindi Accetta (N + 1, x) a tutti gli accettatori,e anche se qualche altra maggioranza degli accettatori risponde con Accettato (N + 1), il consenso è stato raggiunto.

Questo non è uno scenario insolito.

Answer 4

(Rispondendo alla mia domanda.)

La mia comprensione attuale è che non dovrei accettare il valore in N + 1 (cioè non rispondere affatto o inviare un NACK), costringendo così il leader ad eventualmente iniziare un altro round con Prepara (se la maggioranza non ha raggiuntoconsenso ancora).Dopo aver ricevuto Prepare (N + 2), risponderò con Promise (N + 2, V1) e continuerò come al solito.