Теормин, страница 6
Описание файла
Документ из архива "Теормин", который расположен в категории "". Всё это находится в предмете "распределенные алгоритмы" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Онлайн просмотр документа "Теормин"
Текст 6 страницы из документа "Теормин"
Теорема 2
Алгоритм Ченди—Лэмпорта вычисляет значимое моментальное состояние системы.
Алгоритм Лаи-Янга
Допущения:
-
Каналы – не обязательно очередь
Идея алгоритма:
Каждое базовое сообщение снабжается пометкой, которая позволяет понять, является ли это сообщение предмоментальным или постмоментальным.
Для этого процесс p, отправляя сообщение по ходу вычисления C, добавляет к нему значение takenp . Так как содержание сообщений, относящихся к вычислению C, не играет здесь никакой роли, мы будем обозначать такие сообщения просто (mes, c), где c — это значение переменной, включенное в состав сообщения процессом-отправителем. Алгоритм построения моментального состояния проверяет поступающие сообщения и записывает моментальное локальное состояние, и в дальнейшем ко всем своим сообщения приписывает takenp. Следует считать, что принятое сообщение с поднятым флагом takenp – это постмоментальное сообщение и записывать его в конфигурацию не нужно.
Недостатки алгоритма:
-
В алгоритме Лаи-Янга нет обмена контрольными сообщениями, и он не может гарантировать того, что каждый процесс рано или поздно запишет свое состояние.
Теорема 3.
Алгоритм Лая—Янга вычисляет только значимые моментальные состояния системы.
Примеры устойчивых свойств, которые можно проверять на записанных конфигурациях:
-
Завершение вычисления
-
Наличие тупиков
-
Потеря маркеров
-
Наличие «мусора»
41