Византийская отказоустойчивость

Византийская отказоустойчивость — это область исследований, посвященная достижению согласия в условиях, когда некоторые процессы могут произвольно выходить из строя, в том числе путем отправки противоречивых или вредоносных сообщений.

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

Seminal works

• lamport1982byz
• castro1999
• pease1980

Frequently asked questions

Почему для допуска f византийских сбоев требуется 3f+1 процессов?

Корректные процессы должны прийти к решению большинства, даже когда f неисправных процессов лгут, а еще f могут быть медленными или недоступными; только при более чем в три раза большем числе процессов, чем неисправных, корректное большинство всегда может переголосовать комбинацию неисправных и отстающих участников.