stringtranslate.com

Византийский разлом

Византийская ошибка (также проблема византийских общих правил , интерактивная согласованность , конгруэнтность источников , лавина ошибок , проблема византийского соглашения и византийский сбой [1] ) — это состояние компьютерной системы, особенно распределенных вычислительных систем, при котором компоненты могут выходить из строя и существует несовершенность. информация о том, вышел ли из строя компонент. Этот термин получил свое название от аллегории «проблема византийских генералов», [2] разработанной для описания ситуации, в которой, чтобы избежать катастрофического сбоя системы, участники системы должны договориться о согласованной стратегии, но некоторые из этих участников ненадежны.

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

Определение

Византийская ошибка — это любая ошибка, имеющая разные симптомы для разных наблюдателей. [3] Византийский сбой — это потеря системной службы из-за византийской ошибки в системах, требующих консенсуса между распределенными узлами. [4]

Если все генералы атакуют согласованно, битва выиграна (слева). Если два генерала ложно заявят, что намерены атаковать, но вместо этого отступят, битва проиграна (справа).

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

Проблема осложняется наличием коварных генералов, которые могут не только проголосовать за неоптимальную стратегию; они могут делать это выборочно. Например, если голосуют девять генералов, четверо из которых поддерживают атаку, а четыре других — за отступление, девятый генерал может послать голос об отступлении этим генералам в пользу отступления, а голос о нападении — остальным. Те, кто получил голос отступления от девятого генерала, отступят, а остальные нападут (что может не пойти на пользу нападающим). Проблема еще больше усложняется тем, что генералы физически разделены и вынуждены отправлять свои голоса через посыльных, которые могут не доставить голоса или подделать фальшивые голоса.

Византийская отказоустойчивость может быть достигнута, если лояльные (безупречные) генералы имеют согласие большинства относительно своей стратегии. Для отсутствующих сообщений может быть присвоено значение голосования по умолчанию. Например, отсутствующим сообщениям можно присвоить «нулевое» значение . Кроме того, если соглашение заключается в том, что нулевые голоса составляют большинство, можно использовать заранее назначенную стратегию по умолчанию (например, отступление). [5]

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

Формально определено:

Дана система из n компонентов, t из которых нечестны, и предполагается, что между всеми компонентами имеются только двухточечные каналы. [6]

Всякий раз, когда компонент A пытается передать значение x , другим компонентам разрешается обсудить друг с другом и проверить согласованность трансляции A , и в конечном итоге прийти к общему значению y .

Говорят, что система устойчива к византийским ошибкам, если компонент A может передать значение x , а затем:

  1. Если A является честным, то все честные компоненты согласны относительно значения x .
  2. В любом случае все честные компоненты соглашаются на одно и то же значение y .

Проблема изучалась в случае как синхронной, так и асинхронной связи.

Предполагается, что приведенный выше коммуникационный граф является полным графом (т. е. каждый компонент может общаться друг с другом), но коммуникационный граф может быть ограничен.

Его также можно смягчить в более «реалистичной» задаче, когда неисправные компоненты не объединяются в сговор, пытаясь заманить другие на ошибку. Именно в этой ситуации были разработаны практические алгоритмы.

История

Проблема достижения византийского консенсуса была задумана и формализована Робертом Шостаком , который назвал ее проблемой интерактивной согласованности . Эта работа была выполнена в 1978 году в рамках спонсируемого НАСА проекта SIFT [7] в Лаборатории компьютерных наук SRI International . SIFT (для программно-реализованной отказоустойчивости) был детищем Джона Уэнсли и был основан на идее использования нескольких компьютеров общего назначения, которые будут взаимодействовать посредством парного обмена сообщениями для достижения консенсуса, даже если некоторые из компьютеров были неисправны.

В начале проекта не было ясно, сколько всего компьютеров необходимо, чтобы гарантировать, что заговор n неисправных компьютеров не сможет «помешать» усилиям правильно работающих компьютеров по достижению консенсуса. Шостак показал, что необходимо минимум 3 n+ 1, и разработал двухраундовый протокол обмена сообщениями 3 n+1 , который будет работать для n =1. Его коллега Маршалл Пиз обобщил алгоритм для любого n > 0, доказав, что 3 n +1 одновременно необходимо и достаточно. Эти результаты вместе с более поздним доказательством Лесли Лэмпортом достаточности 3 n с использованием цифровых подписей были опубликованы в основополагающей статье « Достижение соглашения при наличии ошибок». [8] За эту статью авторы были удостоены премии Эдсгера В. Дейкстры 2005 года.

Чтобы облегчить понимание проблемы интерактивной согласованности, Лэмпорт придумал красочную аллегорию, в которой группа армейских генералов формулирует план нападения на город. В первоначальной версии истории генералы были командующими албанской армией . Название было изменено и в конечном итоге остановилось на « Византийском » по предложению Джека Голдберга, чтобы исключить любые потенциальные оскорбления в будущем. [9] Эта формулировка проблемы вместе с некоторыми дополнительными результатами была представлена ​​теми же авторами в их статье 1982 года «Проблема византийских генералов». [5]

смягчение последствий

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

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

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

Термины «неисправность» и «отказ» используются здесь в соответствии со стандартными определениями [10], первоначально созданными совместным комитетом по «Фундаментальным концепциям и терминологии», сформированным Техническим комитетом IEEE Computer Society по надежным вычислениям и отказоустойчивости и Рабочей группой IFIP 10.4 по Надежные вычисления и отказоустойчивость. [11] См. также надежность .

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

Решения

Несколько первых решений были описаны Лэмпортом, Шостаком и Пизом в 1982 году. [5] Они начали с того, что отметили, что проблему генералов можно свести к решению проблемы «командир и лейтенанты», где все лояльные лейтенанты должны действовать в унисон и что их действие должно соответствовать приказу Командующего в случае лояльности Командующего:

Было разработано несколько системных архитектур c. 1980 год, реализовавший византийскую отказоустойчивость. К ним относятся: FTMP Draper, [14] MMFCS Honeywell, [15] и SIFT SRI. [7]

В 1999 году Мигель Кастро и Барбара Лисков представили алгоритм «Практическая византийская отказоустойчивость» (PBFT) [16] , который обеспечивает высокопроизводительную репликацию византийского конечного автомата, обрабатывая тысячи запросов в секунду с увеличением задержки на доли миллисекунды.

После PBFT было введено несколько протоколов BFT для повышения его надежности и производительности. Например, Q/U, [17] HQ, [18] Zyzzyva, [19] и ABsTRACTs, [20] рассматривали вопросы производительности и стоимости; тогда как другие протоколы, такие как Aardvark [21] и RBFT, [22] решают проблемы его надежности. Кроме того, компания Adapt [23] попыталась использовать существующие протоколы BFT путем адаптивного переключения между ними, чтобы повысить надежность и производительность системы при изменении основных условий. Кроме того, были представлены протоколы BFT, которые используют доверенные компоненты для уменьшения количества реплик, например A2M-PBFT-EA [24] и MinBFT. [25]

Приложения

Несколько примеров произошедших византийских неудач приведены в двух эквивалентных журнальных статьях. [3] [4] Эти и другие примеры описаны на веб-страницах NASA DASHlink. [26]

Приложения в вычислительной технике

Византийские механизмы отказоустойчивости используют компоненты, которые повторяют входящее сообщение (или просто его подпись) другим получателям этого входящего сообщения. Все эти механизмы предполагают, что повторение сообщения блокирует распространение византийских симптомов. Для систем с высокой степенью безопасности или критичности защиты эти предположения должны быть верны до приемлемого уровня покрытия неисправностей . При предоставлении доказательств посредством тестирования одной из трудностей является создание достаточно широкого спектра сигналов с византийскими симптомами. [27] Для такого тестирования, скорее всего, потребуются специальные средства определения ошибок . [28] [29]

Военное применение

Византийские ошибки наблюдались нечасто и нерегулярно во время испытаний на долговечность недавно построенных подводных лодок класса «Вирджиния» , по крайней мере, до 2005 года (когда о проблемах было публично сообщено). [30]

Криптовалютные приложения

Сеть Биткойн работает параллельно, создавая блокчейн с доказательством работы, позволяющий системе преодолевать византийские сбои и достигать согласованного глобального представления о состоянии системы. [31] [32] Некоторые блокчейны с доказательством доли также используют алгоритмы BFT. [33]

Приложения в авиации

Некоторые авиационные системы, такие как система управления информацией о самолете Boeing 777 (через сеть ARINC 659 SAFEbus), система управления полетом Boeing 777 и системы управления полетом Boeing 787, используют византийскую отказоустойчивость; поскольку это системы реального времени, их византийские решения по отказоустойчивости должны иметь очень низкую задержку. Например, SAFEbus может обеспечить византийскую отказоустойчивость с добавленной задержкой порядка микросекунды. [34] [35] [36] В своей конструкции SpaceX Dragon учитывает византийскую отказоустойчивость. [37]

Смотрите также

Рекомендации

  1. ^ Киррманн, Хуберт (nd). «Отказоустойчивые вычисления в промышленной автоматизации» (PDF) . Швейцария: Исследовательский центр АББ. п. 94. Архивировано из оригинала (PDF) 26 марта 2014 г. Проверено 2 марта 2015 г.
  2. ^ Лэмпорт, Л .; Шостак Р.; Пиз, М. (1982). «Проблема византийских генералов» (PDF) . Транзакции ACM в языках и системах программирования . 4 (3): 382–401. CiteSeerX 10.1.1.64.2312 . дои : 10.1145/357172.357176. S2CID  55899582. Архивировано (PDF) из оригинала 13 июня 2018 г. 
  3. ^ abcd Дрисколл, К.; Холл, Б.; Паулич, М.; Цумстег, П.; Сивенкрона, Х. (2004). «Настоящие византийские генералы». 23-я конференция по цифровым авиационным системам (IEEE Cat. No.04CH37576) . стр. 6.Д.4–61–11. дои : 10.1109/DASC.2004.1390734. ISBN 978-0-7803-8539-9. S2CID  15549497.
  4. ^ abc Дрисколл, Кевин; Холл, Брендан; Сивенкрона, Хокан; Цумстег, Фил (2003). «Византийская отказоустойчивость: от теории к реальности». Компьютерная безопасность, надежность и защищенность . Конспекты лекций по информатике. Том. 2788. стр. 235–248. дои : 10.1007/978-3-540-39878-3_19. ISBN 978-3-540-20126-7. ISSN  0302-9743. S2CID  12690337.
  5. ^ abc Лэмпорт, Л .; Шостак Р.; Пиз, М. (1982). «Проблема византийских генералов» (PDF) . Транзакции ACM в языках и системах программирования . 4 (3): 387–389. CiteSeerX 10.1.1.64.2312 . дои : 10.1145/357172.357176. S2CID  55899582. Архивировано из оригинала (PDF) 7 февраля 2017 года. 
  6. ^ Матиас Фитци (2002). «Обобщенные модели связи и безопасности в Византийском соглашении» (PDF) . ETH Цюрих .
  7. ^ ab «SIFT: проектирование и анализ отказоустойчивого компьютера управления самолетом». Надежность микроэлектроники . 19 (3): 190. 1979. doi :10.1016/0026-2714(79)90211-7. ISSN  0026-2714.
  8. ^ Пиз, Маршалл; Шостак, Роберт; Лэмпорт, Лесли (апрель 1980 г.). «Достижение соглашения при наличии разногласий». Журнал Ассоциации вычислительной техники . 27 (2): 228–234. CiteSeerX 10.1.1.68.4044 . дои : 10.1145/322186.322188. S2CID  6429068. 
  9. ^ Лэмпорт, Лесли (19 декабря 2016 г.). «Проблема византийских генералов». Транзакции ACM в языках и системах программирования . НИИ Интернешнл . Проверено 18 марта 2019 г.
  10. ^ Авизиенис, А.; Лапри, Ж.-К.; Рэнделл, Брайан ; Ландвер, К. (2004). «Основные концепции и таксономия надежных и безопасных вычислений». Транзакции IEEE для надежных и безопасных вычислений . 1 (1): 11–33. дои : 10.1109/TDSC.2004.2. hdl : 1903/6459 . ISSN  1545-5971. S2CID  215753451.
  11. ^ «Надежные вычисления и отказоустойчивость». Архивировано из оригинала 02 апреля 2015 г. Проверено 2 марта 2015 г.
  12. ^ Фельдман, П.; Микали, С. (1997). «Оптимальный вероятностный протокол для синхронного византийского соглашения» (PDF) . СИАМ Дж. Компьютер . 26 (4): 873–933. дои : 10.1137/s0097539790187084. Архивировано (PDF) из оригинала 5 марта 2016 г. Проверено 14 июня 2012 г.
  13. ^ Паулич, М.; Моррис, Дж.; Холл, Б.; Дрисколл, К.; Латронико, Э.; Купман, П. (2005). «Покрытие и использование циклических избыточных кодов в сверхнадежных системах». 2005 Международная конференция по надежным системам и сетям (DSN'05). стр. 346–355. дои : 10.1109/DSN.2005.31. ISBN 978-0-7695-2282-1. S2CID  14096385.
  14. ^ Хопкинс, Альберт Л.; Лала, Джайнараян Х.; Смит, Т. Бэзил (1987). «Эволюция отказоустойчивых вычислений в лаборатории Чарльза Старка Дрейпера, 1955–85». Эволюция отказоустойчивых вычислений . Надежные вычислительные и отказоустойчивые системы. Том. 1. С. 121–140. дои : 10.1007/978-3-7091-8871-2_6. ISBN 978-3-7091-8873-6. ISSN  0932-5581.
  15. ^ Дрисколл, Кевин; Пападопулос, Грегори; Нельсон, Скотт; Хартманн, Гэри; Рамохалли, Гаутам (1984), Мультимикропроцессорная система управления полетом (технический отчет), База ВВС Райт-Паттерсон, Огайо: AFWAL/FIGL Командование систем ВВС США, AFWAL-TR-84-3076
  16. ^ Кастро, М.; Лисков, Б. (2002). «Практическая византийская отказоустойчивость и упреждающее восстановление». Транзакции ACM в компьютерных системах . 20 (4). Ассоциация вычислительной техники : 398–461. CiteSeerX 10.1.1.127.6130 . дои : 10.1145/571637.571640. S2CID  18793794. 
  17. ^ Абд-эль-Малек, М.; Гангер, Г.; Хорошая песня.; Райтер, М.; Уайли, Дж. (2005). «Отказо-масштабируемые византийские отказоустойчивые службы». Обзор операционных систем ACM SIGOPS . 39 (5). Ассоциация вычислительной техники : 59. doi : 10.1145/1095809.1095817.
  18. ^ Коулинг, Джеймс; Майерс, Дэниел; Лисков, Варвара ; Родригес, Родриго; Шрира, Люба (2006). Репликация HQ: протокол гибридного кворума для византийской отказоустойчивости. Материалы 7-го симпозиума USENIX по проектированию и внедрению операционных систем. стр. 177–190. ISBN 1-931971-47-1.
  19. ^ Котла, Рамакришна; Альвизи, Лоренцо; Далин, Майк; Клемент, Аллен; Вонг, Эдмунд (декабрь 2009 г.). «Zyzzyva: спекулятивная византийская отказоустойчивость». Транзакции ACM в компьютерных системах . 27 (4). Ассоциация вычислительной техники : 1–39. дои : 10.1145/1658357.1658358.
  20. ^ Геррауи, Рашид; Кнежевич, Никола; Вуколич, Марко; Кема, Вивьен (2010). Следующие 700 протоколов BFT. Материалы 5-й Европейской конференции по компьютерным системам. ЕвроСис. Архивировано из оригинала 2 октября 2011 г. Проверено 4 октября 2011 г.
  21. ^ Клемент, А.; Вонг, Э.; Алвиси, Л.; Далин, М.; Маркетти, М. (22–24 апреля 2009 г.). Как сделать византийские отказоустойчивые системы терпимыми к византийским ошибкам (PDF) . Симпозиум по проектированию и внедрению сетевых систем. УСЕНИКС . Архивировано (PDF) из оригинала 25 декабря 2010 г. Проверено 17 февраля 2010 г.
  22. ^ Облин, П.-Л.; Бен Мохтар, С.; Кема, В. (8–11 июля 2013 г.). RBFT: избыточная византийская отказоустойчивость. 33-я Международная конференция IEEE по распределенным вычислительным системам. Международная конференция по распределенным вычислительным системам . Архивировано из оригинала 5 августа 2013 года.
  23. ^ Бахсун, JP; Геррауи, Р.; Шокер, А. (01 мая 2015 г.). «Сделать протоколы BFT действительно адаптивными». Международный симпозиум IEEE по параллельной и распределенной обработке , 2015 г. стр. 904–913. дои : 10.1109/IPDPS.2015.21. ISBN 978-1-4799-8649-1. S2CID  16310807.
  24. ^ Чун, Бён Гон; Маниатис, Петрос; Шенкер, Скотт; Кубятович, Джон (1 января 2007 г.). «Аттестованная память только для добавления». Материалы двадцать первого симпозиума ACM SIGOPS по принципам операционных систем . СОСП '07. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 189–204. дои : 10.1145/1294261.1294280. ISBN 9781595935915. S2CID  6685352.
  25. ^ Веронезе, GS; Коррейя, М.; Бессани, АН; Лунг, LC; Вериссимо, П. (1 января 2013 г.). «Эффективная византийская отказоустойчивость». Транзакции IEEE на компьютерах . 62 (1): 16–30. CiteSeerX 10.1.1.408.9972 . дои : 10.1109/TC.2011.221. ISSN  0018-9340. S2CID  8157723. 
  26. ^ Дрисколл, Кевин (11 декабря 2012 г.). «Реальные системные сбои». DASHссылка . НАСА . Архивировано из оригинала 02 апреля 2015 г. Проверено 2 марта 2015 г.
  27. ^ Наня, Т.; Гусен, ХА (1989). «Византийская модель отказа оборудования». Транзакции IEEE по автоматизированному проектированию интегральных схем и систем . 8 (11): 1226–1231. дои : 10.1109/43.41508. ISSN  0278-0070.
  28. ^ Мартинс, Роландо; Ганди, Раджив; Нарасимхан, Прия; Пертет, Сойла; Казимиро, Антонио; Крейц, Диего; Вериссимо, Пауло (2013). «Опыт внедрения ошибок в византийский отказоустойчивый протокол». Промежуточное ПО 2013 . Конспекты лекций по информатике. Том. 8275. стр. 41–61. дои : 10.1007/978-3-642-45065-5_3. ISBN 978-3-642-45064-8. ISSN  0302-9743. S2CID  31337539.
  29. ^ Патент США 7475318, Кевин Р. Дрисколл, «Метод тестирования чувствительного диапазона входного сигнала византийских фильтров», выдан 6 января 2009 г., передан Honeywell International Inc. 
  30. ^ Уолтер, К.; Эллис, П.; ЛаВэлли, Б. (2005). «Надежная платформа: отказоустойчивая сервисная архитектура на основе свойств». Девятый международный симпозиум IEEE по системному проектированию высокой надежности (HASE'05) . стр. 34–43. дои :10.1109/HASE.2005.23. ISBN 978-0-7695-2377-4. S2CID  21468069.
  31. ^ Рубби, Мэтт (20 января 2024 г.). «Как проблема византийских генералов относится к вам в 2024 году». Лебединый биткойн . Проверено 27 января 2024 г.
  32. ^ Толониат, Пьер; Грамоли, Винсент (2022), Тран, Дюк А.; Тайский, Мой Т.; Кришнамачари, Бхаскар (ред.), «Формальная проверка византийской отказоустойчивости блокчейна», Справочник по блокчейну , оптимизации Springer и ее приложениям, Cham: Springer International Publishing, стр. 389–412, arXiv : 1909.07453 , doi : 10.1007/978- 3-031-07535-3_12, ISBN 978-3-031-07535-3, получено 27 января 2024 г.
  33. ^ Дейрментзоглу, Папакириакопулос и Пацакис 2019, стр. 28716.
  34. ^ М., Паулич; Дрисколл, К. (9 января 2015 г.). «Глава 48: SAFEbus». В Журавски, Ричард (ред.). Справочник по технологиям промышленной связи, второе издание . ЦРК Пресс. стр. 48–1–48–26. ISBN 978-1-4822-0733-0.
  35. ^ Томас А. Хензингер; Кристоф М. Кирш (26 сентября 2001 г.). Встроенное программное обеспечение: первый международный семинар, EMSOFT 2001, Тахо-Сити, Калифорния, США, 8–10 октября 2001 г. Материалы (PDF) . Springer Science & Business Media. стр. 307–. ISBN 978-3-540-42673-8. Архивировано (PDF) из оригинала 22 сентября 2015 г. Проверено 05 марта 2015 г.
  36. ^ Да, YC (2001). «Критическая с точки зрения безопасности авионика для основной системы управления полетом 777». 20-й ДАСК. 20-я конференция по цифровым авиационным системам (кат. № 01CH37219) . Том. 1. С. 1C2/1–1C2/11. дои : 10.1109/DASC.2001.963311. ISBN 978-0-7803-7034-0. S2CID  61489128.
  37. ^ «ELC: Извлеченные уроки SpaceX [LWN.net]» . Архивировано из оригинала 5 августа 2016 г. Проверено 21 июля 2016 г.

Источники

Внешние ссылки