Лекционные материалы (1162669), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

Связь осуществляется по телефону и является надежной, но изn генералов m являются предателями. Предатели активно пытаются воспрепятствоватьсогласию лояльных генералов.Согласие в данном случае заключается в следующем. Каждый генерал знает, сколько воиновнаходится под его командой.

Ставится цель, чтобы все лояльные генералы узналичисленности всех лояльных армий, т.е. каждый из них получил один и тот же вектор длины n,в котором i-ый элемент либо содержит численность i-ой армии (если ее командир лоялен)либо не определен (если командир предатель).Соответствующий рекурсивный алгоритм был предложен в 1982 г. (Lamport).Проиллюстрируем его для случая n=4 и m=1. В этом случае алгоритм осуществляется в 4шага.1 шаг. Каждый генерал посылает всем остальным сообщение, в котором указываетчисленность своей армии. Лояльные генералы указывают истинное количество, а предателимогут указывать различные числа в разных сообщениях.

Генерал-1 указал 1 (одна тысячавоинов), генерал-2 указал 2, генерал-3 указал трем остальным генералам соответственно x,y,z,а генерал-4 указал 4.502-ой шаг. Каждый формирует свой вектор из имеющейся информации.Получается:vect1 (1,2,x,4)vect2 (1,2,y,4)vect3 (1,2,3,4)vect4 (1,2,z,4)3-ий шаг. Каждый посылает свой вектор всем остальным (генерал-3 посылает опятьпроизвольные значения).Генералы получают следующие вектора:g1g2g3g4(1,2,y,4)(1,2,x,4)(1,2,x,4)(1,2,x,4)(a,b,c,d)(e,f,g,h)(1,2,y,4)(1,2,y,4)(1,2,z.4)(1,2,z.4)(1,2,z.4)(i,j,k.l)4-ый шаг. Каждый генерал проверяет каждый элемент во всех полученных векторах. Есликакое-то значение совпадает по меньшей мере в двух векторах, то оно помещается врезультирующий вектор, иначе соответствующий элемент результирующего векторапомечается «неизвестен».Все лояльные генералы получают один вектор (1,2,»неизвестен»,4) - согласие достигнуто.Если рассмотреть случай n=3 и m=1, то согласие не будет достигнуто.Lamport доказал, что в системе с m неверно работающими процессорами можно достичьсогласия только при наличии 2m+1 верно работающих процессоров (более 2/3).Другие авторы доказали, что в распределенной системе с асинхронными процессорами инеограниченными коммуникационными задержками согласие невозможно достичь даже приодном неработающем процессоре (даже если он не подает признаков жизни).Применение алгоритма - надежная синхронизация часов.Алгоритм надежных неделимых широковещательных рассылок сообщений.Алгоритм выполняется в две фазы и предполагает наличие в каждом процессоре очередей длязапоминания поступающих сообщений.

В качестве уникального идентификатора сообщенияиспользуется его начальный приоритет - логическое время отправления, значение которого наразных процессорах различно.1-ая фаза.Процесс-отправитель посылает сообщение группе процессов (список их идентификаторовсодержится в сообщении).При получении этого сообщения процессы:Приписывают сообщению приоритет, помечают сообщение как «недоставленное» ибуферизуют его. В качестве приоритета используется временная метка (текущеелогическое время).Информируют отправителя о приписанном сообщению приоритете.512-ая фаза.При получении ответов от всех адресатов, отправитель:Выбирает из всех приписанных сообщению приоритетов максимальный и устанавливаетего в качестве окончательного приоритета сообщения.Рассылает всем адресатам этот приоритет.Получив окончательный приоритет, получатель:a) Приписывает сообщению этот приоритет.b) Помечает сообщение как «доставленное».c) Упорядочивает все буферизованные сообщения по возрастанию их приписанныхприоритетов.d) Если первое сообщение в очереди отмечено как «доставленное», то оно будетобрабатываться как окончательно полученное.Если получатель обнаружит, что он имеет сообщение с пометкой «недоставленное»,отправитель которого сломался, то он для завершения выполнения протокола осуществляетследующие два шага в качестве координатора.1.

Опрашивает всех получателей о статусе этого сообщения.Получатель может ответить одним из трех способов:Сообщение отмечено как «недоставленное» и ему приписан такой-то приоритет.Сообщение отмечено как «доставленное» и имеет такой-то окончательный приоритет.Он не получал это сообщение.2. Получив все ответы координатор выполняет следующие действия:Если сообщение у какого-то получателя помечено как «доставленное», то егоокончательный приоритет рассылается всем.

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

Характеристики

Список файлов лекций