في Paxos ، يمكن متقبل تقبل قيمة مختلفة بعد أن قبلت بالفعل ؟

Question

في متعدد باكسوس الخوارزمية ، النظر في هذه الرسالة تدفق من وجهة نظر متقبل:

تلقي:إعداد(N)

الرد:وعد(ن, null)

تلقي:تقبل!(N, V1)

الرد:قبلت(ن, V1)

تلقي:تقبل!(N+1, V2)

الرد:?

ما ينبغي أن متقبل رد الفعل في هذه الحالة ، وفقا للبروتوكول ؟ يجب عليه الرد مع قبلت(ن+1, V2) أو أنه تجاهل الثانية تقبل!?

وأعتقد أن هذا قد يحدث في متعدد باكسوس عند الثانية الاقتراح يأتي على الانترنت ويعتقد أنه هو (دائما) زعيم ولذلك كان يرسل له قبول دون إعداد.أو إذا كان له إعداد ببساطة لم تصل إلى متقبل.إن هذه الحالة قد لا يحدث, هل يمكنك أن تشرح لماذا ؟

Answer 1

أنا اختلف مع كل من إجابات أخرى.

1. متعدد باكسوس لا لا أقول أن الزعيم هو فقط مقدم العطاء; هذا من شأنه أن يؤدي النظام إلى نقطة واحدة من الفشل.حتى خلال شبكة أقسام النظام قد لا تكون قادرة على التقدم.متعدد باكسوس هو الأمثل السماح عقدة واحدة (على زعيم) تخطي إعداد بعض المراحل.العقد الأخرى ، والتفكير زعيم ميت قد يحاول مواصلة سبيل المثال نيابة عنها ، ولكن يجب أن لا تزال تستخدم الأساسية الكاملة-باكسوس البروتوكول.

2. Nacking قبول رسالة ينتهك باكسوس الخوارزمية. وهو متقبل ينبغي أن تقبل كل القيم إلا إذا كان قد وعد لا تقبل ذلك. (تجاهل هو مسموح به ولكن غير مستحسن ؛ إنه فقط بسبب تراجع الرسائل المسموح بها.)

3. هناك أيضا حلا لهذا.المشكلة هي مع الزعيم الجولة رقم (N+1 في السؤال).

وهنا بعض الافتراضات:

• لديك مخطط هذه الجولة معرفات منفصلة عبر كافة العقد (مطلوب من قبل باكسوس على أي حال).
• لديك طريقة تحديد العقدة هي الرائدة في باكسوس سبيل المثال (مطلوب متعددة باكسوس).زعيم قادر على تغيير من باكسوس المثال التالي.
  جانبا: بدوام جزئي البرلمان يوحي هذا يتم عن طريق الزعيم الفوز قبل باكسوس سبيل المثال (القسم 3.1) وتشير إلى أنها يمكن أن تبقى زعيم طالما هي على قيد الحياة أو أغنى (القسم 3-3-1).أنا صريحة ELECT_NEW_LEADER:<node> قيمة المقترحة عبر باكسوس.
• الزعيم فقط يتخطى مرحلة تحضير على الأولي جولة في سبيل المثال ؛ و يستخدم كامل الأساسية باكسوس في الجولات اللاحقة.

مع هذه الافتراضات ، الحل هو بسيط جدا.زعيم مجرد يختار منخفضة حقا الجولة معرف انها الأولية قبول المرحلة.هذه الهوية (التي سوف نسميها INITIAL_ROUND_ID) يمكن أن يكون أي شيء طالما أنه أقل من جميع العقد حول معرفات.اعتمادا على الهوية الخاصة بك-اختيار المخطط ، اما -1 ، 0 ، أو عدد صحيح.MIN_VALUE العمل.

يعمل بسبب عقدة أخرى (سأتصل له ستيوارت) يجب أن تذهب من خلال الكاملة باكسوس البروتوكول أن تقترح أي شيء ، جولته id هو دائما أكبر من INITIAL_ROUND_ID.هناك نوعان من الحالات إلى النظر في:ما إذا كان أو لم يكن الزعيم قبول رسائل إلى أي من العقد على ستيوارت إعداد رسالة فعل.

عند الزعيم قبول المرحلة لم يصل أي العقد ، ستيوارت سوف نعود أي قيمة في أي وعد و يمكن المضي قدما تماما مثل العادية الأساسية-باكسوس.

وعندما الزعيم قبول المرحلة وقد وصلت إلى عقدة ، ستيوارت سوف نعود قيمة في الوعد الذي يستخدم على مواصلة الخوارزمية مثل Basic-باكسوس.

في كلتا الحالتين, لأن ستيوارت جولة id أكبر من INITIAL_ROUND_ID أي بطيئة قبول رسائل عقدة يتلقى من الزعيم سوف يؤدي دائما إلى Nack.

لا يوجد منطق خاص على أي متقبل أو ستيوارت.والحد الأدنى من منطق خاص على الزعيم (بمعنى.اختيار منخفضة حقا INITIAL_ROUND_ID).

---

إشعار إذا قمنا بتغيير المرجع سؤال حرف واحد ثم OP الذات الجواب الصحيح:Nack.

• تلقي:إعداد(N)
• الرد:وعد(ن, null)
• تلقي:تقبل!(N, V1)
• الرد:قبلت(ن, V1)
• تلقي:تقبل!(N-1, V2)
• الرد: Nack(N, V1)

ولكن كما هو عليه ، جوابه يكسر باكسوس خوارزمية;ينبغي أن تقبل!

• تلقي:إعداد(N)
• الرد:وعد(ن, null)
• تلقي:تقبل!(N, V1)
• الرد:قبلت(ن, V1)
• تلقي:تقبل!(N+1, V2)
• الرد: تقبل!(N+1, V2)

Answer 2

إن صحة Multi-Paxos مشروطة بشرط ألا يتغير القائد ( أي ، مقدم الطلب) بين مثيلات Paxos المتتالية. من البرلمان بدوام جزئي القسم 3.1 (بروتوكول البرلمان متعدد المراسيم):

منطقيا ، البروتوكول البرلماني [a.k.a. Multi-Paxos] تستخدم أ مثيل منفصل لبروتوكول السينودس الكامل [a.k.a. Paxos] لكل رقم مرسوم. ومع ذلك، رئيس واحد [a.k.a. مقدم / قائد] تم اختياره لجميع هذه الأمثلة ، وقام بإجراء الأول خطوتان من البروتوكول مرة واحدة فقط.
_{[التركيز الإضافي ملكي.]}

لذلك ، تفترض شركة Multi-Paxos أن الحالة التي وصفتها - عندما يأتي مقدم العرض الثاني عبر الإنترنت ويعتقد أنه (وكان دائمًا) زعيمًا - لن تحدث أبدًا. في حالة حدوث مثل هذه الحالة ، فلا ينبغي لأحد استخدام Multi-Paxos. فيما يتعلق بالاحتمال الثاني - عندما لا يصل الكود العام للمقدم الثاني إلى المستقبِل - حقيقة أن مقدم العرض الثاني أرسل بالفعل رمزًا ترميزًا عامًا يعني أنه أرسل في السابق رمزًا ترميزًا عامًا كان عبارة عن كود علامة ترميز عام عن طريق النصاب القانوني للمقبلين. نظرًا لأن المستقبلين قد وعدوا بالفعل مقدم العرض الأول على رمز الترقيم العام المستدير ، فيجب أن يكون قد تم إرسال الكود العام للعارض الثاني قبل تقريب كود الترقيم العام. لذلك ، يجب أن يحتوي رمز العلامة العام النهائي على عداد أقل من رمز علامة عام.

تعديل: تجدر الإشارة أيضًا إلى أن هذا الإصدار من البروتوكول ليس قويًا بالنسبة لـ الفشل البيزنطي :

لا يتسامح [بروتوكول Paxon Parliament] مع الإخفاقات التعسفية والخبيثة ، كما أنه لا يضمن استجابة محدودة الوقت.
_{- البرلمان بدوام جزئي ، القسم 4.1}

Answer 3

ربما تكون الإجابة الأبسط هي ملاحظة أن هذا هو الحال عندما تم قبول أمر التحضير (N + 1) من قبل الأغلبية التي لم تشمل الشخص الذي يقبله.

للتوضيح: بمجرد أن يعرف القائد أن بعض الأغلبية قد وعدت (N + 1) ، فإنه يرسل قبول (N + 1 ، x) إلى جميع القبول ،وحتى إذا ردت أغلبية أخرى من المقبولين بالموافقة (N + 1) ، فقد تم التوصل إلى إجماع.

ليس هذا سيناريو غير عادي.

Answer 4

(الرد على سؤالي)

ما أفهمه حاليًا هو أنه لا ينبغي علي قبول القيمة في N + 1 (أي عدم الإجابة على الإطلاق أو إرسال NACK) ، وبالتالي إجبار القائد على بدء جولة أخرى باستخدام Prepare (إذا لم تصل الأغلبيةالإجماع حتى الآن).بعد أن أتلقى التحضير (N + 2) ، سأرد بوعد (N + 2 ، V1) وأستمر كالمعتاد.