В распределенных вычислениях проблема консенсуса, по-видимому, является одной из центральных тем, которая привлекла интенсивные исследования. В частности, статья «Невозможность распределенного консенсуса с одним ошибочным процессом» была удостоена награды PODC за выдающуюся работу в 2001 году .
Так почему проблема консенсуса так важна? Чего мы можем достичь с консенсусом как в теории, так и на практике?
Любые ссылки или экспозиции будут действительно полезны.
Упомянутый вами документ важен по двум причинам:
Приложения
Одним из важных применений проблемы консенсуса является избрание координатора или лидера в отказоустойчивой среде для инициирования каких-либо глобальных действий. Консенсусный алгоритм позволяет вам делать это на лету, не исправляя заранее «суперузел» (который привел бы к единственной точке отказа).
Другое приложение поддерживает согласованность в распределенной сети: предположим, что у вас есть разные сенсорные узлы, контролирующие одну и ту же среду. В случае, если некоторые из этих сенсорных узлов выходят из строя (или даже начинают отправлять поврежденные данные из-за аппаратного сбоя), согласованный протокол обеспечивает устойчивость к таким сбоям.
(*) Выполнение распределенного алгоритма - это последовательность конфигураций. Конфигурация - это вектор локальных состояний процессов. Каждый процесс выполняет детерминированный конечный автомат. Любой правильный алгоритм консенсуса должен в конечном итоге достичь конфигурации, в которой каждый процесс определил (безвозвратно) одно и то же входное значение. Конфигурация составляет 1 - валентный если, независимо от того , что делает противник, все возможные расширения C приводят к значению решения от 1 . Аналогично мы можем определить 0 - валентность . Конфигурация C является двухвалентной, если оба решения достижимы из C(какой из двух достигнут, зависит от противника). Ясно, что ни один процесс не может быть решен в двухвалентной конфигурации , так как в противном случае мы получим противоречие с соглашением! Таким образом, если мы можем построить бесконечную последовательность таких двухвалентных конфигураций, мы показали, что в этой настройке нет консенсусного алгоритма.
Это показывает, что нет отказоустойчивого детерминированного алгоритма. Довольно сильный теоретический результат, который заставляет дизайнеров по-разному справляться с отказоустойчивостью, некоторые из которых - синхронизация и рандомизация.
Комментарий: По моему мнению, синхронизация - это дополнительное допущение системы, которое вряд ли можно найти в практических приложениях.
Для ссылок, проверьте ссылку в Википедии . Проверьте также этот блог для практических приложений
источник
Одна из причин, по которой проблемы консенсуса важны, заключается в том, что они очень просты и являются своего рода универсальными проблемами для распределенных вычислительных систем.
Если мы можем решить консенсус в асинхронной распределенной системе, мы можем использовать его для линеаризации действий над общими объектами и получения линеаризуемости для общих объектов.
Для простоты, сколько проблем вы можете придумать, какие из них проще, чем согласиться с ценностью?
Результат невозможности достижения консенсуса в (чистых) асинхронных распределенных системах говорит нам о том, что мы не можем решить проблемы, которые хотим решить в (чистых) асинхронных распределенных системах, без каких-либо дополнительных «вещей». Это приводит к асинхронным моделям, в которых мы можем решать консенсус, например, рандомизированные алгоритмы, детекторы ошибок, модели частичной синхронизации и т. Д.
Это также является причиной того, что на практике алгоритмы, которые решают консенсус, такие как Paxos Лампорта, Chubby от Google, Apache ZooKeeper и совсем недавно Raft, являются ядром распределенных систем, где мы часто хотим реплицировать состояние среди серверов.
источник
Я хотел бы только добавить, что характер вычислений все более распределяется по стеку: многие ЦП, многие процессы на машине, многие машины, подключенные к локальным сетям, многие локальные сети, подключенные к сетям.
Это делает проблему общего (распределенного / глобального) состояния первостепенной - каждый алгоритм принимает определенное состояние, и если вычисления должны выполняться более чем в одном месте, то это состояние также должно быть распределено.
Влиятельные статьи ( Paxos , и совсем недавно Raft ) в этой области были опубликованы после цитируемой вами статьи. Оба решают вопросы консенсуса при наличии некоторых неудач.
Византийских ошибок можно избежать в распределенных системах, используя несколько подходов.
Взгляните на статью в Википедии о византийской терпимости к ошибкам .
источник