Наличие 0- и 1-валентных конфигураций в доказательстве невозможности ФЛП
В известной статье " Невозможность распределенного консенсуса с одним ошибочным процессом" (JACM85) FLP (Фишер, Линч и Патерсон) доказали удивительный результат, заключающийся в том, что ни один полностью асинхронный протокол консенсуса не может допустить даже одного необъявленного завершения процесса.
В лемме 3, после того, как показано, что D содержит как 0-валентную, так и 1-валентную конфигурации, он говорит:
Вызовите две конфигурации соседями, если одна получается из другой за один шаг. По простой индукции существуют соседи C₀, C₁ ∈ C, такие что Dᵢ = e(Cᵢ) i-валентна, i = 0, 1.
Я могу следовать всему доказательству, за исключением случаев, когда они заявляют о существовании таких C₀ и C₁. Не могли бы вы дать мне несколько советов?
3 ответа
D (множество возможных конфигураций после применения e к элементам C) содержит как 0-валентные, так и 1-валентные конфигурации (и предполагается, что они не содержат двухвалентных конфигураций).
То есть - e сопоставляет каждый элемент в C в 0-валентной или 1-валентной конфигурации. По определению Cдолжен существовать корневой элемент, который связан со всеми другими элементами серией "соседних" отношений, поэтому должна быть граничная точка, в которой элемент C что приводит к 0-валентной конфигурации после e это соседи с элементом в C что приводит к 1-валентной конфигурации после e,
Определить отображение f такой, что f(C) = 0, если e(C) 0-валентный, в противном случае, f(C) = 1, если e(C) 1-валентный
Так как e(C) не может быть двухвалентным, если предположить, что D не имеет двухвалентной конфигурации, f(C) может быть только 0 или 1.
Организовать доступные конфигурации из исходной двухвалентной конфигурации в дереве, в дереве должно быть два соседа C0, C1, которые f(C0) != f(C1), Потому что, если нет, все f(C) одинаковы, что означает, что D имеет только все 0-валентные конфигурации или все 1-валентные конфигурации.
Однажды я пошел по пути чтения всех этих статей только для того, чтобы обнаружить, что это пустая трата времени.
Результат совсем не удивителен.
В документе вы упоминаете "[Невозможность распределенного консенсуса с одним ошибочным процессом]" 1
это длинный список сложных математических доказательств, которые просто приравниваются к:
1) Консенсус является детерминированным состоянием
2) одна (или более) неисправная система в среде является недетерминированной средой
3) Никакое детерминированное состояние, действие или результат не могут быть достигнуты в недетерминированной среде.
Конец. Никаких дальнейших мыслей не требуется.
Вот как это работает в реальном мире за пределами акадамии.
Если вы хотите, чтобы агенты достигли консенсуса, то должны быть добавлены конструкции аппроксимации Синхронного (модель синхронизации), чтобы сделать среду детерминированной в данном наборе ограничений. Например, простые конструкции, такие как Timeouts, Ack/Nack, Handshake, Witness, или более сложные конструкции.
Чем ближе вы хотите приблизиться к синхронной детерминированной модели, тем сложнее становятся конструкции. Гипотетическая синхронная модель будет иметь бесконечно сложные конструкции. Также с учетом того, что полностью нетерминированная синхронная модель никогда не может быть достигнута в нетривиальной распределенной системе. Это происходит потому, что в любой нетривиальной динамической многовариантной системе с переменным начальным состоянием существует бесконечное число возможных состояний, действий и результатов в любой момент времени. Теория хаоса
Рассмотрим сложность конструкции для обнаружения отброшенных пакетов TCP из-за ошибок переполнения буфера в маршрутизаторе на этапе 21. И сложность обнаружения той же ошибки переполнения буфера, отбрасывающего сигнал обнаружения из самой конструкции.