Информация

Дата основания
Местоположение
Россия
Сайт
dodo.dev
Численность
101–200 человек
Дата регистрации

Блог на Хабре

Обновить

Кот Шрёдингера без коробки: проблема консенсуса в распределённых системах

Блог компании Dodo EngineeringАнализ и проектирование системАлгоритмыМатематикаРаспределённые системы
Рейтинг +43
Количество просмотров 17,7k Добавить в закладки 155 Читать комментарии 20
Комментарии 20
Интересно, но жаль нет хотя бы ссылок на практические реализации
Тоже читал статью и размышлял о zk.
В алгоритме не описаны права выбора лидера, если предыдущий пал.
Вы правы, в статье я рассмотрел только самый позитивный сценарий, основной идеей статьи было, скажем так, интро в проблему консенсуса в распределенных системах. Конечно, каждый из алгоритмов заслуживает отдельной подробной статьи и даже не одной.
А если интересна практическая реализация близкого Raft, то можно обратить внимание на etcd которая используется в kubernetes
Вы имеете в виду ссылки на репозитории с кодом практических имплементаций алгоритма или про использование большими компаниями?
Если второе, то я натыкался на несколько статей, например, блог MySQL High Availability и блог Apache Cassandra, правда там совсем старая статья, не знаю, что используется сейчас.
Было бы круто в такие статьи для наглядности анимации вкладывать. Ролик в конце с примерами такого голосования, например
Я пока еще не изучал PoS и не готов к обсуждению этого вопроса, но я учту ваши пожелания :)

Статья очень интересная, спасибо!


По этой теме есть еще супер-интересная книга Designing Data-Intensive Applications, Martin Kleppmann, советую :)


Автору еще раз спасибо.

Да, Мартин Клеппман у нас почти настольная книга. Спасибо за упоминание :)
Спасибо большое за статью! Для тех, кто хочет погрузиться в «математику» распределенных систем, можно еще порекомендовать классическую книгу Gerard Tel «Introduction to Distributed Algorithms».
Задача с генералами ломает мой мозг. Уже на 3-4 итерациях оба генерала знают время, и знают, что время известно им обоим. Но напасть не могут, так как не могут быть уверены, что второй генерал тоже нападет.
В этом и состоит красота данной задачи. У нее еще есть любопытные вариации:
1) Например, гонцы ходят двумя дорогами, южная и северная. Причем генерал А1 — посылает гонца всегда южной дорогой, а А2 — всегда северной. Оппонент выставляет стражу на одну из дорог и случайно может перехватить, а может и не перехватить одного гонца.
2) Те же условия, что и в (1), но оппонент кидает монетку в самом начале, выбирает направление и всегда пытается поймать только на этом направлении.
3) Те же условия, что и в (2), но оппонент гарантированно ловит гонца на выбранном направлении.
В каких из этих кейсов генералы могут договориться, а в каких нет?
Как я понял, нужно, что бы была гарантия 1 удачной доставки сообщения.
В 1 случаи, все так же не известно, доставлено сообщение или нет, потому задача сводится к классической.

В 2 случаи мы все так же не можем быть уверены, нам повезло или путь гарантировано безопасен.

В 3 случаи если генералы знают правила, то достаточно каждому выслать по гонцу с временем, и если пришел гонец то атаковать в то время которое принес гонец, а если нет, то в то время, которое генерал выслал.
Да, все так. Суть именно в гарантированном канале связи.
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.