Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 103
Текст из файла (страница 103)
Не более половины процессов могут перейти в следующий тур, руководствуясь таким правилом: ведь если какой-либо процесс перешел в следующий тур, то хотя бы один младший процесс, который его заметил,в следующий тур переведен не был.Было бы слишком накладно заставлять каждый активный процесс заниматься поиском в сети, до тех пор пока он не заметит другой активный процесс;поэтому активные процессы обшаривают только ограниченное подмножество сети, и поиск может завершиться так, что никакого другого процесса заметить неудастся. Второе правило продвижения указывает, что в таком случае процесс,проводивший поиск, переходит в следующий тур!390Гл. 11. Восприятие направления и ориентацияГлавное достоинство этого алгоритма состоит в организации процедуры поиска таким образом, чтобы 1) область поиска была достаточно велика и позволялалишь немногим процессам перейти в следующий тур по второму правилу и 2)поиск был достаточно эффективным и позволял получить в итоге небольшуюсложность.
Теперь представим себе, что мы очерчиваем все большие и большиеквадраты на бесконечной решетке и замечаем, что число точек на границе растетгораздо медленнее, чем число точек во внутренней области.Квадраты и границы, процедуры поиска. Для каждого элемента g ∈ Z Nназовем l-квадратом элемента g множество элементовSg,l = {g + i · 1 + j · t : 0 6 i 6 l, 0 6 j 6 l}.Множество Sg,l — это множество (не более чем) (l + 1) 2 процессов, доступныхиз g за счет пересечения не более l 1-дуг и не более l t-дуг. Активный процессзанимается поиском другого активного процесса в l-квадрате, но не отправляясообщений всем процессам из этого квадрата, ибо это было бы слишком дорого.Назовем границей такое множество точек Bg,l , для которых хотя бы одно изуказанных нестрогих неравенств становится равенством, т. е.Bg,l = {g + i · 1, g + i · 1 + l · t, g + i · t, g + l · 1 + i · t : 0 6 i 6 l},а внутренней областью назовем множество Ig,l = Sg,l \ Bg,l .
На границе Bg,lрасполагаются (самое большее) 4l процессов, и, кроме того, если S g,l и Sh,l пересекаются, то Bg,l и Bh,l также пересекаются.Процессор, участвующий в i-м туре, начинает поиск других процессов, отправляя зонд-маркер по границе l-квадрата. Этот маркер пытается совершить lпереходов в направлении 1, l переходов в направлении t, l переходов в направлении −1 и l переходов в направлении −t. Размер квадрата зависит от номература; в i-м туре длина стороны li выбирается равной i (где — константа, немногим превосходящая 1). Для обхода всей границы требуется совершить обмен 4lсообщениями, но этот обход может быть прерван по следующим причинам.Если маркер p посетит процесс, в котором уже побывал другой маркер, выпущенный в более высоком туре, обход прерывается; процесс p никогда не получитобратно свой зонд и не перейдет в последующий тур.
Если маркер впервые попадает в процесс, в котором уже побывал (отличный от него) маркер, выпущенныйв том же туре (скажем, процессом q), то процесс p «замечает» процесс q. Еслиимя процесса q младше, чем имя процесса p, то процесс p должен быть об этомуведомлен, так как способность заметить процесс q очень важна для продвижения процесса p в следующий тур по первому правилу. Если же имя процесса qстарше имени процесса p, то p утрачивает шанс быть переведенным в следующийтур, но процесс q должен быть проинформирован об этом, так как тот факт, чтопроцесс p заметил процесс q, мог бы быть очень важен для продвижения q вследующий тур по первому правилу.
Таким образом, либо маркер возвращаетсяобратно к процессу p, либо маркер-преследователь отправляется к процессу q погранице, которую обходит зонд-маркер, выпущенный процессом q, с тем чтобыоповестить q о том, что его заметил процесс с младшим именем. И коль скоро для11.2. Выборы на кольцах и хордовых кольцах391процесса q достаточно, чтобы его оповестили об одном процессе с младшим именем, которому удалось заметить q, процесс, отправивший маркер-преследовательпроцессу q, уже не будет отправлять больше маркеров-преследователей, относящихся к процессу p.На основе приведенного описания процедуры обработки маркеров можносформулировать следующие локальные свойства, определяющие продвижениепроцесса p в следующий тур.
Во-первых, зонд-маркер процесса p возвращается с оповещением о том, что удалось заметить процесс с младшим именем,и, кроме того, маркер-преследователь прибывает в p с сообщением о том, чтокакой-то процесс с младшим именем заметил p. Во-вторых, зонд-маркер процесса p возвращается с уведомлением о том, что никакого процесса с младшимименем заметить не довелось.Мы покажем, что в каждый тур проходит по меньшей мере один процесс.Если ни одному из процессов не довелось заметить других, то в следующий турпроходят все процессы.
Допустим, что хотя бы одному процессу удалось заметитьдругой процесс. Пусть процесс r — это процесс с самым старшим именем изчисла тех, которые были замечены. Тогда либо процессу r не довелось заметитьдругие процессы, и он проходит в следующий тур согласно второму правилу, либопроцесс r заметил процесс с младшим именем и r проходит в следующий тур попервому правилу.Некоторые выкладки Наш алгоритм похож на алгоритм Петерсона из работы [160] , и здесь будут присутствовать те же самые выкладки.
Обозначимсимволом Ai количество активных процессов, которые приняли участие в i-м туре; очевидно, A0 6 N. Вначале мы получим верхнюю оценку величины A i длявсех туров, в которых размер квадратов меньше√ N, т. е. для всех туров, номеракоторых удовлетворяют неравенству i 6 log N.Лемма 11.15. Для туров, номера которых удовлетворяют неравен√N.ству i 6 log N имеет место оценка Ai 6 2i2(2 −)Д о к а з а т е л ь с т в о. Как мы уже убедились, каждый процесс, перешедший в следующий тур по первому правилу, был замечен другим процессом, который в следующий тур не перешел.
Поэтому не более половины процессов, которым удалось заметить какой-либо другой, были переведены в следующий турпо этому правилу.Некоторые процессы могли перейти в следующий тур по второму правилу (засчет того, что их не заметили другие процессы), но при этом требуется, чтобы длядвух процессов p и q, перешедших в следующий тур благодаря этому правилу,квадраты Sp,l и Sq,l не пересекались. Действительно, если бы эти квадраты налагались друг на друга, то пересекались бы и их границы, по которым двигалисьзонды-маркеры, запущенные процессами p и q. Один из таких маркеров достигбы точки пересечения первым, лишив другой маркер возможности продолжитьобход так, чтобы не был замечен ни один процесс.
Следовательно, количествопроцессов, переведенных в следующий тур по второму правилу, меньше N /l2i .392Гл. 11. Восприятие направления и ориентацияИсходя из этого, а также принимая во внимание выбор l i =нами ранее, мы приходим к заключению о том, чтоAi+1 62iAi + N /211.3. Вычисления в гиперкубахi, сделанный.Применяя индукцию по i, можно убедиться в том, что отсюда следует оценкаAi 6.N2i (2 −2)Из этой леммы вытекает линейная оценка числа обменов сообщениями, атакже √константная оценка количества процессов, которым удалось пробитьсяв log N-й тур.Следствие 11.16. На протяжении первых туров, начиная с 0-го тура√8N обменови оканчивая log N-м туром, совершается менее( − 1) (2 − 2)сообщениями.Д о к а з а т е л ь с т в о.
В лемме 11.15 уже установлена оценка числа активных процессов, участвующих в i-м туре. Оценка числа обменов сообщениямипроводится так. Зонд-маркер всякого активного процесса p может совершить4 i переходов, и это заносится на счет процесса p. Маркеры-преследователи,направляющиеся к p, также заносят свой вклад на счет процесса p.
Каждыйпроцесс, который был посещен зонд-маркером, запущенным процессом p, может отправить самое большее один маркер-преследователь, и поэтому на счетпроцесса p можно занести не более 4 i переходов, совершенных маркерамипреследователями.чительнымТаким образом, на долю каждого изтуре, приходится не более 8iN2i (2 −2)процессов, участвующих в i-мобменов сообщениями, и общее число обменов со-8N· (1/ ) i .
Эти величины образу2− 28N·.ют геометрическую прогрессию, сумма которой по всем турам равна−12− 2общениями в i-м туре ограничено величинойЗавершаемость работы алгоритма. Из леммы 11.15можно заключить, что√число процессов, успешно выдержавших первые log N туров, ограничено сверху константой 1/ (2 − 2). Чтобы избрать лидера из этих оставшихся процессов,наш алгоритм переходит к другому этапу работы и начинает работать,√ как алгоритм Ченя—Робертса (§ 7.2.1). Всякий процесс, выдержавший log N-й тур,отправляет маркер по всему кольцу, т. е.
сообщение совершает N переходов в направлении +1. Этот маркер поглощается всяким другим процессом с более старшим отличительным признаком, который также участвует в этом туре; маркертакже прерывает активность всех процессов, пребывающих на первом этапе работы алгоритма. На втором этапе работы алгоритма гарантируется, что только√процесс с наибольшим отличительным признаком, сумевший пройти log N-йтур, получит свой маркер обратно; этот процесс и избирается лидером.393Теорема 11.17. Описанный алгоритм позволяет избрать лидера с использованием O(N) обменовсообщениями на хордовом кольце с одной хор√дой (имеющей размах N).Д о к а з а т е л ь с т в о.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
