Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 84
Текст из файла (страница 84)
§ 2.3.3); для этой цели пригодны какаппаратные таймеры, так и логические часы Лампорта (см. раздел 2.3.3). Сампринцип обнаружения завершения вычислений был предложен в работе Раны[161] .318Гл. 8. Обнаружение завершенияvar statep::::punackpqtp(active, passive)integer init 0 ;integer init 0 ;integer init 0 ;;(* Логические часы *)(* Число неподтвержденных сообщений *)(* Время недавно случившегося перехода в quiet *)Sp : { statep = active }begin p := p + 1 ; send hmes, p i ; unackp := unackp + 1 endRp : { Сообщение hmes, i из q достигло p }begin receive hmes, i; p := max( p , ) + 1 ;send hack, p i to q ; statep := activeendIp : { statep = active }begin p := p + 1 ; statep := passive ;if unackp = 0 then (* p переходит в состояние quite *)begin qtp := p ; send htok, p , qtp , pi to Nextp endendAp : { Подтверждение hack, i достигло p }begin receive hack, i ; p := max( p , ) + 1 ;unackp := unackp − 1 ;if unackp = 0 and statep = passive then (* p переходит в quiet *)begin qtp := p ; send htok, p , qtp , pi to Nextp endendTp : { Маркер htok, , qt, qi достиг p }begin receive htok, , qt, qi ; p := max( p , ) + 1 ;if quiet(p) thenif p = q then Announceelse if qt > qtp then send htok, p , qt, qi to NextpendАлгоритм 8.10.
Алгоритм РаныКак и для решений из раздела 8.3.3, в основу решения Раны положен локальный предикат quiet(p), определенный для каждого процесса p так, чтоstatep = passive ∧∧ никакое базовое сообщение, отправленное p,не пребывает на этапе пересылки,319Всякий процесс, не пребывающий в состоянии quiet, не реагирует на сообщенияволны, тем самым эффективно гася саму волну.В отличие от решений, предложенных в разделе 8.5.3, взаимодействие волныс процессом p не оказывает влияния на переменные процесса p, используемыедля обнаружения завершения вычисления.
(Взаимодействие с волной может повлиять на переменные самого волнового алгоритма, а также, в случае использования логических часов Лампорта, на часы процесса.) Вследствие этого правильность работы нашего алгоритма не нарушается при параллельном распространении нескольких волн.Алгоритм Раны — это децентрализованный алгоритм; каждый процесс выполняет один и тот же алгоритм обнаружения завершения вычисления. Децентрализованный алгоритм может быть также получен и в том случае, если снабдитьпроцедуру из раздела 8.3.4 децентрализованным волновым алгоритмом. То решение, которое было предложено Раной, позволяет процессам инициировать ихсобственные волны, распространяемые параллельно.Процесс p, перейдя в состояние quiet, сохраняет в памяти тот момент времени qtp , когда произошло это событие, и запускает волну, чтобы проверить, всели процессы уже перешли в состояние quiet к моменту времени qt p .
Если этотак, то завершение вычисления считается обнаруженным. В противном случаесуществует процесс, который перейдет в состояние quiet позже, и он запуститновую волну. Именно по такому принципу устроен алгоритм 8.10, в котором используются логические часы Лампорта, а в качестве волнового алгоритма выбранкольцевой алгоритм.Теорема 8.12. Алгоритм Раны (алгоритм 8.10) является корректнымалгоритмом обнаружения завершения вычислений.Д о к а з а т е л ь с т в о. Чтобы обосновать необходимое условие корректности, предположим, что для конфигурации выполняется условие term, где aподтверждений все еще пребывают на этапе пересылки.
Начиная с этого моментавыполняются только действия Ap и Tp . Коль скоро выполнение каждого действияAp приводит к сокращению на единицу числа сообщений hack, i, пребывающихна этапе пересылки, может быть совершено лишь конечное число таких шагов.Каждый процесс переходит в состояние quiet самое большее один раз; следовательно, маркеры порождаются не более N раз, и каждый маркер передается неболее N раз.
Таким образом, спустя a + N 2 шагов алгоритм обнаружения завершения вычисления достигает заключительной конфигурации , в которой все ещевыполняется условие term.Обозначим символом p0 процесс, у которого показатель времени qt в конфигурации является максимальным, т. е. в заключительной конфигурации длякаждого процесса p выполняется неравенство qt p0 > qtp .
Когда процесс p0 пребывал в состоянии quiet в последний раз (т. е. в момент времени qt p0), он отправил маркер htok, qtp0 , qtp0 , p0 i. Этот маркер совершил полный обход по кольцуи был возвращен процессу p0 . Действительно, каждый процесс p в тот момент,когда к нему попал маркер, должен был пребывать в состоянии quiet и при этомдолжно было выполняться неравенство qtp 6 qtp0 . Если бы это было не так, тоquiet(p) =⇒8.4. Прочие решенияоткуда следует импликация (∀p quiet(p)) =⇒ term.
Как и ранее, условие quietопределяется следующим соотношениемquiet(p) ≡ (statep = passive ∧ unackp = 0).Цель алгоритма — проверить, верно ли, что в определенный момент времени t всепроцессы удовлетворяют условию quiet. Отсюда следует, что в момент времениt вычисление завершилось. Это осуществляется при помощи волны, по ходу которой каждому процессу задается вопрос о том, достиг ли этот процесс в данныймомент состояния quiet и будет ли он оставаться в этом состоянии в дальнейшем.320Гл. 8.
Обнаружение завершенияпроцесс p по получении маркера пришлось бы установить на своих часах значение, превышающее qtp0 , и перейти в состояние quiet позже, нежели это довелосьпроцессу p0 , вопреки нашему выбору процесса p0 . Когда маркер был возвращенпроцессу p0 , этот процесс все еще пребывал в состоянии quiet и поэтому вызвалпроцедуру Announce.Чтобы обосновать достаточное условие корректности рассматриваемого алгоритма, предположим, что процесс p0 вызывает процедуру Announce. Это происходит, когда p0 пребывает в состоянии quiet и получает назад свой маркерhtok, , qt, p0 i, который был переправлен ему поочередно всеми процессами.Проведем доказательство от противного.
Допустим, что условие term не соблюдается в тот момент, когда процесс p0 обнаруживает завершение вычисления; этоозначает, что имеется процесс p, который не удовлетворяет условию quiet. В таком случае процесс p перестал удовлетворять условию quiet уже после того,как расстался с маркером, выпущенным процессом p 0 ; ведь p должен был пребывать в состоянии quiet, когда передавал этот маркер. Пусть q — первый процесс, который перестал удовлетворять условию quiet после передачи маркераhtok, , qt, p0 i.
Это означает, что процесс q был активизирован в результате получения сообщения от некоторого процесса r, который еще не участвовал в передаче маркера, выпущенного процессом p0 , ибо в противном случае процесс rперестал бы удовлетворять условию quiet после передачи этого маркера, но дотого, как этому условию перестал удовлетворять процесс q, вопреки выбору q.Теперь после передачи указанного маркера неравенство q > qtp0 будет по-прежнему соблюдаться. Отсюда следует, что в подтверждении, отправленном процессом q процессу r в ответ на сообщение, которое вывело q из состояния quiet,стоит метка времени 0 > qtp0 . Таким образом, когда r перейдет в состояние quietпосле получения этого подтверждения, будет выполняться неравенство r > qtp0 ,и поэтому в тот момент, когда процессу r вручат маркер, будет выполняться соотношение qtr > p0 .
Согласно описанию алгоритма процесс r не станет передаватьмаркер, вопреки тому, что маркер совершил полный обход по кругу.Доказательство корректности, опирающееся на инварианты и функцию нормирования, предложено в работе ван Везеля [200] . Модификация рассмотренного алгоритма, не зависящая от кольцевой топологии, предложена в работе Хуана [109] .8.5. Упражнения к главе 88.5.1Упражнение 8.1. Опишите активные и пассивные состояния алгоритма A.2.Где можно найти эти состояния в алгоритме A.1?8.5.2Сложность по времени алгоритма обнаружения завершения вычисленийопределяется количеством единиц времени, которое разделяют в худшем слу-8.5. Упражнения к главе 8321чае (при идеализированных допущениях, указанных в определении 6.31) моментзавершения базового вычисления и момент вызова процедуры Announce.Упражнение 8.2.
Какова сложность по времени алгоритма Дейкстры —Шолтена?Упражнение 8.3. Алгоритм Шави—Франчеза применяется к произвольнойсети с уникальными отличительными признаками процессов, а для того, чтобыуменьшить издержки, связанные с передачей контрольных сообщений, в качестве волнового алгоритма используется алгоритм Галладжера —Хамблета—Спиры. Сложность по времени обнаружения завершения вычисления составляет величину Ω (N log N).Можно ли уменьшить эту оценку сложности по времени до величины O(N) засчет дополнительного обмена O(N) контрольными сообщениями?8.5.3Упражнение 8.4. Почему предикат P0 , используемый при описании алгоритма Дейкстры—Фейджена—ван Гастерена, не опровергается, когда процессpj активизируется процессом pi так, что j 6 t или i > t?Упражнение 8.5.
Покажите, что для всякого m существует такое базовоевычисление, в котором происходит обмен m базовыми сообщениями, и при этомалгоритм Дейкстры–Фейджена–ван Гастерена совершает обмен m · (N − 1) контрольными сообщениями.8.5.4Упражнение 8.6. Какие изменения следует внести в алгоритм 8.9, чтобыприменить правило 5a из алгоритма возвращения кредита, вместо правила 5b?Упражнение 8.7. В алгоритме Раны предполагается, что процессы наделеныотличительными признаками. Предположим теперь, что все процессы анонимны, но обладают возможностью отправлять сообщения своим последователям покольцу, и при этом число процессов заранее известно. Внесите в алгоритм 8.10необходимые изменения, позволяющие ему работать в рамках таких допущений.Упражнение 8.8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
