292
правки
Изменения
Нет описания правки
Алгоритм Лампорта-Шостака-Пиза (1982) решает [[Проблема византийских генералов|проблему византийских генералов]]: если имеется $N$ процессов, среди которых не более $f$ византийских, причём $3f < N$, то они могут прийти к консенсусу за конечное время, используя надёжные каналы связи.
== N=4, f=1 с лекции ==В первой фазе все процессы шлют своё предложение всем остальным, во второй — пересылают все полученную информацию всем остальным. У каждого невизантийского процесса появляется матрица информации: кто кому что сказал.Рассмотрим пример такой матрицы (процесс не знает, какой процесс византийский, мы пометили для демонстрации): [[Файл:distributed-byzantine-4-1.png|600px]] Диагональ вычёркиваем, нам эту информацию и так дали на первой фазе и ей нельзя верить в любом случае (например, так мы вычёркиваем $t_7$, что важно для доказательства ниже). В столбце византийского процесса находится что угодно, потому что он мог нам сказать что угодно (то есть $t_4$, $t_5$ и $t_6$ могут быть разные у всех процессов).В строчке византийского процесса тоже находится что угодно, но одинаковое для всех процессов, потому чтосодержимое этой строчки нам гарантированно рассказывают честные процессы (т.е. $t_1$, $t_2$ и $t_3$ одинаковые для всех процессов).Так что большинство в строчке византийского процесса ($t$) непонятное, но одно для всех честных процессов. А в строчках нормальных процессов находятся константы, за исключением одного столбца от византийского процесса.Таким образом, большинство в каждой строчке (кроме одной византийской) — это то, что соответствующий процесс реально рассылал ($x$, $y$, $z$). Следовательно, теперь у всех нормальных процессов множество из большинств по строкам одинаковое.Можно применять детерминированную функцию для выбора консенсуса.То есть византийский процесс не может помешать достигнуть консенсуса, но иногда может его изменить. == Идея общего случая с $f>1$ ==Надо сделать ещё несколько стадий. На первой рассылаем значения, на второй — матрицы, на третьей — кубики (мне прислали такую матрицу), и так далее.На экзамене подробнее не требуется. Впрочем, описание в Garg (секция 15.4.2, страница 244) требует $N > 4f$, а не $N > 3f$. == Общий случай из старых конспектов ==Считаем, что у процессов есть номера. Процесс 1 - "генерал" - рассылает всем предложение - 0 или 1. И после этого молчит(принимает своё предложение).
При f=0 все остальные ("лейтенанты") просто принимают предложение.
