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

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

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

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

В следующем тексте используются локальные переменные сайтов:

pre – сайт, предшествующий тому, который выполняет текущий процесс, т.е. сайт, с которого пришел маркер;

used[q] – признак того, отправлен ли был маркер на сайт u.

var used[q]: boolean init false для всех u Î Out(this);

pre: site init udef;

Для инициатора (выполняется один раз):

begin pre:= this; выбор u Î Out(this);

used[u]:= true; out token to u;

End

Для каждого процесса при получении token от s:

begin if pre = udef then pre:= s;

if " u Î Out(this): used[u]

then return(OK)

else if $ u Î Out(this): (u ¹ pre & Øused[u])

then begin выбор u Î Out(this) \ {pre} с Øused[u];

used[u]:= true; out token to u

End

else begin used[pre]:= true;

out token to pre

End

End

Так как процесс каждого сайта передает маркер через каждый канал не более одного раза, то каждый процесс получает маркер через каждый канал не более одного раза. Каждый раз, когда маркер захватывается не-инициатором u, получается, что процесс u получил маркер на один раз больше, чем послал его. Отсюда следует, что количество каналов, инцидентных u, превышает количество каналов, использованных u, по крайней мере, на 1. Таким образом, u не завершает процесс, а передает маркер дальше. Следовательно, завершение процесса производится в сайте-инициаторе.

Ниже показывается, что когда алгоритм завершается, каждый процесс передал маркер.

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

(2) Для каждого посещаемого процесса u все каналы, инцидентные u были пройдены один раз в каждом направлении. Предположив, что это не так, выберем в качестве u первый встретившийся процесс, для которого это не выполняется, и заметим, что из пункта (1) u не является инициатором. Из выбора u, все каналы, инцидентные pre(u) были пройдены один раз в обоих направлениях, откуда следует, что u переслал маркер своему предшественнику. Следовательно, u использовал все инцидентные каналы, чтобы переслать маркер; но, так как маркер в конце остается в инициаторе, u получил маркер ровно столько же раз, сколько отправил его, т.е. u получил маркер по одному разу через каждый инцидентный канал. Мы пришли к противоречию.

(3) Все процессы были посещены и каждый канал был пройден по одному разу в обоих направлениях. Если есть непосещенные процессы, то существуют соседи u и s такие, что u был посещен, а s не был. Это противоречит тому, что все каналы u были пройдены в обоих направлениях. Следовательно, из пункта (2), все процессы были посещены и все каналы пройдены один раз в обоих направлениях.

Каждое вычисление алгоритма Тарри определяет остовное дерево графа. В корне дерева находится инициатор, а каждый не-инициатор u в конце вычисления занес своего предшественника в дереве в переменную pre.