Введение
Ошибка в компьютерной системе, проявляющая различные симптомы для разных наблюдателей.
Византийская ошибка (также проблема византийских генералов, интерактивная согласованность, согласованность источника, лавинообразный сбой, проблема византийского соглашения и византийский отказ) — это состояние компьютерной системы, особенно распределённых вычислительных систем, при котором компоненты могут выходить из строя, и существует неполная информация о том, вышел ли компонент из строя. Термин происходит от аллегории, "проблемы византийских генералов", разработанной для описания ситуации, в которой, чтобы избежать катастрофического сбоя системы, участники системы должны согласовать единую стратегию, но некоторые из этих участников ненадежны. При византийской ошибке компонент, такой как сервер, может непоследовательно казаться как вышедшим из строя, так и функционирующим системам обнаружения сбоев, проявляя различные симптомы для разных наблюдателей. Другим компонентам сложно объявить его неисправным и исключить из сети, поскольку им сначала необходимо достичь консенсуса относительно того, какой компонент изначально вышел из строя. Византийская отказоустойчивость (BFT) — это способность отказоустойчивой компьютерной системы противостоять таким условиям.
История
Проблема достижения византийского консенсуса была сформулирована и формализована Робертом Шостаком, который назвал её проблемой интерактивной согласованности. Эта работа была выполнена в 1978 году в контексте проекта SIFT, финансируемого NASA. Авторы были удостоены премии Эдсгера В. Дайкстры за эту работу в 2005 году. Чтобы облегчить понимание проблемы интерактивной согласованности, Лампорт разработал яркую аллегорию, в которой группа армейских генералов разрабатывает план атаки на город. В первоначальной версии истории генералы были предсталены как командиры албанской армии. Название было изменено и окончательно закрепилось как "Византийский" по предложению Джека Голдберга, чтобы избежать возможных обид в будущем. Эта формулировка проблемы, вместе с дополнительными результатами, была представлена теми же авторами в их статье 1982 года "Проблема византийских генералов". Изначально разработана совместным комитетом по "Фундаментальным понятиям и терминологии", сформированным Техническим комитетом IEEE Computer Society по надежным вычислениям и отказоустойчивости и Рабочей группой 10.4 IFIP по надежным вычислениям и отказоустойчивости. См. также надежность. Византийская отказоустойчивость касается только согласованности широковещательной передачи, то есть свойства, при котором, когда один компонент передает одно значение всем остальным компонентам, все они получают именно это значение, или, в случае непоследовательности передатчика, остальные компоненты приходят к согласию относительно общего значения. Этот вид отказоустойчивости не гарантирует корректность самого значения; например, злонамеренный компонент, который намеренно отправляет неверное значение, но последовательно отправляет его всем компонентам, не будет обнаружен схемой византийской отказоустойчивости.
Решение
Несколько ранних решений были описаны Лампортом, Шостаком и Писом в 1982 году. Второе решение требует не подделываемых подписей сообщений. Для систем, критичных к безопасности, цифровые подписи (в современных компьютерных системах это может быть реализовано на практике с использованием криптографии с открытым ключом) могут обеспечить византийскую отказоустойчивость в присутствии произвольного числа недобросовестных генералов. Однако для систем, критичных к безопасности функционирования (где "безопасность" относится к преднамеренным угрозам, а "безопасность функционирования" – к неотъемлемым опасностям, связанным с деятельностью или задачей), простые коды обнаружения ошибок, такие как CRC, обеспечивают менее надежную, но часто достаточную защиту при значительно меньших затратах. Это справедливо как для византийских, так и для невизантийских ошибок. Более того, иногда меры безопасности ослабляют безопасность функционирования и наоборот. Таким образом, методы криптографической цифровой подписи не являются оптимальным выбором для систем, критичных к безопасности функционирования, если нет также конкретной угрозы безопасности. Хотя коды обнаружения ошибок, такие как CRC, предпочтительнее криптографических методов, ни один из них не обеспечивает достаточной защиты для активной электроники в системах, критичных к безопасности функционирования. Это иллюстрируется сценарием CRC Шрёдингера, где защищенное CRC сообщение с одним византийским ошибочным битом представляет разные данные разным наблюдателям, и каждый наблюдатель видит допустимый CRC. Примеры: MMFCS от Honeywell и SIFT от SRI. В 1999 году Мигель Кастро и Барбара Лисков представили алгоритм "Практическая византийская отказоустойчивость" (PBFT), обеспечивающий высокопроизводительное реплицирование византийских конечных автоматов, обрабатывающий тысячи запросов в секунду с увеличением задержки менее одной миллисекунды. После PBFT было разработано несколько протоколов BFT для повышения его надежности и производительности. Например, Q/U, HQ, Zyzzyva и ABsTRACTs решали проблемы производительности и стоимости, в то время как другие протоколы, такие как Aardvark и RBFT, решали проблемы надежности. Кроме того, Adapt пытался использовать существующие протоколы BFT, переключаясь между ними адаптивным образом, для повышения устойчивости и производительности системы в зависимости от изменяющихся условий. Также были разработаны протоколы BFT, использующие доверенные компоненты для уменьшения количества реплик, например, A2M PBFT EA и MinBFT.
Приложения
В двух равнозначных научных статьях приводится несколько примеров неудач Византии.
Приложения в вычислительной технике
Византийские механизмы устойчивости к ошибкам используют компоненты, которые повторяют входящее сообщение (или только его подпись) другим получателям этого сообщения. Все эти механизмы основаны на предположении, что повторение сообщения препятствует распространению византийских симптомов. Для систем с высокой степенью надежности или критически важной безопасностью эти предположения должны быть доказаны с приемлемым уровнем охвата отказов. При подтверждении посредством тестирования возникает сложность в создании достаточно широкого спектра сигналов, проявляющих византийские симптомы. Для таких тестов, вероятно, потребуются специализированные генераторы ошибок.
Военные применения
Византийские ошибки наблюдались нечасто и в разрозненных точках во время ходовых испытаний новых подводных лодок класса "Вирджиния", по крайней мере, до 2005 года (когда об этих проблемах стало публично известно).
Приложения для криптовалют
Сеть Биткоина работает параллельно для создания блокчейна с использованием доказательства работы, что позволяет системе противостоять византийским ошибкам и достигать единой глобальной картины состояния системы. Некоторые блокчейны с доказательством доли владения (Proof of Stake) также используют алгоритмы BFT.
Применение в авиации
Некоторые системы самолетов, такие как система управления информацией Boeing 777 (через сеть ARINC 659 SAFEbus), система управления полетом Boeing 777 и системы управления полетом Boeing 787, используют византийскую отказоустойчивость; поскольку это системы реального времени, решения, обеспечивающие византийскую отказоустойчивость в этих системах, должны обладать очень низкой задержкой. Например, SAFEbus способен обеспечить византийскую отказоустойчивость с дополнительной задержкой порядка микросекунды. SpaceX Dragon учитывает византийскую отказоустойчивость при проектировании.