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

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

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

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

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

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

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

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

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

routine Initiator