تحمل الأخطاء البيزنطية
تحمل الأخطاء البيزنطية هو دراسة الوصول إلى اتفاق عندما قد تفشل بعض العمليات بشكل تعسفي، بما في ذلك إرسال رسائل متضاربة أو ضارة.
Definition
الخطأ البيزنطي هو انحراف تعسفي عن مواصفات المكون، بما في ذلك السلوك الضار؛ تحمل الأخطاء البيزنطية هو قدرة بروتوكول موزع على تلبية شروط صحته على الرغم من وجود عدد محدود من المشاركين المعيبين.
Scope
يغطي هذا الموضوع مشكلة الجنرالات البيزنطيين والحدود الصارمة للمرونة التي تحددها (ما لا يقل عن 3f+1 عملية، أو رسائل موقعة، لتحمل f من الأخطاء التعسفية)، وخوارزميات الاتفاق الشفهي المتزامن والرسائل الموقعة، والبروتوكولات العملية غير المتزامنة لتحمل الأخطاء البيزنطية مثل PBFT ومشتقاتها. وهو يشكل الأساس لنماذج الثقة في سلاسل الكتل المسموح بها والخدمات المنسوخة عالية النزاهة.
Core questions
- كم عدد العمليات الصحيحة المطلوبة لتحمل عدد معين من الأخطاء التعسفية؟
- كيف تغير التوقيعات الرقمية حدود المرونة للاتفاق البيزنطي؟
- كيف يمكن جعل الاتفاق البيزنطي فعالاً بما يكفي للأنظمة العملية غير المتزامنة؟
Key theories
- حد الجنرالات البيزنطيين
- مع الرسائل غير الموثقة (الشفهية)، يكون الاتفاق البيزنطي قابلاً للحل إذا وفقط إذا كان أكثر من ثلثي العمليات صحيحة (n > 3f)؛ الرسائل الموثقة ذات التوقيعات غير القابلة للتزوير تخفف هذا الشرط.
- النسخ المتماثل العملي لـ BFT
- يُظهر PBFT أن الاتفاق البيزنطي يمكن أن يعمل في نظام متزامن جزئيًا مع نسخ متماثل لآلة الحالة باستخدام أساسي وبروتوكول من ثلاث مراحل، مما يحقق أداءً عمليًا مع تحمل ما يصل إلى ثلث النسخ المتماثلة المعيبة.
- خوارزميات الاتفاق المتزامن
- في النموذج المتزامن، تحقق خوارزميات الرسائل الشفهية المتكررة والرسائل الموقعة الاتفاق في f+1 جولة، مما يوضح تكلفة تعقيد الجولات لتحمل الأخطاء التعسفية.
Clinical relevance
يُعد تحمل الأخطاء البيزنطية أساس الأنظمة التي يجب أن تصمد ليس فقط أمام الأعطال ولكن أيضًا أمام الاختراق أو السلوك الضار، بما في ذلك سلاسل الكتل المسموح بها، والخدمات المنسوخة عالية الضمان، وأنظمة التحكم في الطيران والفضاء حيث لا يمكن استبعاد الفشل التعسفي للمكونات.
History
وضع بيس وشوستاك ولامبورت حدود الاتفاق في عام 1980 وصاغوها بشكل درامي كمشكلة الجنرالات البيزنطيين في عام 1982؛ لما يقرب من عقدين من الزمان، اعتُبر الاتفاق البيزنطي مكلفًا للغاية من الناحية العملية حتى أظهر PBFT لكاسترو وليسكوف في عام 1999 تكرارًا بيزنطيًا غير متزامن فعالًا، مما أحيا المجال وأثر لاحقًا على إجماع سلاسل الكتل.
Key figures
- Leslie Lamport
- Robert Shostak
- Marshall Pease
- Miguel Castro
- Barbara Liskov
Related topics
Seminal works
- lamport1982byz
- castro1999
- pease1980
Frequently asked questions
- لماذا يتطلب تحمل f من الأخطاء البيزنطية 3f+1 عملية؟
- يجب أن تصل العمليات الصحيحة إلى قرار الأغلبية حتى عندما تكذب f من العمليات المعيبة وقد تكون f أخرى بطيئة أو غير قابلة للوصول؛ فقط بوجود أكثر من ثلاثة أضعاف عدد العمليات المعيبة يمكن للأغلبية الصحيحة دائمًا أن تتفوق في التصويت على مزيج المشاركين المعيبين والمتأخرين.