Алгоритм голосования

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

Существо алгоритма заключается в следующем.

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

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

Структура распределенной системы задается формулой

System:= compl(n)(Node[1..n](P[1..n – 1])).

Здесь у каждого сайта Node[i] имеется набор полюсов P[1..n – 1]. Эти полюсы связаны каналами передачи данных с соответствующими полюсами остальных сайтов. Таким образом, все каналы изолированы друг от друга. Маркер, передаваемый сайтом Node[i] через полюс P[j], попадет только в один канал и, соответственно, только на один сайт.

Рутина сайта – инициатора:

routine Initiator

Initial

integer counter;

counter:= 0;

out token;

Endi

event;

if message = token then

if (counter = n – 2) then return (OK)

else counter:= counter + 1 endi

Ende

endrout.

Здесь оператор out token означает передачу маркеров token всем смежным сайтам.

Рутины остальных сайтов имеют вид:

routine OtherNode

event;

case of polus

if message = token then out token through polus endi

Endc

Ende

endrout.

Здесь оператор case of – оператор распознавания входа. Идентификатор polus обозначает полюс, на который пришло сообщение, подобно тому, как само сообщение «скрывается» за идентификатором message. Оператор out token through polus возвращает маркер token через тот полюс сайта, на который пришел этот маркер, т.е. инициатору алгоритма.

Описанный распределенный алгоритм выполняется за время O (n).

Алгоритм «Эхо»

Алгоритм «Эхо» может работать для любой топологии распределенной системы. Как и предыдущий алгоритм, в нем имеется один инициатор.

Алгоритм использует метод прохода по графу, называемый «поиск (или просмотр графа) в ширину», описанный, в частности, в учебнике Л.Н.Королева, А.И.Микова «Информатика. Введение в компьютерные науки» для поиска множества R достижимых вершин из данной вершины start.

Метод состоит в том, чтобы продвигаться от начальной вершины по ширине всего фронта, включив сначала в множество R все вершины, смежные с вершиной start, затем смежные со смежными и так далее. В описанном ниже методе Expand(R) расширения множества R множество Out(R) – это множество всех вершин, смежных с вершинами из R, так сказать, достижимых за один шаг. В частности, может оказаться, что все они уже принадлежат R и тогда дальнейшее расширение невозможно. На этом процесс прекращается.

Expand(R):

begin

if Out(R) Ë R then

begin Out(R) Þ R;

Expand(R)

end

end;

Первый вызов – Expand(Out (start)); Предполагается, что Out(Æ) = Æ, Æ Í Æ.

В алгоритме «Эхо» инициатор посылает маркеры всем своим соседям. Любой сайт s (не инициатор), получивший первый раз маркер от одного из своих соседей (обозначим этого соседа pre), рассылает маркеры всем соседним сайтам, кроме того, от которого получил маркер. Соседи поступают точно так же. Волна удаляется от инициатора.

Дальнейший процесс рассмотрим на примере дерева. Волна доходит до некоторых из висячих вершин. Висячей вершине отправлять маркер дальше некуда. Тогда она возвращает его той вершине, от которой получила (вот оно «эхо»). Вершины, получившие «эхо» от своих соседей, возвращают маркеры своим вершинам pre. Те, в свою очередь, генерируют «эхо» своим предшественникам. Наконец «эхо» доходит до инициатора. Инициатор, получив «эхо» от всех своих соседей, выполняет процедуру return (OK).

Ниже приведен распределенный алгоритм, состоящий из описаний процесса вычислений для сайта – инициатора и описаний процессов для сайтов – не-нициаторов. В тексте описания процесса тот сайт, на котором этот процесс выполняется (свой сайт), обозначен идентификатором this (в традициях языка Симула-67). Множество Out(this) – это множество сайтов, смежных по выходу с сайтом this, т.е. тех сайтов, на которые с сайта this можно отправить сообщения по однонаправленным или двунаправленным каналам связи. Функция card() задает число кардинальности (мощность) множества, являющегося аргументом этой функции. Переменные, встречающиеся в текстах процессов – локальные (по экземпляру для каждого процесса): обмен информацией между процессами происходит только посредством сообщений, разделяемые переменные отсутствуют. Начальные значения счетчиков counter равны 0.

Процесс для инициатора:

begin for u Î Out(this) do out token to u;