Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 74
Текст из файла (страница 74)
Отсюда следуетуказанная в этой теореме оценка.Метод Аттьи. Другой метод построения алгоритма избрания лидера на основе алгоритмов обхода был предложен Аттьей в работе [9] . В этом алгоритме обход, совершаемый некоторым маркером с отличительным признаком q, непрерывается в том случае, когда этот маркер достигает какого-либо процессаr, который уже посетил другой маркер, выпущенный, например, процессом p.Вместо этого маркер-захватчик переходит в режим ожидания в узле r, но затопосылает в погоню за маркером p «охотничий» маркер, который возвращаетсяв узел r, если маркер p был успешно подавлен. Когда охотник возвращается,278Гл. 7. Алгоритмы избрания лидеранет нужды начинать новый обход; можно продолжить текущий обход, совершаемый маркером q, экономя тем самым используемые сообщения.
Чтобы охотникмог вернуться в узел r, требуется двунаправленность сети. Если использоватьпроизвольный алгоритм f(x)-обхода, то в результате будет построен алгоритмизбрания лидера, имеющий сложность по числу обменов сообщениями, приблиNPзительно равную величине 3f(N/i).i=17.4.2. Приложения алгоритма Корача—Каттена—МоранаЕсли для некоторого класса сетей существует алгоритм f(x) -обхода, то этоткласс будем называть f(x)-обозримым. Так как многие классы сетей относятся к числу O(x)-обозримых, предложенный метод позволяет строить алгоритмы избрания сложности O(N log N) по числу обменов сообщениями, и это самоелучшее, что может быть получено на основе указанного результата. Впрочем,в отдельных случаях при наличии ориентации в сети можно построить и болеекачественные алгоритмы (см.
гл. 11).Выборы в кольцах. Все кольца x-обозримы, и, следовательно, алгоритмКорача–Каттена–Морана проводит выборы лидера в кольце с использованием2N log N обменов сообщениями. Мы уже знаем из теоремы 7.13, что это наилучшая возможная оценка.Выборы в кликах. Все клики 2x-обозримы, причем ориентация здесь ненужна, и, следовательно, алгоритм KKM проводит выборы лидера в клике с использованием 3N log N обменов сообщениями в соответствии с теоремой 7.24.Более тщательный анализ этого алгоритма показывает, что на самом деле в данном случае его сложность оценивается величиной 2N log N + O(N).
Чтобы догнатьлюбой маркер достаточно использовать не более трех сообщений, поэтому общеечисло сообщений в режиме погони, отправленных по ходу вычисления, ограниlogPN +12−i N = O(N). Во время написания этой книги автору нечено величиной 3i=0было известно никаких алгоритмов избрания в кликах, имеющих лучшую оценкусложности, нежели 2N log N + O(N). Нижняя оценка сложности Ω (N log N) былаустановлена Корачем, Мораном и Заксом [119] .Указанные результаты остаются справедливыми только для клик, не наделенных ориентацией; при наличии ориентации можно построить алгоритмы линейнойсложности.Выборы в торах.
Торовые сети с ориентацией являются x-обозримыми (см. алгоритм 6.10), и, следовательно, алгоритм KKM проводит выборы лидера в торес использованием 2N log N обменов сообщениями. При отсутствии ориентациидля обхода можно воспользоваться алгоритмом Тарри, который решает задачуобхода тора за линейное время. Петерсон в работе [160] предложил алгоритмизбрания лидера на решетках и торах, который использует O(N) обменов сообщениями и не требует разметки ребер.7.5. Упражнения к главе 72797.5. Упражнения к главе 77.5.1Упражнение 7.1. Докажите, что алгоритм избрания путем сравнения является волновым алгоритмом, если событие избрания процесса лидером рассматривать как событие решения.Упражнение 7.2.
Покажите, что сложность по времени алгоритма 7.1 составляет 2D.7.5.2PУпражнение 7.3. Докажите тождество mi=1 Hi = (m + 1)Hm − m, используемое в § 7.2.1.Упражнение 7.4. Покажите, что ln(N + 1) < HN < ln(N) + 1. (Здесь lnобозначает натуральный логарифм.)Упражнение 7.5. Рассмотрим алгоритм Ченя—Робертса, полагая, что каждый процесс является инициатором. При каком расположении отличительныхпризнаков в кольце сложность по числу обменов сообщениями будет минимальной и сколько обменов сообщениями потребуется в этом случае?Упражнение 7.6. Какова будет сложность в среднем алгоритма Ченя —Робертса, если ограничиться теми случаями, когда есть в точности S инициаторов,причем любой выбор одного из S процессов в качестве инициаторов одинакововозможен?Упражнение 7.7.
Приведите начальную конфигурацию для алгоритма 7.7,при которой алгоритму действительно потребуется провести blog Nc + 1 туров.Приведите также начальную конфигурацию, при которой этому алгоритму потребуется всего два тура, независимо от числа инициаторов. Может ли алгоритмзавершить работу за один тур?Упражнение 7.8. Определите множество ECR (как это сделано непосредственно перед леммой 7.10) для алгоритма Ченя —Робертса.7.5.3Упражнение 7.9. Примените метод угасания к кольцевому алгоритму и сравните полученный алгоритм с алгоритмом Ченя—Робертса. В чем состоит различие и как оно проявляется?Упражнение 7.10. Для каждого из семи типов сообщений, фигурирующихв алгоритме Галладжера—Хамблета—Спиры определите, может ли сообщениеэтого типа поступить в узел, пребывающий в состоянии sleep.Упражнение 7.11.
Предположим, что в алгоритме GHS применяется дополнительная процедура побудки, которая гарантирует, что этот алгоритм начнетсвою работу в каждом узле не позднее чем через N единиц времени.Докажите методом индукции, что спустя самое большее 5N l − 3N единиц временикаждый узел будет иметь ранг l.Докажите, что этот алгоритм завершит работу спустя не более 5N log N единицвремени.280Гл. 7. Алгоритмы избрания лидера7.5.4Упражнение 7.12. Покажите, что для планарных сетей существует алгоритмизбрания сложности O(N log N).Упражнение 7.13. Покажите, что для торов, не наделенных ориентацией, существует алгоритм избрания сложности O(N log N) .
(Указание: проведитеанализ производительности алгоритма Тарри на торах.)Упражнение 7.14. Покажите, что для гиперкубов, не наделенных ориентацией, существует алгоритм избрания сложности O(N log N).Упражнение 7.15. Покажите, что для сетей, степень узлов которых ограничена величиной k (это означает, что каждый узел имеет не более k соседей),существует алгоритм избрания сложности O(N(log N + k)).ГЛАВА 8ОБНАРУЖЕНИЕ ЗАВЕРШЕНИЯВычисление распределенного алгоритма завершается, когда этот алгоритм достигает некоторой заключительной конфигурации, т.
е. такой конфигурации, изкоторой данный алгоритм не может сделать ни одного шага. Это не всегда означает, что в заключительной конфигурации каждый процесс пребывает в одном иззаключительных состояний, т. е. в таком состоянии, в котором не может произойти никаких событий. Рассмотрим, например, такую ситуацию, когда каждыйпроцесс пребывает в состоянии готовности к приему сообщений, а все каналыпусты. Эта конфигурация является заключительной, хотя указанные состояниямогли бы с равным успехом оказаться и промежуточными состояниями вычисления.
В данном случае процессы не осведомлены о том, что вычисление ужезавершилось; мы будем говорить, что произошло неявное завершение вычисления. Мы будем говорить также, что в процессе произошло явное завершениевычисления, если то состояние, в котором пребывает этот процесс в заключительной конфигурации, является заключительным состоянием данного процесса.Неявное завершение вычисления называют также завершением обмена сообщениями, потому что никакой обмен сообщениями невозможен, если достигнутазаключительная конфигурация. Явное завершение вычисления называют такжезавершением работы процессов, потому что работа процессов завершается,если алгоритм явно завершает работу.Обычно проще спроектировать алгоритм, завершающий вычисления неявно,чем алгоритм, работа которого завершается явно.
Действительно, при проектировании алгоритма можно не обращать внимания на те детали, которые касаются завершения работы процессов; наше внимание сосредоточено на том, чтобыограничить общее число событий, которые могут произойти по ходу вычисления.С другой стороны, в приложениях алгоритма может потребоваться, чтобы процессы завершали работу явно.
Только после явного завершения работы можнобудет сбросить значения используемых переменных и рассматривать результаты вычисления как окончательные. Кроме того, к заключительной конфигурацииможет привести и блокировка распределенного алгоритма; в этом случае придостижении заключительной конфигурации вычисление должно быть перезапущено.В настоящей главе будут исследованы общие методы преобразования алгоритмов, в которых вычисления оканчиваются по завершении обмена сообщениями, в алгоритмы, в которых вычисления оканчиваются завершением работы процессов.
Располагая такими методами, можно проектировать алгоритм, принимаяв расчет лишь неявное завершение его вычислений (т. е. следя лишь за тем, чтобы282Гл. 8. Обнаружение завершениявсе вычисления нашего алгоритма были конечны), после чего, используя один изэтих методов, привести алгоритм к такому виду, в котором вычисления оканчиваются по завершении работы процессов. Указанные методы предусматриваютвведение двух дополнительных алгоритмов, которые взаимодействуют друг с другом, а также с заданным алгоритмом, имеющим неявное завершение вычислений.Один из этих алгоритмов анализирует текущее вычисление исходного алгоритмаи каким-либо образом обнаруживает, что это вычисление достигло заключительной конфигурации. После этого вызывается второй алгоритм, который рассылаетсообщение о завершении вычисления всем процессам, призывая их перейти в заключительное состояние.Самой сложной частью такого преобразования оказывается алгоритм, обнаруживающий завершение вычисления.
Процедура рассылки весьма проста, и мыобсудим ее в § 8.1.3. В этой главе будет показано, что обнаружение завершениявозможно для всех классов сетей, для которых можно разработать волновой алгоритм. Эти классы включают сети, допускающие избрание лидера, сети, процессы которых обладают отличительными признаками, древесные сети, а также сети,в которых процессам доступны сведения о таких топологических параметрах, какдиаметр сети или число процессов. С другой стороны, в гл. 9 будет показано,что для безымянных сетей, размер которых заранее неизвестен процессам, существует неявно завершающийся алгоритм вычисления максимума входных данныхвсех процессов, но нет явно завершающегося алгоритма решения указанной задачи.
И это означает, что обнаружение завершения невозможно для безымянныхсетей, размер которых неизвестен.В тех случаях, когда обнаружение завершения возможно, мы установим нижние оценки для числа сообщений, которыми обмениваются процессы при работеалгоритма обнаружения завершения. Будет показано также, что существуют алгоритмы, сложность которых соответствует указанным оценкам. В разд. 8.5.1 дается формальная постановка задачи на основе модели поведения распределенныхвычислений, устанавливаются нижние оценки и описывается процедура рассылкиоповещающих сообщений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
