Алгоритм византийских генералов

By Денис Чащин  

Описание задачи

При создании распределенных систем можно столкнуться с трудностью недоверия результату, полученному каким-то компьютером. Например вы не можете контролировать кто именно установил себе вашу программу и как ее поменял, либо компьютер может начать глючить. Рассмотрим задачу о византийских генералах, которая как раз моделирует такую ситуацию, и алгоритм ее решения.

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

Задача о командире и подчиненных

Для начала решим задачу о командире и подчиненных. Есть один командир и много подчиненных. Командир отдает приказ и необходимо сделать так, чтобы у всех подчиненных этот приказ был одинаков. При этом некоторые подчиненные либо командир могут быть предателями и передавать приказ разный для всех.

Считаем, что между командиром и подчиненными могут передаваться сообщения, удовлетворяющие следующим условиям:

  1. Каждое отправленное сообщение доставляется без изменений,
  2. Получатель знает кто отправил сообщение,
  3. Потеря сообщения может быть обнаружена.

В оригинале статьи на английском языке он называется «Oral Message algorithm«; не будем отступать от принятых сокращений и обозначим его OM(m),  где m — число предателей. Алгоритм построен на рекурсии по возможному числу предателей. Итак, что необходимо делать командиру:

Алгоритм OM(0):

  1. Командир отправляет остальным свое значение
  2. Каждый подчиненный использует значение, которое получил от командира, либо значение по умолчанию, если сообщение не пришло.

Алгоритм OM(m), m>0:

  1. Командир отправляет остальным свое значение
  2. Для каждого i положим v_i - значение которое подчиненный с номером i получил от командира, либо значение по умолчанию, если сообщение не дошло. Подчиненный i выступает в роли командира в алгоритме OM(m-1), отправляя значение v_i оставшимся n-2 подчиненным.
  3. Для каждого номера j \ne{}i записываем как v_j — значение, которое подчиненный i получил от подчиненного j на шаге 2(используя алгоритм от OM(m-1)), либо значение по умолчанию, если ничего получено не было. Подчиненный i использует наиболее часто встречающееся значение из (v_1,\cdots{},v_{n-1}), в качестве результата V. Если значения встречаются одинаково часто, то используется значение по умолчанию.

Решение задачи о византийских генералах

Теперь, зная как решить задачу о командире и подчиненных, легко решить задачу о генералах.

  1. Каждый генерал выступает в роли командира, считая остальных генералов своими подчиненными.
  2. В результате у каждого генерала собирается набор приказов остальных генералов (V_1,\cdots{},V_{n-1}). Из этого набора выбираем наиболее часто встречающееся значение и действуем в соостветствии с ним. Если значения встречаются одинаково часто, то как всегда используем значение по умолчанию.

Когда алгоритм не работает

Приведенный алгоритм будет работать только в том случае, когда общее число генералов n\ge{m-1}, где m-число предателей.  При таких условиях невозможно решить задачу, если предателей будет больше чем m. Доказательство этого факта приведено в статье «Византийские генералы. Доказательство невозможности«.


One Trackback

  1. [...] в статье «Алгоритм византийских генералов» алгоритм решения задачи о византийских генералах [...]

Post a Comment

Your email is never shared. Required fields are marked *

*
*