Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 73

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 73)

□Функцию / назовем в ы п у к л о й , если выполняется неравенство /(а) + f { b ) ^^ /(а + b). Мы оценим здесь сложность нашего алгоритма исходя из предпо­ложения, что в его основу положен алгоритм /(х)-обхода (см. §6.6.3), где / —выпуклая функция.Теорема 7.24.Е сли и с п о л ь зо в а т ь п р о и з в о л ь н ы й а л г о р и т м f(x )-o 6 x o d a ,/ — вы пуклая ф ункция, т о алгорит м избрания лидера К орача— К ат т е­н а — М о р а н а , б уд уч и за п у щ е н k п р о ц есса м и -и н и ц и а т о р а м и , р еш и т за д а ч уо в ы б о р а х , о г р а н и ч и в ш и с ь (1 + log6)[/(/V) + А] о б м е н а м и с о о б щ е н и я м и .гдеД о к а з а т е л ь с т в о . Если алгоритм был запущен k процессами, то науровне / может быть порождено не более 2 ~ lk маркеров, откуда следует, чтонаивысший уровень, который может быть достигнут, не превосходит величиныLlog/eJ.На любом уровне каждый процесс отправляет маркер в режиме захвата са­мое большее с одним отличительным признаком.

Если на некотором уровне /есть маркеры с отличительными признаками р \ , ■■■, р / и имеется N t процессов,отправивших маркеры ( р р /), пребывающие в режиме захвата, то справедливо/неравенствоЛ/,- ^ N. Так как используемый алгоритм обхода — это алгоритм(=1/(х)-обхода, маркеры { р р /), остающиеся в режиме захвата, были переправленыне более /(А*) раз, и поэтому общее число обменов сообщениями, сопряженныхс передачей маркеров уровня /, пребывающих в режиме захвата, не превосходит/'величины/(Л^г).

которая, в свою очередь, не превышает f ( N ) , ибо функция /(=1выпуклая. На любом уровне каждый процесс отправляет не более одного дого­няющего маркера, и, следовательно, общее количество догоняющих маркеров накаждом уровне не превосходит N .Итак, мы имеем не более (1 -blog 6 ) различных уровней, на каждом из которыхсовершается самое большее f ( N ) + N обменов сообщениями.

Отсюда следуетуказанная в этой теореме оценка.□Метод Аттьи. Другой метод построения алгоритма избрания лидера на ос­нове алгоритмов обхода был предложен Аттьей в работе [9]. В этом алгорит­ме обход, совершаемый некоторым маркером с отличительным признаком q, непрерывается в том случае, когда этот маркер достигает какого-либо процессаг, который уже посетил другой маркер, выпущенный, например, процессом р .Вместо этого маркер-захватчик переходит в режим ожидания в узле г, но затопосылает в погоню за маркером р «охотничий» маркер, который возвращаетсяв узел г, если маркер р был успешно подавлен. Когда охотник возвращается,Гл. 7.

Алгоритмы избрания лидера278нет нужды начинать новый обход; можно продолжить текущий обход, соверша­емый маркером q, экономя тем самым используемые сообщения. Чтобы охотникмог вернуться в узел г, требуется двунаправленность сети. Если использоватьпроизвольный алгоритм /(х)-обхода, то в результате будет построен алгоритмизбрания лидера, имеющий сложность по числу обменов сообщениями, приблиNзительно равную величине 3 ^ f(N/i).(=17.4.2. Приложения алгоритма Корача—Каттена—МоранаЕсли для некоторого класса сетей существует алгоритм /(х)-обхода, то этоткласс будем называть /(х)-обозримым.

Так как многие классы сетей относят­ся к числу 0 (х)-обозримых, предложенный метод позволяет строить алгорит­мы избрания сложности 0(N log N) по числу обменов сообщениями, и это самоелучшее, что может быть получено на основе указанного результата. Впрочем,в отдельных случаях при наличии ориентации в сети можно построить и болеекачественные алгоритмы (см. гл. 1 1 ).Выборы в кольцах. Все кольца х-обозримы, и, следовательно, алгоритмКорача—Каттена—Морана проводит выборы лидера в кольце с использованием2AMogiV обменов сообщениями. Мы уже знаем из теоремы 7.13, что это наилуч­шая возможная оценка.Выборы в кликах. Все клики 2х-обозримы, причем ориентация здесь ненужна, и, следовательно, алгоритм ККМ проводит выборы лидера в клике с ис­пользованием 3A4og/V обменов сообщениями в соответствии с теоремой 7.24.Более тщательный анализ этого алгоритма показывает, что на самом деле в дан­ном случае его сложность оценивается величиной 2N log N+0(N).

Чтобы догнатьлюбой маркер достаточно использовать не более трех сообщений, поэтому общеечисло сообщений в режиме погони, отправленных по ходу вычисления, ограниlog/V + 12~‘N = 0(N). Во время написания этой книги автору нечено величиной 3;= обыло известно никаких алгоритмов избрания в кликах, имеющих лучшую оценкусложности, нежели 2NlogN + 0(N). Нижняя оценка сложности fi(iVlogiV) былаустановлена Корачем, Мораном и Заксом [119].Указанные результаты остаются справедливыми только для клик, не наделен­ных ориентацией; при наличии ориентации можно построить алгоритмы линейнойсложности.Выборы в торах. Торовые сети с ориентацией являются х-обозримыми (см. ал­горитм 6.10), и, следовательно, алгоритм ККМ проводит выборы лидера в торес использованием 2A4ogiV обменов сообщениями.

При отсутствии ориентациидля обхода можно воспользоваться алгоритмом Тарри, который решает задачуобхода тора за линейное время. Петерсон в работе [160] предложил алгоритмизбрания лидера на решетках и торах, который использует 0(N) обменов сооб­щениями и не требует разметки ребер.7.5. Упражнения к главе 72797.5.

Упражнения к главе 77.5.1Упражнение 7.1. Докажите, что алгоритм избрания путем сравнения явля­ется волновым алгоритмом, если событие избрания процесса лидером рассмат­ривать как событие решения.Упражнение 7.2. Покажите, что сложность по времени алгоритма 7.1 со­ставляет 2D.7.5.2Упражнение 7.3. Докажите тождество YlT=\ Н; = {т + 1 )НШ- т , исполь­зуемое в §7.2.1.Упражнение 7.4. Покажите, что In (У + 1) < Ндг < 1п(Л/) + 1. (Здесь Inобозначает натуральный логарифм.)Упражнение 7.5. Рассмотрим алгоритм Ченя—Робертса, полагая, что каж­дый процесс является инициатором.

При каком расположении отличительныхпризнаков в кольце сложность по числу обменов сообщениями будет минималь­ной и сколько обменов сообщениями потребуется в этом случае?Упражнение 7.6. Какова будет сложность в среднем алгоритма Ченя—Ро­бертса, если ограничиться теми случаями, когда есть в точности S инициаторов,причем любой выбор одного из S процессов в качестве инициаторов одинакововозможен?Упражнение 7.7. Приведите начальную конфигурацию для алгоритма 7.7,при которой алгоритму действительно потребуется провести Llog ?VJ + 1 туров.Приведите также начальную конфигурацию, при которой этому алгоритму по­требуется всего два тура, независимо от числа инициаторов. Может ли алгоритмзавершить работу за один тур?Упражнение 7.8.

Определите множество £ cr (как это сделано непосред­ственно перед леммой 7.10) для алгоритма Ченя—Робертса.7.5.3Упражнение 7.9. Примените метод угасания к кольцевому алгоритму и срав­ните полученный алгоритм с алгоритмом Ченя—Робертса. В чем состоит разли­чие и как оно проявляется?Упражнение 7.10. Для каждого из семи типов сообщений, фигурирующихв алгоритме Галладжера—Хамблета—Спиры определите, может ли сообщениеэтого типа поступить в узел, пребывающий в состоянии sleep.Упражнение 7.11. Предположим, что в алгоритме GHS применяется до­полнительная процедура побудки, которая гарантирует, что этот алгоритм начнетсвою работу в каждом узле не позднее чем через N единиц времени.Докажите методом индукции, что спустя самое большее 5N1—3N единиц временикаждый узел будет иметь ранг /.Докажите, что этот алгоритм завершит работу спустя не более bNlogN единицвремени.280Гл.

7. Алгоритмы избрания лидера7.5.4Упражнение 7.12. Покажите, что для планарных сетей существует алгоритмизбрания сложности 0(N log N).Упражнение 7.13. Покажите, что для торов, не наделенных ориентаци­ей, существует алгоритм избрания сложности 0(NlogN) . (Указание: проведитеанализ производительности алгоритма Тарри на торах.)Упражнение 7.14. Покажите, что для гиперкубов, не наделенных ориента­цией, существует алгоритм избрания сложности 0(NlogN).Упражнение 7.15.

Покажите, что для сетей, степень узлов которых огра­ничена величиной k (это означает, что каждый узел имеет не более k соседей),существует алгоритм избрания сложности 0(N(logN + k)).ГЛАВА8ОБНАРУЖЕНИЕ ЗАВЕРШЕНИЯВычисление распределенного алгоритма завершается, когда этот алгоритм до­стигает некоторой заключительной конфигурации, т. е.

такой конфигурации, изкоторой данный алгоритм не может сделать ни одного шага. Это не всегда озна­чает, что в заключительной конфигурации каждый процесс пребывает в одном иззаключительных состояний, т. е. в таком состоянии, в котором не может про­изойти никаких событий. Рассмотрим, например, такую ситуацию, когда каждыйпроцесс пребывает в состоянии готовности к приему сообщений, а все каналыпусты. Эта конфигурация является заключительной, хотя указанные состояниямогли бы с равным успехом оказаться и промежуточными состояниями вычис­ления.

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

Характеристики

Список файлов книги