Определение волнового алгоритма
• Волновым алгоритмом называется распределенный алгоритм, который удовлетворяет следующим трем требованиям:
– Завершение. Каждое вычисление C конечно: ∀C: |C| < ∞.
– Решение. Каждое вычисление C содержит хотя бы одно событие e решения: ∀C : ∃e ∈ C : e является событием решения decide.
– Зависимость. В любом вычислении C всякому событию решения предшествует в причинно-следственном отношении хотя бы одно событие fв каждом из процессов: ∀C : ∀e ∈ C : (e— событие решения decide ⇒ ∀q ∈ C : ∃f ∈ Cq : f ≤ e).
• Вычисление волнового алгоритма называется волной. В волновых алгоритмах есть два вида процессов: инициаторы (стартовые процессы) и неинициаторы (последователи).
Аспекты, в которых волновые алгоритмы отличаются друг от друга
• Централизация
• Топология
• Первоначальные сведения
• Число решений
• Сложность
Основные свойства
• Структурные свойства волн
– Каждому событию в вычислении предшествует некоторое событие в инициаторе.
– Волна с одним инициатором определяет остовное дерево сети, если для каждого неинициатора выделить канал, по которому он получает первое сообщение.
– В качестве события f, упомянутого в третьем пункте определения, можно выбрать событие отправления сообщения для всех процессов q за исключением того процесса, в котором происходит событие decide.
• Нижние оценки сложности
– Для числа сообщений, которыми обмениваются процессы при прохождении волны нижняя оценка N-1. Если событие решения происходит только в инициаторе, то оценка увеличивается до N сообщений.
Многие задачи в распределенных системах решаются путем пересылки сообщений согласно некоторой схемы, которая гарантирует участие всех сайтов. Эта схема зависит от топологических особенностей системы, т.е. от вида графов, представляющих связи между узлами – сайтами.
Распределенные алгоритмы обычно допускают большой набор возможных трасс вычислений благодаря недетерминированности как в процессах, так и в подсистеме передачи. Трасса вычисления – это набор событий, частично упорядоченных отношением причинно-следственного предшествования. Волновой алгоритм обменивается конечным числом сообщений со всеми сайтами и затем на основе этого выполняет специальную процедуру return(OK).
Волновой алгоритм - это распределенный алгоритм, который удовлетворяет следующим трем требованиям:
1. Конечность. Каждое вычисление содержит конечное число событий.
2. Успешное завершение. Каждое вычисление содержит хотя бы одно событие return(OK).
3. Зависимость. В каждом вычислении каждому событию вызова процедуры return(OK) предшествует (в смысле причинно-следственной связи) какое-либо событие на каждом сайте.
Выполнение волнового алгоритма называется волной. Кроме того, в выполнении алгоритма различаются сайты инициаторы и сайты не-инициаторы. Сайт является инициатором, если он начинает выполнение своего локального алгоритма самопроизвольно, т.е. при выполнении некоторого условия, внутреннего по отношению к процессу. Не-инициатор включается в алгоритм только когда прибывает сообщение и вызывает выполнение локального алгоритма сайта. Начальное событие инициатора – внутреннее событиеили событие посылки сообщения, начальное событие не-инициатора – событие получения сообщения.
• Волновым алгоритмом называется распределенный алгоритм, который удовлетворяет следующим трем требованиям:
– Завершение. Каждое вычисление C конечно: ∀C: |C| < ∞.
– Решение. Каждое вычисление C содержит хотя бы одно событие e решения: ∀C : ∃e ∈ C : e является событием решения decide.
– Зависимость. В любом вычислении C всякому событию решения предшествует в причинно-следственном отношении хотя бы одно событие fв каждом из процессов: ∀C : ∀e ∈ C : (e— событие решения decide ⇒ ∀q ∈ C : ∃f ∈ Cq : f ≤ e).
• Вычисление волнового алгоритма называется волной. В волновых алгоритмах есть два вида процессов: инициаторы (стартовые процессы) и неинициаторы (последователи).
Аспекты, в которых волновые алгоритмы отличаются друг от друга
• Централизация
• Топология
• Первоначальные сведения
• Число решений
• Сложность
Основные свойства
• Структурные свойства волн
– Каждому событию в вычислении предшествует некоторое событие в инициаторе.
– Волна с одним инициатором определяет остовное дерево сети, если для каждого неинициатора выделить канал, по которому он получает первое сообщение.
– В качестве события f, упомянутого в третьем пункте определения, можно выбрать событие отправления сообщения для всех процессов q за исключением того процесса, в котором происходит событие decide.
• Нижние оценки сложности
– Для числа сообщений, которыми обмениваются процессы при прохождении волны нижняя оценка N-1. Если событие решения происходит только в инициаторе, то оценка увеличивается до N сообщений.
Многие задачи в распределенных системах решаются путем пересылки сообщений согласно некоторой схемы, которая гарантирует участие всех сайтов. Эта схема зависит от топологических особенностей системы, т.е. от вида графов, представляющих связи между узлами – сайтами.
Распределенные алгоритмы обычно допускают большой набор возможных трасс вычислений благодаря недетерминированности как в процессах, так и в подсистеме передачи. Трасса вычисления – это набор событий, частично упорядоченных отношением причинно-следственного предшествования. Волновой алгоритм обменивается конечным числом сообщений со всеми сайтами и затем на основе этого выполняет специальную процедуру return(OK).
Волновой алгоритм - это распределенный алгоритм, который удовлетворяет следующим трем требованиям:
1. Конечность. Каждое вычисление содержит конечное число событий.
2. Успешное завершение. Каждое вычисление содержит хотя бы одно событие return(OK).
3. Зависимость. В каждом вычислении каждому событию вызова процедуры return(OK) предшествует (в смысле причинно-следственной связи) какое-либо событие на каждом сайте.
Выполнение волнового алгоритма называется волной. Кроме того, в выполнении алгоритма различаются сайты инициаторы и сайты не-инициаторы. Сайт является инициатором, если он начинает выполнение своего локального алгоритма самопроизвольно, т.е. при выполнении некоторого условия, внутреннего по отношению к процессу. Не-инициатор включается в алгоритм только когда прибывает сообщение и вызывает выполнение локального алгоритма сайта. Начальное событие инициатора – внутреннее событиеили событие посылки сообщения, начальное событие не-инициатора – событие получения сообщения.
Показать текст полностью
