Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 103
Текст из файла (страница 103)
Топологияхордового кольца с единственной хордой, размах которой близок к л/М напоминает тор, и наш алгоритм будет представлять собой адаптацию алгоритма Петерсона (см. [160]) для торов.В начале каждого тура всякий активный процесс пытается отыскать, или увидеть, другой процесс, который считается активным в том же самом туре; процессвидит самое большее еще один процесс, но его могут видеть многие процессы.Есть два способа продвижения какого-либо активного процесса в следующийтур.Первый из них весьма похож на продвижение по принципу «локального максимума» из алгоритма Франклина: если процесс замечает другой процесс с младшим именем и его также замечает процесс с младшим именем, то наш процесспереходит в следующий тур.
Не более половины процессов могут перейти в следующий тур, руководствуясь таким правилом: ведь если какой-либо процесс перешел в следующий тур, то хотя бы один младший процесс, который его заметил,в следующий тур переведен не был.Было бы слишком накладно заставлять каждый активный процесс заниматься поиском в сети, до тех пор пока он не заметит другой активный процесс;поэтому активные процессы обшаривают только ограниченное подмножество сети, и поиск может завершиться так, что никакого другого процесса заметить неудастся.
Второе правило продвижения указывает, что в таком случае процесс,проводивший поиск, переходит в следующий тур!390Гл. 11. Восприятие направления и ориентацияГлавное достоинство этого алгоритма состоит в организации процедуры поиска таким образом, чтобы 1 ) область поиска была достаточно велика и позволялалишь немногим процессам перейти в следующий тур по второму правилу и 2 )поиск был достаточно эффективным и позволял получить в итоге небольшуюсложность. Теперь представим себе, что мы очерчиваем все большие и большиеквадраты на бесконечной решетке и замечаем, что число точек на границе растетгораздо медленнее, чем число точек во внутренней области.Квадраты и границы, процедуры поиска.
Для каждого элемента g £ Ъмназовем 1-квадратом элемента g множество элементовSg,i= {&+ г' 1+ /' t'- 0 ^ i ^ /, 0 ^ ^ /}.Множество Sgj — это множество (не более чем) ( /+ I ) 2 процессов, доступныхиз g за счет пересечения не более / 1-дуг и не более / /-дуг. Активный процессзанимается поиском другого активного процесса в /-квадрате, но не отправляясообщений всем процессам из этого квадрата, ибо это было бы слишком дорого.Назовем границей такое множество точек Bgj, для которых хотя бы одно изуказанных нестрогих неравенств становится равенством, т. е.Bgj = {§■ + /• 1 , g + / • 1 + / • /, g + / • /, g + / • 1 + i ■t : 0 ^/},а внутренней областью назовем множество Igj = Sgj \ Bg t. На границе Bg tрасполагаются (самое большее) 4/ процессов, и, кроме того, если S gj и Spj пересекаются, то Bgj и Врц также пересекаются.Процессор, участвующий в г'-м туре, начинает поиск других процессов, отправляя зонд-маркер по границе /-квадрата. Этот маркер пытается совершить /переходов в направлении 1 , / переходов в направлении /, / переходов в направлении —1 и / переходов в направлении —/.
Размер квадрата зависит от номература; в г-м туре длина стороны /; выбирается равной а' (где а — константа, немногим превосходящая 1). Для обхода всей границы требуется совершить обмен 4/сообщениями, но этот обход может быть прерван по следующим причинам.Если маркер р посетит процесс, в котором уже побывал другой маркер, выпущенный в более высоком туре, обход прерывается; процесс р никогда не получитобратно свой зонд и не перейдет в последующий тур.
Если маркер впервые попадает в процесс, в котором уже побывал (отличный от него) маркер, выпущенныйв том же туре (скажем, процессом q), то процесс р «замечает» процесс q. Еслиимя процесса q младше, чем имя процесса р, то процесс р должен быть об этомуведомлен, так как способность заметить процесс q очень важна для продвижения процесса р в следующий тур по первому правилу. Если же имя процесса qстарше имени процесса р, то р утрачивает шанс быть переведенным в следующийтур, но процесс q должен быть проинформирован об этом, так как тот факт, чтопроцесс р заметил процесс q, мог бы быть очень важен для продвижения q вследующий тур по первому правилу.
Таким образом, либо маркер возвращаетсяобратно к процессу р, либо маркер-преследователь отправляется к процессу q погранице, которую обходит зонд-маркер, выпущенный процессом q, с тем чтобыоповестить q о том, что его заметил процесс с младшим именем. И коль скоро для11.2. Выборы на кольцах и хордовых кольцах391процесса q достаточно, чтобы его оповестили об одном процессе с младшим именем, которому удалось заметить q, процесс, отправивший маркер-преследовательпроцессу q, уже не будет отправлять больше маркеров-преследователей, относящихся к процессу р.На основе приведенного описания процедуры обработки маркеров можносформулировать следующие локальные свойства, определяющие продвижениепроцесса р в следующий тур.
Во-первых, зонд-маркер процесса р возвращается с оповещением о том, что удалось заметить процесс с младшим именем,и, кроме того , маркер-преследователь прибывает в р с сообщением о том, чтокакой-то процесс с младшим именем заметил р. Во-вторых, зонд-маркер процесса р возвращается с уведомлением о том, что никакого процесса с младшимименем заметить не довелось.Мы покажем, что в каждый тур проходит по меньшей мере один процесс.Если ни одному из процессов не довелось заметить других, то в следующий турпроходят все процессы. Допустим, что хотя бы одному процессу удалось заметитьдругой процесс. Пусть процесс г — это процесс с самым старшим именем изчисла тех, которые были замечены.
Тогда либо процессу г не довелось заметитьдругие процессы, и он проходит в следующий тур согласно второму правилу, либопроцесс г заметил процесс с младшим именем и г проходит в следующий тур попервому правилу.Некоторые выкладки Наш алгоритм похож на алгоритм Петерсона из работы [160], и здесь будут присутствовать те же самые выкладки. Обозначимсимволом At количество активных процессов, которые приняли участие в г-м туре; очевидно, До ^ N.
Вначале мы получим верхнюю оценку величины Л; длявсех туров, в которых размер квадратов меньше N, т. е. для всех туров, номеракоторых удовлетворяют неравенству г ^ loga V~N.Лемма 11.15. Для туров , номера которых удовлетворяют неравенству г ^ log_ л/N имеет место оценка At ^ctZI(2 — )Д о к а з а т е л ь с т в о . Как мы уже убедились, каждый процесс, перешедший в следующий тур по первому правилу, был замечен другим процессом, который в следующий тур не перешел. Поэтому не более половины процессов, которым удалось заметить какой-либо другой, были переведены в следующий турпо этому правилу.Некоторые процессы могли перейти в следующий тур по второму правилу (засчет того, что их не заметили другие процессы), но при этом требуется, чтобы длядвух процессов р и q, перешедших в следующий тур благодаря этому правилу,квадраты Spj и Sqj не пересекались.
Действительно, если бы эти квадраты налагались друг на друга, то пересекались бы и их границы, по которым двигалисьзонды-маркеры, запущенные процессами р и q. Один из таких маркеров достигбы точки пересечения первым, лишив другой маркер возможности продолжитьобход так, чтобы не был замечен ни один процесс. Следовательно, количествопроцессов, переведенных в следующий тур по второму правилу, меньше 7V//?.392Гл. 11. Восприятие направления и ориентацияИсходя из этого, а также принимая во внимание выбор /; = а', сделанныйнами ранее, мы приходим к заключению о том, чтоAi+ 1 ^Aj + N/a2Применяя индукцию по г, можно убедиться в том, что отсюда следует оценкаAi ^Nt2i( 2- o t 2)□Из этой леммы вытекает линейная оценка числа обменов сообщениями, атакже константная оценка количества процессов, которым удалось пробитьсяв loga \/N - vl тур.Следствие 11.16.
На протяжении первых туров, начиная с 0-го тураи оканчивая loga \Щ-м туром, совершается менее ------^ -----щЫ обменовсообщениями.aaД о к а з а т е л ь с т в о . В лемме 11.15 уже установлена оценка числа активных процессов, участвующих в г-м туре. Оценка числа обменов сообщениямипроводится так. Зонд-маркер всякого активного процесса р может совершить4а‘ переходов, и это заносится на счет процесса р. Маркеры-преследователи,направляющиеся к р, также заносят свой вклад на счет процесса р. Каждыйпроцесс, который был посещен зонд-маркером, запущенным процессом р, может отправить самое большее один маркер-преследователь, и поэтому на счетпроцесса р можно занести не более 4а' переходов, совершенных маркерамипреследователями.чительнымNпроцессов, участвующих в г-ма2'(2 —а2)туре, приходится не более 8 а! обменов сообщениями, и общее число обменов соg/уобщениями в г-м туре ограничено величиной У.-----^•(1 /а)'.
Эти величины образу—8N<хют геометрическую прогрессию, сумма которой по всем турам равна -----— -.Таким образом, на долю каждого из□Завершаемость работы алгоритма. Из леммы 11.15 можно заключить, чточисло процессов, успешно выдержавших первые loga л/N туров, ограничено сверху константой 1/(2 —а2). Чтобы избрать лидера из этих оставшихся процессов,наш алгоритм переходит к другому этапу работы и начинает работать, как алгоритм Ченя—Робертса (§7.2.1). Всякий процесс, выдержавший loga y/V-й тур,отправляет маркер по всему кольцу, т. е. сообщение совершает N переходов в направлении + 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
