Интернет магазин китайских планшетных компьютеров

Компьютеры - Задача византийских генералов

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

Определение

N «синих» генералов возглавляют армии в горах и готовятся атаковать «зелёных» в долине. Для связи атакующие используют надёжную связь. Однако, из n генералов m являются предателями и активно пытаются воспрепятствовать согласию лояльных генералов. Согласие состоит в том, чтобы все лояльные генералы узнали о численности всех лояльных армий.

Формализация

Каждый из генералов должен получить один и тот же вектор длины n, в котором i-й элемент либо содержит численность i-й армии либо не определён.

Алгоритм решения

Соответствующий рекурсивный алгоритм был предложен в 1982 г. Лесли Лампортом.

Проиллюстрируем его для случая n=4 и m=1. В этом случае алгоритм осуществляется в 4 шага.

1-ый шаг. Каждый генерал посылает всем остальным сообщение, в котором указывает численность своей армии. Лояльные генералы указывают истинное количество, а предатели могут указывать различные числа в разных сообщениях. Генерал-1 указал число 1, генерал-2 указал число 2, генерал-3 указал трем остальным генералам соответственно x, y, z, а генерал-4 указал 4.

2-ой шаг. Каждый формирует свой вектор из имеющейся информации.

Получается:

vect1

vect2

vect3

vect4

3-ий шаг. Каждый посылает свой вектор всем остальным.

Генералы получают следующие вектора:

4-ый шаг. Каждый генерал проверяет каждый элемент во всех полученных векторах. Если какое-то значение совпадает по меньшей мере в двух векторах, то оно помещается в результирующий вектор, иначе соответствующий элемент результирующего вектора помечается неизвестен.

Все лояльные генералы получают один вектор — согласие достигнуто.