distributed-consensus-error

Distributed Consensus Error

После изучения материалов лекций про Распределенный Консенсус в голове у студента всё смешалось. Он усвоил, что если среди 4-х процессов 1 процесс сбойный, то оставшиеся три могут прийти даже к Византийскому консенсусу! А так как Византийская ошибка самая сильная в иерархии ошибок (то есть может эмулировать любую другую), то и любая другая ошибка 4-м процессам точно по зубам. Например, самая простая ошибка — отказ одного процесса. Базовый алгоритм консенсуса при отказе одного процесса требует выполнения 2-х фаз. Но как понять что фаза закончилась, если один из процессов может оказать? К счастью, в алгоритме Бен-Ора обнаружился подходящий трюк. Если известно, что могут оказать не более чем nFails процессов, то в каждой фазе надо просто ждать nProcesses - nFails - 1 сообщений от других процессов и переходить к следующий фазе!

В итоге у студента получился следующий алгоритм для консенсуса 4-х процессов:

• Каждый процесс поддерживает множество proposals — множество известных этому процессу предложений. В начале каждый процесс предлагает свой processId.
• Алгоритм выполняет 2 фазы.
• В каждой фазе процесс сначала шлет сообщение остальным 3-м процессам, содержащее:
  • номер фазы;
  • размер своего множества proposal;
  • все элементы множества proposals.
• При получении такого сообщения процесс добавляет все полученные элементы в свое множество proposals.
  • Если вдруг пришло сообщение из старой фазы, то оно игнорируется.
  • Если вдруг пришло сообщение из будущей фазы, то оно откладывается в отдельную очередь, чтобы обработать позже, в соответствующей фазе.
• Фаза заканчивается, когда процесс получил 2 ответа от других процессов в этой фазе (один сбойный — его не ждем).
• После окончаний 2-й фазы процесс приходит к решению взяв минимальное значение из всех известных ему proposals.

Но ведь теорема FLP утверждает, что такой алгоритм сделать невозможно! Где подвох?

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

Задача

Вам дана реализация описанного выше алгоритма консенсуса в файле ProcessNaiveConsensus.kt. Эта реализация написана с использованием сопрограмм (корутин) в Котлине, что позволило сделать её максимально похожей на описанный в тексте алгоритм, без использования многопоточности и без необходимости ручного преобразования кода в машину состояний, реагирующую на приходящее сообщение. Вместо реализации функции onMessage, в нем реализована функция suspend fun run(), которая выполняет алгоритм, засыпая для ожидания следующего сообщения с помощью вызова suspend fun nextMessage():

// Repeat the protocol for nPhases
for (phase in 1..nPhases) {
    // Broadcast proposals
    for (i in 1..env.nProcesses) {
        if (i != env.processId) {
            env.send(i) {
                writeInt(phase) // phase number goes first
                writeInt(proposals.size)
                proposals.forEach { writeInt(it) }
            }
        }
    }
    // Wait for nProcesses - nFails - 1 answers from this phase
    var remaining = env.nProcesses - nFails - 1
    while (remaining > 0) {
        // take a message for this phase from the queue
        val message = queue[phase]?.removeFirstOrNull() ?:
            nextMessage().message // or wait until a message is received
        // parse message
        message.parse {
            val messagePhase = readInt()
            if (messagePhase < phase) { // old phase -- ignore message
                return@parse
            }
            if (messagePhase > phase) { // next phase -- queue
                queue.getOrPut(messagePhase) { ArrayDeque() }.add(message)
                return@parse
            }
            // process the message if it is for this phase
            val nProposals = readInt()
            repeat(nProposals) { proposals += readInt() }
            remaining--
        }
    }
}
// Done all phases -- decide on the minimal proposed value
env.decide(proposals.min()!!)

В файле src/Visualise.kt находится интерактивная программа визуализации алгоритмов. Её можно запустить из IDEA используя функцию main либо из командной строки:

gradlew run

Для запуска рекомендуется использовать JDK версии 11, особенно на Windows машинах с большим DPI экрана.

Ваша задача заключается в том, чтобы выбирая порядок доставки сообщений создать ситуацию, при которой разные процессы придут к решению на разных значениях, то есть хотя бы два процесса остановятся с разным решением.

Работа с визуализатором

В первой строке окна "Visualisation" находятся следующие элементы управления:

• "Name" — здесь нужно указать свое имя и фамилию.
• "Impl" — здесь уже выбран алгоритм ProcessNaiveConsensus.
• "Restart" — используйте для запуска алгоритма с начала.
• "Save" — нажмите для сохранения решения.

Визуализатор имитирует работу 4-х процессов, пронумерованных начиная с 1. Вертикальные линии изображают время в процессе. В верхней части вертикальных линий указан номер процесса и текущее содержимое множества proposals в алгоритме.

Время идет сверху-в-низ. Обратите внимание, что на лекциях мы изображали время слева-на-право. На линиях времени обозначаются события, происходящие в процессах:

• Черная окружность — процесс хочет послать сообщение. При нажатии мышкой на неё происходит доставка сообщения и внутри окружности появляется черный круг меньшего размера.
• Черный круг — процесс принял и обработал сообщение.
• Горизонтальная черточка — процесс принял решение.

Нажимая мышкой на черные окружности вы выбираете порядок доставки сообщений.

Вам нужно добиться того, чтобы как минимум два процесса пришли к различным решениям.
После того, как вам удастся получить такое исполнение, нажмите кнопку "Save". Не забудьте перед этим указать свое имя и фамилию в поле "Name".

Решение будет записано в файл solution.txt, который вам надо добавить в репозиторий и закоммитить:

git add solution.txt
git commit -m "Solution"
git push origin master

Тестирование

Тестирование решения происходит путем запуска теста SolutionTest. Из командной строки: gradlew test.

Тест читает файл "solution.txt", проверяет его корректность и выполнение задания.

Формат сдачи

Выполняйте задание в этом репозитории. Решение должно быть в файле solution.txt.

Инструкции по сдаче заданий находятся в этом документе.