Почему определяется порог отказоустойчивости византийской “асинхронной” сети?(где он не может допустить даже одного неисправного узла)

Question

В следующем ответе (Ссылка: https://bitcoin.stackexchange.com/a/58908/41513), было показано, что для Асинхронное Византийское соглашение:

"мы не можем допустить, чтобы 1/3 или более узлов были нечестными, иначе мы потеряем либо безопасность, либо жизнеспособность".

Для этого доказательства были рассмотрены следующие условия/требования:

1. Наша система - это асинхронный.
2. Некоторые участники могут быть злонамеренными.
3. Мы хотим безопасности.
4. Мы хотим живости.

Фундаментальный вопрос заключается в том, что:

С учетом хорошо известной статьи под названием: "Невозможность распределенного консенсуса при Одном Неисправном процессе" (Ссылка: https://apps.dtic.mil/dtic/tr/fulltext/u2/a132503.pdf)

показывая , что:

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

Можем ли мы по - прежнему предполагать , что сеть асинхронна ?Поскольку в этом случае сеть не может допустить даже одного неисправного узла.

Answer 1

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

1.Невозможность распределенного консенсуса при Одном Неисправном процессе

Этот основополагающий результат (Майкла Фишера, Нэнси Линч и Майкла Патерсона) касается распределенного консенсуса, когда система не просто асинхронна, но и удовлетворяет:

• Детерминизм. Консенсусный алгоритм не использует никакой случайности.

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

Давайте посмотрим, почему эти свойства слишком сильны и делают невозможным распределенный консенсус.

Рассмотрим пример:Элис, Боб и Чарли - друзья и хотят решить, где встретиться за ужином.Вполне возможно, что один из них неожиданно уходит в самоволку (или решает, что им больше неинтересно быть друзьями) и перестает отвечать на сообщения.В этом случае двое других все еще могут определиться с местом встречи.Что же им теперь делать?

Очевидный подход заключался бы в том, что:

Элис просто решает, куда идти, и рассказывает об этом Бобу и Чарли.

Но это не сработает, потому что Элис может быть той, кто уходит в самоволку.Итак, чтобы исправить это, следующим наиболее очевидным подходом может быть:

И Алиса, и Боб говорят всем остальным, куда идти.Если все услышат от Алисы, то они пойдут туда, куда скажет Алиса;в противном случае они пойдут туда, куда скажет Боб.

Но здесь возникает новая проблема.Предположим, вы Чарли.Если вы услышите что-нибудь от Элис, вы знаете, куда обратиться.Если вы ничего не услышите ни от одного из них, вы будете ждать ответа.Проблема возникает, когда вы получили известие от Боба, но не от Алисы.Поскольку существуют произвольные задержки сообщений, вы не можете взять на себя обязательство перейти туда, куда сказал Боб:Алиса могла бы сказать, куда обратиться, а вы просто еще не получили этого!Итак, вы полностью застряли, и если случится так, что Элис уйдет в самоволку, вы просто будете ждать вечно.

Проблема здесь в том, что у нас нет возможности прервать транзакцию;невозможно сказать: "О'кей, это не работает, прошло слишком много времени, и я не получал сообщений с задержкой - давайте попробуем еще раз". В реальных алгоритмах консенсуса (наиболее известным из которых является Paxos) существует вероятность того, что раунды завершатся неудачей из-за сетевых задержек, и в этом случае они просто повторяют попытку, надеясь на более короткие сетевые задержки.Кроме того, проблему можно обойти, используя рандомизированные протоколы, которые обычно работайте и продолжайте работать вечно только с небольшой (или даже нулевой) вероятностью.

2.Асинхронное Византийское соглашение, где меньше $1/3$ один из узлов выходит из строя

Сообщение bitcoinSE, на которое вы ссылаетесь, умалчивает о проблеме жизнеспособности, говоря только, что это "способность продолжать продвигаться вперед".Фактически, приведенный выше результат показывает, что самая сильная форма этого невозможна, поэтому мы должны ослабить наши требования / предположения.

Давайте рассмотрим два примера.В книге Мигеля Кастро и Барбары Лисков "Практическая византийская отказоустойчивость" они достигают практической жизнеспособности при неисправности менее трети узлов за счет предполагая, что задержки сообщений не будут расти бесконечно.Как заявляют авторы:

Мы гарантируем оперативность, то есть клиенты в конечном итоге получают ответы на свои запросы, предоставленные не более $\фракция {n-1}{3}$ копии неисправны и $задержка(t)$ не растет быстрее, чем $т$ бесконечно...Это довольно слабая синхронность предположение, которое, вероятно, верно в любой реальной системе при условии, что сетевые сбои в конечном итоге устраняются, все же это позволяет нам обойти результат невозможности, приведенный в [9].

Здесь [9] приведен результат невозможности, рассмотренный выше.Проще говоря, в нашем примере они избегают описанной выше проблемы с Charlie, требуя слабой формы синхронности:Чарли не просто должен ждать вечно, поскольку мы знаем, что задержки сообщений могут расти только временно, а не бесконечно.(Конечно, сам алгоритм становится намного сложнее, но отчасти это концептуальная идея о том, почему возможна живучесть.)

В работе Рена Канетти и Таля Рабина "Быстрое асинхронное византийское соглашение с оптимальной устойчивостью" они используют случайность, чтобы получить живучесть с меньшими затратами. $n/3$ Сбои византийского узла.Из их газеты:

В этой настройке мы опишем $(\lceil\frac{n}{3} ceil- 1)$-устойчивый протокол Византийского соглашения.С подавляющей вероятностью все исправные игроки завершат выполнение протокола.При условии, что все игроки, не имеющие ошибок, завершили выполнение протокола, они делают это в постоянно ожидаемое время.

Здесь $(\lceil\frac{n}{3} ceil- 1)$-устойчивость просто означает, что менее трети узлов являются византийскими.Обратите внимание на ключевые слова с подавляющей вероятностью. Таким образом, у них есть вероятностный алгоритм, который имеет множество возможных "запусков", и в подавляющем большинстве случаев большинство из них работают.Обратите внимание, что приведенный выше результат невозможности подразумевает, что всегда должно быть некоторые выполняется там, где живучесть не возникает, т.е.единого мнения нет:

Основополагающий результат Фишера, Линча и Патерсона [FLP] о невозможности детерминированных протоколов подразумевает, что любой (рандомизированный) протокол, достигающий уровня BA, должен иметь не завершающиеся запуски.