Dans Paxos, un accepteur peut-il accepter une valeur différente après avoir déjà accepté un?

Question

Dans l'algorithme multi-Paxos, considérez ce flux de message du point de vue d'un accepteur:

Recevoir: Préparer (n)

Réponse: Promise (n, null)

recevoir: accepter! (n, v1)

Réponse: acceptée (n, v1)

recevoir: accepter! (n + 1, v2)

Réponse: ?

Quelle devrait être la réaction de l'accepteur dans ce cas, selon le protocole? Doit-il répondre avec accepté (n + 1, v2), ou devrait-il ignorer le deuxième acceptation !?

Je crois que ce cas peut se produire dans Multi-Paxos lorsqu'un deuxième proposant est mis en ligne et pense qu'il est (et toujours) leader, donc il envoie son acceptation sans se préparer. Ou si sa préparation n'a tout simplement pas atteint l'accepteur. Si cette affaire peut ne pas se produire, pouvez-vous expliquer pourquoi?

Answer 1

Je ne suis pas d'accord avec les deux autres réponses.

1. Multi-Paxos fait ne pas Dites que le leader est le seul proposant; Cela entraînerait un seul point d'échec du système. Même pendant les partitions de réseau, le système peut ne pas être en mesure de progresser. Multi-Paxos est une optimisation permettant un seul nœud (le Chef) pour sauter quelques phases de préparation. D'autres nœuds, pensant que le leader est mort, peut tenter de poursuivre l'instance en son nom, mais doit toujours utiliser le protocole complet de base-Paxos.

2. Nacking the Accept Message viole l'algorithme Paxos. Un accepteur doit accepter toutes les valeurs à moins qu'elle n'ait promis de ne pas accepte-le. (L'ignorance est autorisée mais pas recommandée; c'est simplement parce que les messages supprimés sont autorisés.)

3. Il existe également une solution élégante à cela. Le problème concerne le numéro rond du leader (n + 1 dans la question).

Voici quelques hypothèses:

• Vous avez un schéma tel que les ID ronds sont disjoints sur tous les nœuds (requis par Paxos de toute façon).
• Vous avez un moyen de déterminer quel nœud est le leader par instance Paxos (requis par Multi-Paxos). Le leader est capable de passer d'une instance Paxos à l'autre.
  De côté: Le parlement à temps partiel suggère que cela est fait par le leader remportant une instance de Paxos antérieure (section 3.1) et souligne qu'elle peut rester leader tant qu'elle est en vie ou la plus riche (section 3.3.1). J'ai un elect_new_leader explicite:u003Cnode> Valeur proposée via Paxos.
• Le leader ne fait que sauter la phase de préparation sur le initial rond par instance; et utilise des paxos de base complets sur les tours ultérieurs.

Avec ces hypothèses, la solution est très simple. Le leader choisit simplement un ID rond très faible pour sa phase d'acceptation initiale. Cet ID (que je l'appellerai initial_round_id) peut être n'importe quoi tant qu'il est inférieur à tous les ID ronds des nœuds. Selon votre schéma d'identité, -1, 0 ou Integer.min_value fonctionnera.

Cela fonctionne parce qu'un autre nœud (je vais l'appeler le Stewart) doit passer par le protocole complet de Paxos pour proposer quoi que ce soit et Son ID rond est toujours supérieur à Initial_round_id. Il y a deux cas à considérer: si les messages acceptés par le leader ont atteint l'un des nœuds que le message de préparation de Stewart a fait.

Quand la phase d'acceptation du leader n'a pas Atteint tous les nœuds, le Stewart ne récupérera aucune valeur dans aucune promesse et peut procéder comme dans les bassos de base réguliers.

Et, quand la phase d'acceptation du leader a Atteint un nœud, le Stewart récupérera une valeur dans une promesse, qu'il utilise pour continuer l'algorithme, tout comme dans Basic-Paxos.

Dans les deux cas, comme l'ID ronde de Stewart est supérieur à Initial_round_id, tout message à accepter lent qu'un nœud reçoit du leader entraînera toujours un NACK.

Il n'y a aucune logique spéciale sur l'accepteur ou le Stewart. Et une logique spéciale minimale sur le leader (à savoir. Choisissez un Initial_round_id vraiment faible).

---

Remarquez, si nous modifions la question du PO par un personnage, la réponse auto-auto-OP est correcte: nack.

• Recevoir: Préparer (n)
• Réponse: Promise (n, null)
• recevoir: accepter! (n, v1)
• Réponse: acceptée (n, v1)
• Recevoir: accepter! (N-1, V2)
• Réponse: Nack (n, v1)

Mais en l'état, sa réponse brise l'algorithme Paxos; Il devrait être accepté!

• Recevoir: Préparer (n)
• Réponse: Promise (n, null)
• recevoir: accepter! (n, v1)
• Réponse: acceptée (n, v1)
• Recevoir: accepter! (N + 1, V2)
• Réponse: Accepter! (N + 1, v2)

Answer 2

L'exactitude du multi-Paxos est conditionnée à l'exigence que le leader (c'est à dire, proposant) ne change pas entre les instances de Paxos successives. De Le parlement à temps partiel Section 3.1 (Le protocole du Parlement multi-excrétion)::

Logiquement, le protocole parlementaire [AKA Multi-Paxos] a utilisé une instance distincte du protocole Synod complet [aka Paxos] pour chaque numéro de décret. Cependant, Un seul président [alias proposant / leader] a été sélectionné pour toutes ces instances, et il a effectué les deux premières étapes du protocole une seule fois.
_{L'accent est mis à moi.}

Par conséquent, Multi-Paxos fait l'hypothèse que le cas que vous décrivez - lorsqu'un deuxième proposant est mis en ligne et pense qu'il est (et toujours) leader - ne se produira jamais. Si un tel cas peut se produire, il ne faut pas utiliser Multi-Paxos. En ce qui concerne la deuxième possibilité - lorsque le deuxième proposant Prepare n'a pas atteint l'accepteur - le fait que le deuxième proposant a déjà envoyé un Accept! signifie qu'il avait précédemment envoyé un Prepare c'était Promised par un quorum d'accepteurs. Puisque les accepteurs ont déjà promis au premier proposant en tour N, alors le deuxième proposant Prepare doit avoir été envoyé avant le tour N. Par conséquent, la finale Accept!(N+1,V2) Doit avoir un comptoir moins que N.

Éditer: Il convient également de noter que cette version du protocole n'est pas robuste à Échec byzantin:

Le protocole du Parlement de Paxon] ne tolère pas les échecs arbitraires et malveillants, et il ne garantit pas la réponse à temps délimité.
_{—Le parlement à temps partiel, Section 4.1}

Answer 3

Peut-être qu'une réponse plus simple consiste à observer que c'est le cas lorsque la commande de préparation (n + 1) a été acceptée par une majorité qui n'incluait pas l'accepteur en question.

Pour élaborer: une fois qu'un leader sait que quelques La majorité a promis (n + 1), il envoie ensuite l'acceptation (n + 1, x) à tout accepteurs, et même si certains autre La majorité des accepteurs répondent avec accepté (n + 1) alors le consensus a été atteint.

Ce n'est pas un scénario inhabituel.

Answer 4

(Répondre à ma propre question.)

Ma compréhension actuelle est que je ne devrais pas accepter la valeur en n + 1 (c'est-à-dire ne pas répondre du tout ou envoyer un nack), obligeant ainsi le leader à commencer un autre tour avec Préparer (si la majorité n'a pas encore atteint le consensus) . Après avoir reçu préparé (n + 2), je répondrai avec promesse (n + 2, v1) et continuez comme d'habitude.