Теормин, страница 3

Допущения для алгоритма Netchange:

1. Каждый узел осведомлен о размере всей сети (N).

2. В каналах поддерживается очередность сообщений.

3. Узлы получают уведомления о возникновении неисправностей и восстановлении работоспособности примыкающих к ним каналов. (алгоритм может быть легко расширен для случая, если у каналов есть вес, и эти веса могут меняться (нужны лишь уведомления))

4. Стоимость пути равна количеству каналов в этом пути

Требования к алгоритму:

1. Если топология сети после конечного числа изменений остается далее неизменной, то алгоритм завершает работу после конечного числа шагов.

2. Теорема 1

Когда алгоритм завершает работу, таблицы Nb_u[v] удовлетворяют следующим условиям:

• если v = u , то Nb_u[v] = local

• если существует путь из вершины u в вершину v ≠ u, то Nb_u[v] = w, где w — это первая вершина-сосед узла u, который следует за u в кратчайшем пути из u в v

• если пути из вершины u в вершину v нет, то Nb_u[v] = udef

<описание алгоритма Netchange> (начиная со слайда 14)

В постой модели алгоритма мы считаем, что fail и repair обрабатываются одновременно на обоих узлах от линка (но это не обязательно – слайд 74), и ещё мы просто ищем самый короткий путь, без учёта веса (это не влияет на общую организацию алгоритма) (слайд 75)

<доказательство инвариантов>

Доказательство завершаемости алгоритма Netchange происходит за счёт введения частично-упорядоченного множества (фундированное множество).

Теорема 2.

Если, начиная с какого-то момента топология сети остается неизменной, то спустя конечное число шагов алгоритм достигает стабильной конфигурации.

Другие виды маршрутизации:

1. Схема древесной разметки - Этот метод помечает вершины целыми числами от 0 до N-1 так, чтобы для каждого канала связи множество вершин-адресатов, сообщение с которыми осуществляется через этот канал, представляло собой интервал.

Достоинства

• для задания одного циклического интервала можно обойтись 2 log N битами, указывая только границы интервала.

Недостатки:

• Каналы, не принадлежащие дереву T, не используются, а это означает, что ресурсы сети расходуются неэкономно.

• Весь трафик сосредоточен в дереве, а это приводит к перегрузкам в сети.

• Всякая неисправность в одном канале дерева T приводит к разрыву сети.

1. Префиксная маршрутизация - в префиксной маршрутизации пометками вершин и каналов служат строки. Чтобы выбрать канал, по которому нужно продвигать пакет, алгоритм рассматривает все пометки каналов, являющиеся префиксом адреса вершины назначения. Выбирается наиболее длинная из таких пометок, и продвижение сообщения проводится по соответствующему каналу.

2. Иерархическая маршрутизация - иерархический метод маршрутизации предполагает разбиение сети на кластеры. (очень схоже с современным интернетом, в котором есть понятие «шлюза»)

1. Волновые алгоритмы: определения, основные свойства, область применения. Древесный алгоритм. Алгоритм эха.

Зачем нужны волновые алгоритмы:

При проектировании распределенных алгоритмов для разных приложений некоторые общие проблемы, которые нужно уметь решать, как промежуточные задачи. К ним относятся:

• широковещательное распространение информация (например, сообщения о начале или завершении вычисления), (PIF)

• установление глобальной синхронизации между процессами, (SYN)

• запуск выполнения некоторого действия в каждом процессе,

• вычисление функции при условии, что каждый из процессов содержит только часть входных данных, (INF)

• …

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

Допущения для волновых алгоритмов

Соглашение о сетевой модели:

• имеет фиксированную топологию (никаких изменений топологии не происходит);

• является неориентированной (по каждому каналу сообщения могут передаваться в обоих направлениях);

• является связной (между любыми двумя процессами пролегает путь),

• является асинхронной,

• не имеет доступа к показаниям вещественных часов глобального времени.

Предполагается, что существуют внутренние события специального типа, которые называются событиями решения, такие события просто представлены оператором decide – «событие решения».

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

1. он конечен,

2. каждое вычисление содержит хотя бы одно событие decide,

3. В любом вычислении всякому событию решения предшествует в причинно-следственном отношении хотя бы одно событие в каждом из процессов.

При выполнении проводится различие между процессами инициаторами и неинициаторами.

Параметры волновых алгоритмов:

1. Централизация

2. Топология

3. Первоначальные сведения

4. Число решений

5. Сложность

(формулировки утверждений, перефразированные на человеческий язык)

Утверждение 1

Для каждого события решения есть инициатор и его событие, которые в любом выполнении происходят до этого события.

Утверждение 2

Если отслеживать граф передачи первых событий, то это остовное дерево

Утверждение 3

Для любого события решения в каждом другом процессе было событие до него (в любом выполнении), являющееся отправкой сообщения.

Утверждение 4

Пусть C — такая волна с одним инициатором p в распределенной системе, состоящей из N процессов, что в p происходит событие решения decide. Тогда в вычислении C происходит обмен по крайней мере N сообщениями.

Утверждение 5

Пусть A — волновой алгоритм для произвольной сети, в котором не используются первоначальные сведения об отличительных признаках соседей. Тогда A в каждом вычислении проводит не менее |Е| обменов сообщениями.

Волновые алгоритмы необходимы для широковещательного распространения информации с подтверждением о завершении выполнения (широковещательной связи Propagation of Information with Feedback, PIF).

Пусть имеется подмножество процессов, обладающих некоторым сообщением M. Нужно, чтобы все процессы приняли M. Некоторые выделенные процессы должны быть уведомлены о завершении широковещательной связи; это означает, что в них должно быть выработано специальное событие notify с тем условием, что событие notify произойдет только в том случае, когда все процессы уже получат сообщение M.

Утверждение 6.

Каждый PIF-алгоритм — это волновой алгоритм.

Утверждение 7.

Каждый волновой алгоритм может быть использован в качестве PIF-алгоритма.

Волновые алгоритмы необходимы для глобальной синхронизации (Synchronization, SYN) между процессами. Требование синхронизации таковы: в каждом процессе q должно быть выполнено событие a_q, и в некоторых процессах событие b_p должно быть выполнено так, чтобы выполнение a_q произошло по времени ранее, нежели выполнение любого из событий b_p.

В SYN-алгоритме события b_p рассматриваются как события decide.

Утверждение 8.

Каждый волновой алгоритм может быть использован в качестве SYN-алгоритма.

Утверждение 9.

Каждый SYN-алгоритм может быть использован в качестве волнового алгоритма.

Волновые алгоритмы необходимы для вычисления некоторых функций, зависящих от входных данных каждого процесса. Примером такими функциями могут служить функции точной нижней грани по всем входам.

Примеры волновых алгоритмов (подробное и формальное описание на слайдах):

1. Кольцевой алгоритм

2. Древесный алгоритм

3. Алгоритм эха

Утверждения: эти примеры алгоритмов являются волновыми алгоритмами.

1. Волновые алгоритмы. Фазовый алгоритм. Алгоритм Финна. Распределенные алгоритмы обхода: основные свойства. Алгоритм обхода Тарри. Распределенный обход в глубину. Алгоритмы Авербаха и Сидона.

Фазовый алгоритм является децентрализованным алгоритмом, пригодным для сетей с произвольной топологией.

Ограничения:

1. Его можно использовать в качестве волнового алгоритма для ориентированных сетей.

2. В этом алгоритме требуется, чтобы все процессы располагали сведениями о диаметре сети D. Алгоритм будет оставаться корректным (хотя и менее эффективным), если все процессы будут использовать вместо D константу D1, превышающую диаметр сети.

3. Процессы могут не уметь друг друга идентифицировать

Идея фазового алгоритма:

В фазовом алгоритме всякий процесс отправляет в точности D сообщений каждому соседу на выходе.

При этом (i + 1) -е сообщение отправляется каждому соседу на выходе только после того, как были получены i сообщений от каждого соседа на входе.

Как только от каждого соседа будет получено в точности D сообщений, процесс завершает алгоритм и принимает decision.

Лемма 7.1

Суть: даже если канал не является очередью (при волновом алгоритме), то соотношение взаимозависимости между событиями сохраняется.

Теорема о фазовом алгоритме.

Фазовый алгоритм – это волновой алгоритм.

Алгоритм Финна

Алгоритм Финна — это еще один волновой алгоритм, который можно использовать для произвольных ориентированных сетей.

Ограничения:

1. Процессы должны однозначно друг друга идентифицировать.

2. Не нужно знать диаметра сети

3. В сообщениях процессы обмениваются отличительными признаками, и это приводит к тому, что битовая сложность алгоритма становится достаточно большой.

Основная идея.

Процесс p формирует два множества отличительных признаков Inc_p и NInc_p

• Inc_p — это множество таких процессов q, что некоторое событие в q предшествует (по отношению <=) самому последнему событию, случившемуся в p.

• NInc_p — множество таких процессов q, что у каждого соседа г процесса q какое-нибудь событие в r предшествует самому последнему событию, случившемуся в p.

Множества Inc_p и NInc_p формируются так:

1. Вначале Inc_p = {p} и NInc_p = Ø.

2. Процесс p отправляет сообщения, содержащие Inc_p и NInc_p всякий раз, когда одно из этих множеств расширяется.

3. Когда p получает сообщение с множествами Inc и NInc полученные отличительные признаки добавляются к мнoжecтвaм Inc_p и NInc_p

4. Если p получил сообщения от всех своих соседей на входе, то отличительный признак p вставляется в NInc_p

5. Если Inc_p = NInc_p, то p принимает решение.

Это означает, что каков бы ни был процесс q , если некоторое событие в q предшествует d_p, то у всякого соседа r процесса q также произошло какое-нибудь событие, предшествующее d_p. Отсюда следует, что для нашего алгоритма требование зависимости соблюдено.

Теорема об алгоритме Финна:

Алгоритм Финна — это волновой алгоритм.

Особый интерес представляют централизованные волновые алгоритмы, в которых все события линейно упорядочены по отношению причинно-следственной зависимости, и решение принимает инициатор. Волновые алгоритмы такого рода называются алгоритмами обхода.

Алгоритмом обхода называется алгоритм, обладающий следующими тремя свойствами.

1. В каждом вычислении единственный инициатор запускает алгоритм, отправляя одно-единственное сообщение.

2. Всякий процесс после получения сообщения либо отправляет ровно одно сообщение, либо принимает решение.

3. Алгоритм завершает работу в инициаторе, и к тому моменту, когда это происходит, каждому процессу хотя бы один раз удалось отправить сообщение.

Алгоритм Тарри

Алгоритм обхода произвольных связных сетей был предложен Тарри в 1895. Этот алгоритм определяется двумя следующими правилами.

R1. Процесс не передает маркер по одному и тому же каналу дважды.

R2. He-инициатор передает маркер своей родительской вершине (соседу, от которого он впервые получил маркер) только в том случае, когда его невозможно передать по другим каналам согласно правилу R1.

Теорема об алгоритме Тарри: Алгоритм Тарри — это алгоритм обхода

Стягивающее ребро — это ребро, не принадлежащее остовному дереву.

Корневое остовное дерево T тети G называется деревом поиска в глубину, если для каждого стягивающего ребра pq выполняется соотношение q ∈ T [p] V q ∈ A[p] – т.е. либо q – вершина поддерева вершины p, либо q – вершина предшественник вершины p.