تحمل خطای بیزانسی
تحمل خطای بیزانسی به مطالعه دستیابی به توافق در شرایطی میپردازد که برخی فرآیندها ممکن است به طور دلخواه دچار خطا شوند، از جمله با ارسال پیامهای متناقض یا مخرب.
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 فرآیند دیگر ممکن است کند یا غیرقابل دسترس باشند؛ تنها با بیش از سه برابر تعداد فرآیندهای معیوب، اکثریت صحیح همیشه میتواند بر ترکیب شرکتکنندگان معیوب و عقبمانده غلبه کند.