Лекция 12. Волновые алгоритмы распространения информации

Многие задачи в распределенных системах решаются путем пересылки сообщений согласно некоторой схемы, которая гарантирует участие всех сайтов. Эта схема зависит от топологических особенностей системы, т.е. от вида графов, представляющих связи между узлами – сайтами.

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

Волновой алгоритм - это распределенный алгоритм, который удовлетворяет следующим трем требованиям:

1. Конечность. Каждое вычисление содержит конечное число событий.

2. Успешное завершение. Каждое вычисление содержит хотя бы одно событие return (OK).

3. Зависимость. В каждом вычислении каждому событию вызова процедуры return (OK) предшествует (в смысле причинно-следственной связи) какое-либо событие на каждом сайте.

Выполнение волнового алгоритма называется волной. Кроме того, в выполнении алгоритма различаются сайты инициаторы и сайты не-инициаторы. Сайт является инициатором, если он начинает выполнение своего локального алгоритма самопроизвольно, т.е. при выполнении некоторого условия, внутреннего по отношению к процессу. Не-инициатор включается в алгоритм только когда прибывает сообщение и вызывает выполнение локального алгоритма сайта. Начальное событие инициатора – внутреннее событие или событие посылки сообщения, начальное событие не-инициатора – событие получения сообщения.

Обычно при применении волновых алгоритмов в сообщение могут быть включены дополнительные переменные и другая информация. Многие приложения используют одновременное или последовательное распространение нескольких волн; в этом случае в сообщение должна быть включена информация о волне, которой оно принадлежит. Кроме того, процесс может хранить дополнительные переменные для управления волной, или волнами, в которых он в настоящее время активен.