لماذا هو عتبة تحديد البيزنطية التسامح مع الخطأ من "غير المتزامن" الشبكة ؟ (التي لا تحتمل حتى واحدة خاطئة عقدة)

Question

في الإجابة التالية (الرابط: https://bitcoin.stackexchange.com/a/58908/41513), وقد تبين أن غير متزامن البيزنطية الاتفاق:

"نحن لا يمكن أن يتسامح مع 1/3 أو أكثر من العقد كونها غير شريفة أو خسرنا إما السلامة أو liveness."

هذا دليل على الشروط التالية/متطلبات تم النظر فيها:

1. لدينا نظام غير متزامن.
2. بعض المشاركين قد تكون ضارة.
3. نريد السلامة.
4. نريد liveness.

سؤال أساسي هو:

مع مراعاة المعروفة بعنوان: "استحالة توزيع توافق مع خلل عملية" (الرابط: https://apps.dtic.mil/dtic/tr/fulltext/u2/a132503.pdf)

تبين أن:

لا تماما غير متزامن توافق البروتوكول يمكن أن يتسامح مع حتى واحد غير معلن عملية الموت,

لا يزال بوسعنا أن نفترض أن الشبكة غير متزامن ؟ كما في هذه الحالة الشبكة تحتمل حتى واحدة خاطئة عقدة.

Answer 1

الجواب له علاقة مع تتبع دقة الافتراضات التي يتم إجراؤها في هذه نتائج مختلفة.باختصار, في حين أن كلا النتائج تفترض عدم التزامن ، "استحالة توزيع توافق مع خلل عملية" يتطلب شكل أقوى من liveness و الحتمية و أن يجعل إجماع من المستحيل.

1.استحالة توزيع توافق مع خلل عملية

هذا المنوي نتيجة (مايكل فيشر نانسي لينش ، مايكل باترسون) عن توزيع توافق في الآراء حيث النظام ليس فقط غير متزامن ، ولكن يرضي أيضا:

• الحتمية. توافق الآراء خوارزمية لا تستخدم أي العشوائية.

• Liveness بموجب رسالة التأخير. ليس فقط الرسائل قد يتأخر بشكل تعسفي ، ولكن علينا أيضا أن تضمن liveness حتى في وجود مثل هذا التأخير المستمر.

دعونا نرى لماذا tehse خصائص قوية جدا ، وجعل إجماع توزيعها من المستحيل.

ينظر على سبيل المثال:أليس " بوب " و "تشارلي" أصدقاء وتريد أن تقرر أين الوفاء لتناول العشاء.فمن الممكن أن واحد منهم بشكل غير متوقع يذهب في اجازة (أو تقرر أنها ليست مهتمة في أن يكونوا أصدقاء بعد الآن) و توقف عن الاستجابة إلى الرسائل.في هذه الحالة, اثنين آخرين يمكن أن تقرر ما زال على مكان للقاء.الآن ما يجب القيام به ؟

نهج واضح أن:

أليس مجرد تقرر إلى أين تذهب ، و يقول " بوب " و "تشارلي".

ولكن هذا لا يعمل بسبب أليس قد تكون واحدة تغيب.لذلك يصلح هذا القادم الأكثر وضوحا النهج قد يكون:

سواء أليس وبوب أخبر الجميع إلى أين تذهب.إذا كان الجميع يسمع من أليس ، ثم أنها سوف تذهب حيث أليس يقول ؛ وإلا فإنها سوف تذهب حيث يقول بوب.

ولكن هذه مشكلة جديدة.لنفترض أنك تشارلي.إذا سمعت من أليس ، تعرف إلى أين تذهب.إذا سمعت من لا تنتظر أن تسمع.المشكلة هي عندما كنت قد سمعت من بوب, ولكن ليس أليس.لأن هناك التعسفي رسالة التأخير لا يمكن ارتكاب الذهاب حيث بوب وقال:أليس قد قال أين تذهب ، تتلق حتى الآن!لذلك كنت عالقة تماما, و إذا حدث أن أليس قد ذهب بدون اذن, سوف تبقي فقط الانتظار إلى الأبد.

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

2.غير متزامن البيزنطية الاتفاق فيها أقل من $1/3$ العقد تفشل

على bitcoinSE بعد الارتباط اللمعان على مسألة liveness ، مكتفيا بالقول أنه "القدرة على مواصلة التقدم إلى الأمام".في الواقع ، فإن النتيجة أعلاه يظهر أن أقوى شكل هذا أمر مستحيل ، لذلك علينا أن الاسترخاء متطلباتنا / الافتراضات.

دعونا النظر في اثنين من الأمثلة.في ميغيل كاسترو و باربرا Liskov هو "عملية البيزنطية التسامح مع الخطأ" ، وتحقيق عملية liveness مع أقل من ثلث العقد يجري الخاطئة من قبل على افتراض أن رسالة التأخير لا تستمر في النمو إلى أجل غير مسمى.كما في الكتاب:

نحن نضمن liveness ، أي العملاء في نهاية المطاف تلقي الردود على طلباتهم المقدمة في معظم $\فارك{n-1}{3}$ النسخ المعيبة ، $تأخير(t)$ لا تنمو أسرع من $t$ إلى أجل غير مسمى...هذه هي ضعيفة إلى حد ما التزامن افتراض أن من المرجح أن يكون صحيحا في أي نظام حقيقي قدمت شبكة أخطاء هي في نهاية المطاف إصلاحه ، ومع ذلك ، تمكننا من الالتفاف على استحالة النتيجة في [9].

هنا [9] هو استحالة النتيجة التي نوقشت أعلاه.حيث سهل على تجنب هذه المشكلة مع تشارلي التي تتطلب ضعيفة شكل التزامن:تشارلي لا ببساطة للحفاظ على الانتظار إلى الأبد, كما نعلم أن رسالة التأخير يمكن أن تنمو فقط termporarily ، وليس إلى أجل غير مسمى.(طبعا الفعلية خوارزمية يحصل على الكثير أكثر تعقيدا ، ولكن هذا هو جزئيا المفاهيمي فكرة لماذا liveness ممكن.)

في ركض كانيتي وتل رابين "سريع غير متزامن البيزنطية اتفاق مع المثلى الصمود" ، فإنها تستخدم العشوائية للحصول على liveness مع أقل من $n/3$ البيزنطية عقدة الفشل.من الورق:

في هذا الإعداد ، ونحن تصف $(\lceil\فارك{ن}{3} ceil - 1)$-مرونة البيزنطية بروتوكول اتفاق.مع الساحقة احتمال كل غير خلل اللاعبين استكمال تنفيذ البروتوكول.مشروطة حال كل غير خلل اللاعبين قد أكملت تنفيذ البروتوكول ، فإنها تفعل ذلك في ثابت المتوقع الوقت.

هنا $(\lceil\فارك{ن}{3} ceil - 1)$-مرونة فقط يعني أقل من ثلث العقد البيزنطية.ملاحظة الكلمات الرئيسية مع الساحقة احتمال. لذا لديهم احتمالي الخوارزمية التي لديها العديد من ممكن "يعمل" و بأغلبية ساحقة معظمهم من العمل.علما أنه سبق استحالة النتيجة يعني أنه يجب أن يكون هناك دائما بعض يعمل فيها liveness لا تحدث أيلا يوجد توافق في الآراء:

فيشر لينش باترسون [FLP] المنوي استحالة نتيجة حتمية بروتوكولات يعني أن أي (العشوائية) بروتوكول الوصول إلى درجة البكالوريوس يجب أن يكون nonterminating يعمل.