Это машинный перевод. Оригинал на английском здесь: Update 24 November, 2022
Продолжая наш прогресс в адаптации согласованных протоколов децентрализованных сетей для наших целей, в данном случае обрабатывая членство в секциях, на этой неделе Мостафа знакомит нас с ABBA и MVBA. ABBA — это протокол подбрасывания монеты для бинарного соглашения. Если раздел нуждается в другом взрослом, старшие могут выбрать один узел, чтобы предотвратить массовое присоединение, в то время как MVBA используется для выбора между конкурирующими предложениями, например, какие узлы должны быть старшими в следующей итерации раздела.
Общий прогресс
@roland усердно работал над новой утилитой TestNetwork, которая облегчит настройку среды для тестов узлов. Мы можем указать сборщику сгенерировать сеть с определенным SAP в префиксе, и он создаст функциональную и настраиваемую сеть со всеми заполненными пробелами. @oetyng сейчас рефакторинг, чтобы включить некоторые сквозные тесты, которые были был отключен после работы двунаправленного потока, который некоторое время зависал.
@chriso обновил нашу настройку AWS, и теперь мы просто проверяем, как лучше всего использовать это во время PR (чтобы получить больше скорости и надежности для определенных тестов).
@joshuef и @roland продолжают сокращать количество блокировок записи, которые мы берем на состояние узла. Это сообщения, которые отправляются между старшими и связывающимися с ними клиентами, чтобы убедиться, что у клиента есть актуальная информация о разделе, прежде чем он попытается сделать запрос. Эти блокировки записи — еще одно место, где мы можем заблокировать выполнение кода и замедлить работу узла. Они также являются ненужным усложнением и потенциальным источником ошибок. Теперь мы блокируем только сообщения AE, которые фактически обновляют нас (ранее это были все сообщения AE). Мы также больше не блокируем во время репликации данных или отслеживания сбоев. Таким образом, мы намного ближе к бережливому/нормальному состоянию «узла», которому требуется только доступ «на запись» для небольшого подмножества задач, связанных с сетью.
В дополнение к этой работе @bochaco также работает над обменом сообщениями AE и удалением избыточной логики в клиентской обработке AE.
АББА и МВБА
Протокол ABBA
ABBA или асинхронное бинарное византийское соглашение — это способ решения проблемы консенсуса в асинхронных сетях. В частности, ABBA можно использовать для группового решения вопроса «да/нет».
В этом протоколе каждая сторона начинает с широковещательной передачи своих предпочтений (да/нет). Если для инициализированных значений нет большинства, стороны запускают пороговую схему подбрасывания монеты, которая дает случайный результат, с которым все могут согласиться. ABBA — недетерминированный протокол, его выход — случайное число. Если мы воспроизведем входные события, мы можем получить другой результат.
Непротиворечивость обеспечивается VCBC. Как рассматривалось на прошлой неделе, VCBC — это широковещательный протокол, который пытается передать сообщение от узла в сеть, при этом все узлы соглашаются в сообщении, отправленном узлом. Протокол VCBC можно изменить, чтобы принимать только действительные и правильные предложения.
Мы используем VCBC, чтобы убедиться, что сообщения, передаваемые узлами, действительны. VCBC — это просто проверочная проверка. Таким образом, если старейшина транслирует предложение о том, что другой узел должен быть допущен в раздел, другие узлы могут убедиться, что старейшина не повреждена или неисправна, и к этому предложению следует отнестись серьезно.
После этого мы можем использовать раунды ABBA, чтобы прийти к соглашению через пороговую схему подписи, которая продолжается до тех пор, пока большинство старейшин не придут к консенсусу. ABBA всегда прекращает свое существование. Он всегда будет генерировать случайное двоичное значение, которое используется для принятия решения. Если у нас будет достаточно голосов, мы можем принять предложение.
Порядок старших имеет значение. Представьте, что старшие упорядочены так: [3,5,7,2,1]
и 3 не в сети. После VCBC у нас есть предложения [-, P5, P7, P2, P1]. Первое предложение — P5. Мы запускаем ABBA для P5. Мы знаем, что P5 действителен и он есть у всех старейшин (постоянно транслируется), поэтому это должно решиться через некоторое время.
Более слабое понятие достоверности
Мы берем эти ванильные алгоритмы и меняем их для наших целей. Поскольку VCBC уже проверил сообщения для нас, мы можем просто потребовать, чтобы честная сторона могла принимать решение только о значении, для которого у нее есть соответствующие данные проверки. В противном случае он будет отклонен.
Это позволяет нам упростить протокол ABBA.
Протокол MVBA
Протокол Византийского соглашения о множественных ценностях (MVBA) используется, когда имеется более одного предложения для достижения консенсуса. .
Мы можем использовать его, когда несколько старейшин уходят или несколько взрослых одновременно получают право на повышение, поэтому существует несколько возможных версий следующей итерации раздела.
В этом сценарии каждая сторона последовательно транслирует свои предложения через VCBC, и после получения достаточного количества предложений от честных сторон (действительных) протокол начинает выполнять бинарное соглашение (с использованием ABBA) для каждого предложения. Когда первое предложение получает dесли процесс завершается.
Проблема членства
Так что же все это пытается решить? Речь идет о повышении и понижении в должности старших. Этот процесс должен происходить с согласия подавляющего большинства честных старейшин, и мы хотим избежать полного порядка, так как это требует больших вычислительных ресурсов, а не так, как это делает природа. Нам также необходимо обрабатывать высокий уровень параллелизма (множество одновременных присоединяющихся/выходящих) без необходимости ждать заказа и иметь возможность обрабатывать или запрещать вилки.
Наш подход заключается в решении этой проблемы с использованием протокола MVBA. В этом сценарии каждый старейшина предлагает список старейшин, которые будут отвечать за раздел после изменения, и транслирует его другим старейшинам. Это продолжается до тех пор, пока большинство старейшин не получит достаточно предложений от других партий. После этого предложения голосуются с использованием протокола ABBA, так что один окончательный список старейшин выбирается случайным образом из предложенных.
Как вы знаете, мы внимательно изучаем эту область, и здесь есть компромиссы и выбор. Одно улучшение, которое мы можем сделать, — это использовать валидируемые предложения. Членство позволяет нам сделать это, тем самым сокращая время до соглашения. Еще одна область — параллелизм. В то время как строгий порядок не допускает параллелизма, есть варианты, это сложные варианты для рассмотрения, но, вероятно, снова гораздо меньше кода. В любом случае хорошо иметь варианты, но адаптация этих вариантов к конкретному случаю членства дает нам много вариантов, и мы можем затем с большей уверенностью рассмотреть компромиссы в этом случае использования.
Полезные ссылки
Не стесняйтесь отвечать ниже со ссылками на переводы этого обновления для разработчиков, и модераторы добавят их сюда.
Как проект с открытым исходным кодом, мы всегда ждем отзывов, комментариев и предложений сообщества - так что не стесняйтесь, присоединяйтесь и давайте вместе создадим безопасную сеть!