МЕНЮ


Фестивали и конкурсы
Семинары
Издания
О МОДНТ
Приглашения
Поздравляем

НАУЧНЫЕ РАБОТЫ


  • Инновационный менеджмент
  • Инвестиции
  • ИГП
  • Земельное право
  • Журналистика
  • Жилищное право
  • Радиоэлектроника
  • Психология
  • Программирование и комп-ры
  • Предпринимательство
  • Право
  • Политология
  • Полиграфия
  • Педагогика
  • Оккультизм и уфология
  • Начертательная геометрия
  • Бухучет управленчучет
  • Биология
  • Бизнес-план
  • Безопасность жизнедеятельности
  • Банковское дело
  • АХД экпред финансы предприятий
  • Аудит
  • Ветеринария
  • Валютные отношения
  • Бухгалтерский учет и аудит
  • Ботаника и сельское хозяйство
  • Биржевое дело
  • Банковское дело
  • Астрономия
  • Архитектура
  • Арбитражный процесс
  • Безопасность жизнедеятельности
  • Административное право
  • Авиация и космонавтика
  • Кулинария
  • Наука и техника
  • Криминология
  • Криминалистика
  • Косметология
  • Коммуникации и связь
  • Кибернетика
  • Исторические личности
  • Информатика
  • Инвестиции
  • по Зоология
  • Журналистика
  • Карта сайта
  • Распределенные алгоритмы

    независимо друг от друга предложили решение, составляющее O(N log N) для

    однонаправленного кольца. Это решение рассматривается в Подразделе 7.2.2.

    Алгоритмы были дополнены соответствующими нижними границами примерно в то

    же время. Нижняя граница для наихудшего случая для двунаправленных колец,

    равная ? 0.34N logN сообщений, была доказана Бодлендером [Bodlaender;

    Bod88]. Pachl, Korach и Rotem [PKR84] доказали нижние границы в ?(N logN)

    для средней сложности, как для двунаправленных так и для однонаправленных

    колец. Их результаты по нижним границам будут рассмотрены в Подразделе

    7.2.3.

    7.2.1 Алгоритмы ЛеЛанна и Чанга-Робертса

    В алгоритме ЛеЛанна [LeL77] каждый инициатор вычисляет список

    идентификаторов всех инициаторов, после чего выбирается инициатор с

    наименьшим идентификатором. Каждый инициатор посылает маркер, содержащий

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

    Предполагается, что каналы подчиняются дисциплине FIFO, и что инициатор

    должен сгенерировать свой маркер до того, как он получит маркер другого

    инициатора. (Когда процесс получает маркер, он после этого не инициирует

    алгоритм.) Когда инициатор p получает свой собственный маркер, маркеры всех

    инициаторов прошли через p, и p выбирается лишь в том случае, если p -

    наименьший среди инициаторов; см. Алгоритм 7.2.

    var Listp : set of P init {p} ;

    statep ;

    begin if p - инициатор then

    begin statep := cand ; send to Nextp ; receive ;

    while q ? p do

    begin Listp := Listp ? {q} ;

    send to Nextp ; receive ;

    end ;

    if p = min (Listp) then statep := leader

    else statep := lost

    end

    else repeat receive ; send to Nextp ;

    if statep = sleep then statep := lost

    until false

    end

    Алгоритм 7.2 Алгоритм выбора ЛеЛанна.

    Теорема 7.4 Алгоритм ЛеЛанна (Алгоритм 7.2) решает задачу выбора для

    колец, используя O(N2) сообщений и O(N) единиц времени.

    Доказательство. Так как порядок маркеров в кольце сохраняется (из

    предположения о каналах FIFO), и инициатор q отправляет до того как

    получит , то инициатор p получает прежде, чем вернется

    . Отсюда следует, что каждый инициатор p заканчивается со списком

    Listp, совпадающим с множеством всех инициаторов, и единственным выбираемым

    процессом становится инициатор с наименьшим идентификатором. Всего

    получается не больше N маркеров и каждый делает N шагов, что приводит к

    сложности сообщений в O(N2). Не позднее чем через N-1 единицу времени после

    того, как первый инициатор отправил свой маркер, это сделали все

    инициаторы. Каждый инициатор получает свой маркер обратно не позднее, чем

    через N единиц времени с момента генерации этого маркера. Отсюда следует,

    что алгоритм завершается в течение 2N-1 единиц времени.

    Все не-инициаторы приходят в состояние проигравший, но навсегда остаются в

    ожидании сообщений . Ожидание может быть прервано, если лидер

    посылает по кольцу специальный маркер, чтобы объявить об окончании выбора.

    Алгоритм Чанга-Робертса [CR79] улучшает алгоритм ЛеЛанна, устраняя из

    кольца маркеры тех процессов, для которых очевидно, что они проиграют

    выборы. Т.е. инициатор p удаляет из кольца маркер , если q > p.

    Инициатор p становится проигравшим, когда получает маркер с идентификатором

    q < p, или лидером, когда он получает маркер с идентификатором p; см.

    Алгоритм 7.3.

    var statep ;

    begin if p - инициатор then

    begin statep := cand ; send to Nextp ;

    repeat receive ;

    if q = p then statep := leader

    else if q < p then

    begin if statep = cand then statep := lost ;

    send to Nextp

    end

    until statep = leader

    end

    else repeat receive ; send to Nextp ;

    if statep = sleep then statep := lost

    until false

    end

    -'?[pic].

    Алгоритм Чанга-Робертса не улучшает алгоритм ЛеЛанна в отношении временной

    сложности или наихудшего случая сложности сообщений. Улучшение касается

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

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

    Теорема 7.6 Алгоритм Чанга-Робертса в среднем случае, когда все процессы

    являются инициаторами, требует только O(N logN) пересылок сообщений.

    Доказательство. (Это доказательство основано на предложении Friedemann

    Mattern.)

    Предположив, что все процессы являются инициаторами, вычислим среднее

    количество пересылок маркера по всем круговым расположениям N различных

    идентификаторов. Рассмотрим фиксированное множество из N идентификаторов, и

    пусть s будет наименьшим идентификатором. Существует (N-1)! различных

    круговых расположений идентификаторов; в данном круговом расположении пусть

    pi - идентификатор, находящийся за i шагов до s; см. Рис. 7.5.

    [pic]

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

    Чтобы вычислить суммарное количество пересылок маркера по всем

    расположениям, вычислим сначала суммарное количество пересылок маркера

    по всем расположениям, а потом просуммируем по i. Маркер

    при любом расположении передается N раз, следовательно, он пересылается

    всего N(N-1)! раз. Маркер передается не более i раз, так как он

    будет удален из кольца, если достигнет s. Пусть Ai,k - количество

    циклических расположений, при которых передается ровно k раз.

    Тогда суммарное число пересылок равно [pic].

    Маркер передается ровно i раз, если pi является наименьшим из

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

    итак

    [pic]

    Маркер передается не менее k раз (здесь k ? i), если за процессом

    pi следует k-1 процесс с идентификаторами, большими pi. Количество

    расположений, в которых pi - наименьший из k идентификаторов pi-k+1, ...,

    pi, составляет 1/k часть всех расположений, т.е. (1/k)*(N-1)!. Теперь, для

    k передается ровно k раз, если он передается не менее, но и не

    более k раз, т.е. ?€k раз, но не ?€k+1 раз. В результате количество

    расположений, где это выполняется, равно [pic], т.е. [pic] ( для k <

    i ).

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

    [pic],

    что равняется [pic]. Сумма [pic]известна как i-е гармоническое число,

    обозначаемое ?i. В качестве Упражнения 7.3 оставлено доказательство

    тождества [pic].

    Далее мы суммируем по i количество передач маркера, чтобы получить общее

    количество передач (исключая передачи ) во всех расположениях. Оно

    равно

    [pic].

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

    передач, равное

    [pic].

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

    расположениям, очевидно, равно N(?N, что составляет ?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 кругов остается только один активный идентификатор,

    который и является победителем.

    [pic]

    Рис.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 является пассивным и просто пропускает

    через себя все получаемые сообщения. Активный процесс посылает свой текущий

    идентификатор следующему активному процессу, и получает текущий

    идентификатор предыдущего активного процесса, используя сообщения .

    Полученный идентификатор сохраняется (в переменной acnp), и если он не

    выбывает из круга, он будет текущим идентификатором p в следующем круге.

    Чтобы определить, остается ли идентификатор acnp в круге, его сравнивают с

    cip и активным идентификатором, полученным в сообщении . Процесс p

    посылает сообщение , чтобы следующий активный процесс мог

    провести такое же сравнение. Исключение возникает, когда acnp = cip; в этом

    случае остался один активный идентификатор и об этом сообщается всем

    процессам в сообщении .

    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 ; receive ; acnp := q ;

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

    begin send ; winp := acnp ;

    receive

    end

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

    begin send ; receive ;

    if acnp < cip and acnp < q

    then cip := acnp

    else statep := passive

    end

    end

    else (* statep = passive *)

    begin receive ; send ;

    receive m ; send m ;

    (* m - либо , либо *)

    if m - 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, то сообщение всегда будет получено в том же круге, в каком

    оно было послано. На первом круге все инициаторы активны и все имеют

    различные «текущие идентификаторы».

    Утверждение 7.8 Если круг i начинается с k (k>1) активными процессами, и

    все процессы имеют различные ci, то в круге остаются не меньше 1 и не

    больше k/2 процессов. В конце круга снова все текущие идентификаторы

    активных процессов различны и включают наименьший идентификатор.

    Доказательство. Путем обмена сообщениями , которые пропускаются

    пассивными процессами, каждый активный процесс получает текущий

    идентификатор своего активного соседа против часовой стрелки, который

    всегда отличается от его собственного идентификатора. Далее, каждый

    активный процесс продолжает обход круга, передавая сообщения ,

    благодаря которым каждый активный процесс получает текущий идентификатор

    своего второго активного соседа против часовой стрелки. Теперь все активные

    процессы имеют различные значения acn, откуда следует, что в конце круга

    все оставшиеся в круге идентификаторы различны. По крайней мере, остается

    идентификатор, который был наименьшим в начале круга, т.е. остается хотя бы

    один процесс. Идентификатор рядом с локальным минимумом не является

    локальным минимумом, откуда следует, что количество оставшихся в круге не

    превышает k/2.

    Из Утверждения 7.8 следует, что существует круг с номером ?€?logN?+1,

    который начинается ровно с одним активным идентификатором, а именно, с

    наименьшим среди идентификаторов инициаторов.

    Утверждение 7.9 Если круг начинается ровно с одним активным процессом p с

    текущим идентификатором cip, то алгоритм завершается после этого круга с

    winq = cip для всех q.

    Доказательство. Сообщение пропускается всеми процессами и, в

    конце концов, его получает p. Процесс p обнаруживает, что acnp = cip и

    посылает по кольцу сообщение , вследствие чего все процессы

    выходят из основного цикла с winp = acnp.

    Алгоритм завершается в каждом процессе и все процессы согласовывают

    идентификатор лидера (в переменной winp); этот процесс находится в

    состоянии лидер, а остальные - в состоянии проигравший.

    Всего происходит не более ?logN?+1 обходов круга, в каждом из которых

    передается ровно 2N сообщений, что доказывает, что сложность сообщений

    ограничена 2N logN + O(N). Теорема 7.7 доказана.

    Dolev и др. удалось улучшить свой алгоритм до 1.5N logN, после чего

    Petersen получил алгоритм, использующий только 1.44N logN сообщений. Этот

    алгоритм снова был улучшен Dolev и др. до 1.356N logN. Верхняя граница в

    1.356N logN считалась наилучшей для выбора на кольцах более 10 лет, но была

    улучшена до 1.271N logN Higham и Przytycka [HP93].

    7.2.3 Вывод нижней границы

    В этом подразделе будет доказана нижняя граница сложности выбора на

    однонаправленных кольцах. Т.к. выбор можно провести за одно выполнение

    децентрализованного волнового алгоритма, нижняя граница сложности

    децентрализованных волновых алгоритмов для колец будет получена как

    заключение.

    Результат получен Pachl, Korach и Rotem [PKR84] при следующих

    предположениях.

    Граница доказывается для алгоритмов, вычисляющих наименьший идентификатор.

    Если существует лидер, наименьший идентификатор может быть вычислен с

    помощью N сообщений, а если наименьший идентификатор известен хотя бы

    одному процессу, процесс с этим идентификатором может быть выбран опять же

    за N сообщений. Следовательно, сложность задач выбора и вычисления

    наименьшего идентификатора различаются не более чем на N сообщений.

    Кольцо является однонаправленным.

    Процессам не известен размер кольца.

    Предполагается, что каналы FIFO. Это предположение не ослабляет результат,

    потому что сложность не-FIFO алгоритмов не лучше сложности FIFO алгоритмов.

    Предполагается, что все процессы являются инициаторами. Это предположение

    не ослабляет результат, потому что оно описывает ситуацию, возможную для

    каждого децентрализованного алгоритма.

    Предполагается, что алгоритмы управляются сообщениями; т.е. после

    отправления сообщений при инициализации алгоритма, процесс посылает

    сообщения в дальнейшем только после получения очередного сообщения. Т.к.

    рассматриваются асинхронные системы, общие алгоритмы не достигают лучшей

    сложности, чем алгоритмы, управляемые сообщениями. Действительно, если A -

    асинхронный алгоритм, то управляемый сообщениями алгоритм B может быть

    построен следующим образом. После инициализации и после получения любого

    сообщения B посылает максимальное количество сообщений, которое можно

    послать в A, не получая при этом сообщений, и только затем получает

    следующее сообщение. Алгоритм B не только управляется сообщениями, но кроме

    того, каждое вычисление B является возможным вычислением A (возможно, при

    довольно пессимистическом распределении задержек передачи сообщений).

    Три последних предположения устраняют недетерминизм системы. При этих

    предположениях каждое вычисление, начинающееся с данной начальной

    конфигурации, содержит одно и то же множество событий.

    В этом разделе через s = (s1, ..., sN), t и т.п. обозначаются

    последовательности различных идентификаторов процессов. Множество всех

    таких последовательностей обозначено через D, т.е. D = {(s1, ..., sk): si ?

    P и i ? j ? si ? sj}. Длина последовательности s обозначается через

    len(s), а конкатенация последовательностей s и t обозначается st.

    Циклическим сдвигом s называется последовательность s's'', где s = s''s' ;

    она имеет вид si, ..., sN, s1, ..., si-1. Через CS(s) (cyclic shift -

    циклический сдвиг) обозначено множество циклических сдвигов s, и

    естественно |CS(s)| = len(s).

    Говорят, что кольцо помечено последовательностью (s1, ..., sN), если

    идентификаторы процессов с s1 по sN расположены на кольце (размера N) в

    таком порядке. Кольцо, помеченное s также называют s-кольцом. Если t -

    циклический сдвиг s, то t-кольцо совпадает с s-кольцом.

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

    идентификаторов процессов, называемую следом (trace) сообщения. Если

    сообщение m было послано процессом p до того, как p получил какое-либо

    Страницы: 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


    Приглашения

    09.12.2013 - 16.12.2013

    Международный конкурс хореографического искусства в рамках Международного фестиваля искусств «РОЖДЕСТВЕНСКАЯ АНДОРРА»

    09.12.2013 - 16.12.2013

    Международный конкурс хорового искусства в АНДОРРЕ «РОЖДЕСТВЕНСКАЯ АНДОРРА»




    Copyright © 2012 г.
    При использовании материалов - ссылка на сайт обязательна.