Быстрый поиск

Реферат: Распределенные алгоритмы

Рис.7.5 Расположение идентификаторов на кольце.

Чтобы вычислить суммарное количество пересылок маркера по всем расположениям, вычислим сначала суммарное количество пересылок маркера <tok,pi> по всем расположениям, а потом просуммируем по i. Маркер <tok,s> при любом расположении передается N раз, следовательно, он пересылается всего N(N-1)! раз. Маркер <tok,pi> передается не более i раз, так как он будет удален из кольца, если достигнет s. Пусть Ai,k - количество циклических расположений, при которых <tok,pi> передается ровно k раз. Тогда суммарное число пересылок <tok,pi> равно .

Маркер <tok,pi> передается ровно i раз, если pi является наименьшим из идентификаторов от p1 до pi, что имеет место в (1/i)*(N-1)! расположениях; итак

Маркер <tok,pi> передается не менее k раз (здесь k £ i), если за процессом pi следует k-1 процесс с идентификаторами, большими pi. Количество расположений, в которых pi - наименьший из k идентификаторов pi-k+1, ..., pi, составляет 1/k часть всех расположений, т.е. (1/k)*(N-1)!. Теперь, для k<i <tok,pi> передается ровно k раз, если он передается не менее, но и не более k раз, т.е. ³ k раз, но не ³ k+1 раз. В результате количество расположений, где это выполняется, равно , т.е. ( для k < i ).

Общее количество передач <tok,pi> во всех расположениях равно:

что равняется . Сумма известна как i-е гармоническое число, обозначаемое Hi. В качестве Упражнения 7.3 оставлено доказательство тождества .

Далее мы суммируем по i количество передач маркера, чтобы получить общее количество передач (исключая передачи <tok,s>) во всех расположениях. Оно равно

Добавляя N(N-1)! передач маркера для <tok,s>, мы получаем общее количество передач, равное

Т.к. это число выведено для (N-1)! различных расположений, среднее по всем расположениям, очевидно, равно N×HN, что составляет »0.69N logN (см. Упр.7.4).

7.2.2 Алгоритм Petersen / Dolev-Klawe-Rodeh

Алгоритм Чанга-Робертса достигает сложности сообщений O(N logN) в среднем, но не в наихудшем случае. Алгоритм со сложностью O(N logN) в наихудшем случае был дан Франклином [Franklin; Fra82], но этот алгоритм требует, чтобы каналы были двунаправленными. Petersen [Pet82] и Dolev, Klawe, Rodeh [DKR82] независимо разработали очень похожий алгоритм для однонаправленных колец, решающий задачу с использованием только O(N logN) сообщений в наихудшем случае. Алгоритм требует, чтобы каналы подчинялись дисциплине FIFO.

Сначала алгоритм вычисляет наименьший идентификатор и сообщает его каждому процессу, затем процесс с этим идентификатором становится лидером, а все остальные терпят поражение. Алгоритм легче понять, если представить, что он выполняется идентификаторами, а не процессами. Изначально каждый идентификатор активен, но на каждом круге некоторые идентификаторы становятся пассивными, как будет показано позднее. При обходе круга активный идентификатор сравнивает себя с двумя соседними активными идентификаторами по часовой стрелке и против нее. Если он является локальным минимумом, он остается в круге, иначе он становится пассивным. Т.к. все идентификаторы различны, идентификатор рядом с локальным минимумом сам не является локальным минимумом, откуда следует, что не менее половины идентификаторов выбывают из круга при каждом обходе. Следовательно, после не более чем logN кругов остается только один активный идентификатор, который и является победителем.

Рис.7.6 Процесс p получает текущие идентификаторы q и r.

Этот принцип может быть непосредственно реализован в двунаправленных сетях, как это сделано в алгоритме Франклина [Fra82]. В ориентированных кольцах сообщения можно посылать только по часовой стрелке, что затрудняет получение соседнего активного идентификатора в этом направлении; см. Рис. 7.6. Идентификатор q нужно сравнить с r и p; идентификатор r можно послать q, но идентификатор p нужно было бы передавать против направления каналов. Чтобы сравнить q и с r, и с p, идентификатор q передается (в направлении кольца) процессу, который имеет идентификатор p, а r передается не только процессу с идентификатором q, но и дальше, процессу с идентификатором p. Если q является единственным активным идентификатором в начале обхода круга, первый идентификатор, который q встречает при обходе, равен q (т.е. в этом случае p = q). Когда это происходит, идентификатор q выигрывает выборы.

Алгоритм для процессов в однонаправленном кольце обозначен как Алгоритм 7.7. Процесс p является активным в круге, если он в начале круга имеет активный идентификатор cip. Иначе p является пассивным и просто пропускает через себя все получаемые сообщения. Активный процесс посылает свой текущий идентификатор следующему активному процессу, и получает текущий идентификатор предыдущего активного процесса, используя сообщения <one,·>. Полученный идентификатор сохраняется (в переменной acnp), и если он не выбывает из круга, он будет текущим идентификатором p в следующем круге. Чтобы определить, остается ли идентификатор acnp в круге, его сравнивают с cip и активным идентификатором, полученным в сообщении <two,·>. Процесс p посылает сообщение <two,acnp>, чтобы следующий активный процесс мог провести такое же сравнение. Исключение возникает, когда acnp = cip; в этом случае остался один активный идентификатор и об этом сообщается всем процессам в сообщении <smal,acnp>.

var cip : P init p ; (* Текущий идентификатор p *)

acnp : P init udef ; (* Идентификатор соседа против часовой стрелки *)

winp : P init udef ; (* Идентификатор победителя *)

statep : (active, passive, leader, lost) init active ;

begin if p - инициатор then statep := active else statep := passive ;

while winp = udef do

begin if statep = active then

begin send <one,cip> ; receive <one,q> ; acnp := q ;

if acnp = cip then (* acnp - минимум *)

begin send <smal,acnp> ; winp := acnp ;

receive <smal,q>

end

else (* acnp - текущий идентификатор соседа *)

begin send <two,acnp> ; receive <two,q> ;

if acnp < cip and acnp < q

then cip := acnp

else statep := passive

end

else (* statep = passive *)

begin receive <one,q> ; send <one,q> ;

receive m ; send m ;

(* m - либо <two,q>, либо <smal,q> *)

if m - <smal,q> then winp := q

end

end ;

if p = winp then statep := leader else statep := lost

end

Алгоритм 7.7 Алгоритм Petersen / Dolev-Klawe-Rodeh.

Теорема 7.7 Алгоритм 7.7 решает задачу выбора для однонаправленных сетей с использованием O(N logN) сообщений.

Доказательство. Будем говорить, что процесс находится на i-м круге, когда он выполняет основной цикл в i-й раз. Обходы круга не синхронизированы глобально; возможно, что в различных частях кольца один процесс на несколько кругов впереди другого. Но, т.к. каждый процесс отправляет и получает в каждом круге ровно по два сообщения и каналы подчиняются дисциплине FIFO, то сообщение всегда будет получено в том же круге, в каком оно было послано. На первом круге все инициаторы активны и все имеют различные «текущие идентификаторы».

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105