Алгоритм для структуры – дерева

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

1) дерево – связный ациклический граф;

2) количество вершин в дереве на единицу больше, чем количество ребер;

3) в нетривиальном дереве имеется, по крайней мере, две вершины, степени которых равны единице; эти вершины называются висячими или терминальными; остальные вершины имеют степень, не меньше 2.

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

Если задержавшийся сосед все же передаст маркер, т.е. сайт v получит deg (v) маркеров, то сайт v выполнит процедуру return (OK). Выполнение процедуры return (OK) любым из сайтов завершает работу распределенного алгоритма.

Рис. 23. Шаг 1. Маркеры, инициированные висячими вершинами дерева

Рис. 24. Шаг 2. Продвижение маркеров по дереву

Рис. 25. Шаг 3. Заключительное перемещение маркеров

Описанный алгоритм не столь очевиден, как алгоритм для кольцевой архитектуры. Поэтому нам нужны гарантии его правильности, а именно, гарантии того, что если какой-либо из сайтов выполнил процедуру return (OK), все остальные сайты v_i получили, по крайней мере, по deg (v_i) – 1 маркеров и сгенерировали или готовы сгенерировать выходные маркеры.

Рисунки 23 – 25 иллюстрируют на примере некоторого дерева продвижение маркеров. На шаге 2 вершины, уже получившие маркеры, обозначены соответствующими числами. После выполнения шага 3, вершина, обозначенная «a» и имеющая степень 3, получит последние два маркера. Количество полученных маркеров станет равным трем, и будет выполнена процедура return (OK).

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

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

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