После изучения материалов лекций про Распределенный Консенсус в голове у студента всё смешалось.
Он усвоил, что если среди 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.
Инструкции по сдаче заданий находятся в этом документе.