В.А. Крюков - Операционные системы распределенных вычислительных систем (1158860), страница 13

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

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

Есликакое-то значение совпадает по меньшей мере в двух векторах, то оно помещается врезультирующий вектор, иначе соответствующий элемент результирующего векторапомечается «неизвестен».Все лояльные генералы получают один вектор (1,2,»неизвестен»,4) - согласие достигнуто.Если рассмотреть случай n=3 и m=1, то согласие не будет достигнуто.Lamport доказал, что в системе с m неверно работающими процессорами можно достичьсогласия только при наличии 2m+1 верно работающих процессоров (более 2/3).Другие авторы доказали, что в распределенной системе с асинхронными процессорами инеограниченными коммуникационными задержками согласие невозможно достичь даже приодном неработающем процессоре (даже если он не подает признаков жизни).Применение алгоритма - надежная синхронизация часов.Алгоритм надежных неделимых широковещательных рассылок сообщений.Алгоритм выполняется в две фазы и предполагает наличие в каждом процессоре очередей длязапоминания поступающих сообщений.

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

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

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

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

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