Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 82
Текст из файла (страница 82)
Алгоритм 8 .8 является корректным алгоритмом обнаружения завершения вычислений с асинхронным обменом сообщениями.Д о к а з а т е л ь с т в о . Завершение вычисления объявляется в том случае,когда процесс ро удовлетворяет условию quiet и владеет маркером, окрашеннымв цвет white. Отсюда следует, что условия Р2 и Pi не выполняются, и, значит,верна формула РаРРьАРо- Из этой формулы можно заключить, принимая во внимание условие quiet(po), что все процессы также удовлетворяют условию quiet,и, следовательно, предикат term истинен.Когда завершается базовое вычисление, спустя некоторое время будут получены все подтверждения и все процессы будут удовлетворять условию quiet.Первая же волна, запущенная после того, как условие quiet будет выполнено длявсех процессов, завершится, окрасив все процессы в цвет white, и завершениебазового вычисления будет объявлено по окончании следующей волны.□Решение, основанное на ограниченной задержке передачи сообщений.В [187, §4.1.3] описан один подход к решению задачи обнаружения завершения вычисления (а также целого ряда других задач), в основу которого положено допущение о том, что задержка передачи сообщений ограничена некоторойконстантой р (см.
также §3.3.2). В таком случае всякий процесс остается возбужденным на протяжении интервала времени, длительность которого равна р,после отправления самого последнего сообщения, и при этом процесс остается окрашенным в цвет black, до тех пор пока он возбужден, подобно тому какэто было описано выше для решения задачи с использованием подтверждений.312Гл. 8. Обнаружение завершенияПроцесс р перестает быть возбужденным, если (1) самое последнее отправлениесообщения этот процесс осуществил не менее pi единиц времени тому назад, и (2 )этот процесс является пассивным. Мы предоставляем читателю самостоятельнопровести полное формальное построение алгоритма.8.3.4.
Обнаружение завершения вычислений при помощиволнДо сих пор в этом параграфе мы обсуждали алгоритмы обнаружения завершения вычислений, в которых для передачи контрольных сообщений использовались кольцевые структуры; в основу этих алгоритмов были положены волновые алгоритмы для колец. Аналогичные решения были предложены и для другихтопологий. Так, например, Франчез и Роде в работе [8 8 ], а также Топор в работе [193] разработали алгоритм, в котором для передачи контрольных сообщенийиспользуется остовное дерево.
Тян и Ван Ливен (см [181]) построили децентрализованное решение для кольцевых сетей, древесных сетей, а также для сетейпроизвольной топологии. Внимательное изучение этих решений показывает, чтовсе они очень похожи друг на друга, и отличие проявляется лишь в тех волновыхалгоритмах, на которых основываются эти решения.В данном параграфе мы приведем набросок общего метода построения алгоритма обнаружения завершения вычисления (вместе с его инвариантом), в основу которого положен произвольный, а не специальный (например, кольцевой)волновой алгоритм.
Для каждой волны первое событие отправления процессомсообщения по ходу этой волны или принятия им решения мы будем называть посещением волной указанного процесса. Предполагается, что в случае необходимости процесс может отложить посещение, пока не будут выполнены некоторыелокальные условия. Последующие события, связанные с прохождением той жесамой волны через указанный процесс уже никогда не откладываются.В этом параграфе мы проведем построение алгоритма только для случая синхронного обмена базовыми сообщениями, как это было осуществлено в §8.3.1.Наше построение можно обобщить на случай асинхронного обмена сообщениями,подобно тому, как это было сделано в §§8.3.2 и 8.3.3.Инвариант нашего алгоритма должен позволять обнаруживать завершениевычисления, когда волна принимает решение. Поэтому в качестве первого приближения мы полагаем Р = Ро, гдеРо = все посещенные процессы пассивны.Действительно, коль скоро к моменту принятия решения были посещены все процессы, это требование позволяет обнаружить завершение вычисления в том случае, когда волна принимает решение.
Но требование Ро, кроме того, соблюдаетсяи в том случае, когда волна запускается (и ни один процесс еще не посещен).Условие Pq сохраняется в ходе работы волнового алгоритма, если принять вовнимание следующее правило.Правило 1. Волна посещает только пассивные процессы.8.3. Решения на основе волновых алгоритмов313К сожалению, Ро будет опровергнуто, когда процесс, посещенный волной,активизируется другим процессом, который волна еще не посетила.
Поэтомукаждый процесс снабжается окраской и требование Р замещается ослабленнымусловием (Р0 V Pi), гдеPi = имеется процесс цвета black, который еще не был посещен.Ослабленный инвариант сохраняется при выполнении следующего правила.Правило 2. Процесс, отправивший базовое сообщение, приобретает окраскуblack.Но даже и это условие может быть опровергнуто по ходу движения волны,если она посетила единственный ранее не посещенный процесс цвета black.
Чтобы найти выход из положения, нужно еще более ослабить требование Р. Каждыйпроцесс будет придавать волне окраску white или black. Волна преобразуетсятаким образом, чтобы по ходу ее движения определялась самая темная из приданных ей окрасок; здесь следует напомнить, что волновые алгоритмы способнывычислять точные нижние грани, и в качестве таковой рассматривается «самаятемная окраска». Когда волна принимает решение, определяется самая темнаяиз всех приданных ей окрасок. Это будет окраска white, если все процессы придали волне окраску white, и окраска black, если хотя бы один процесс привнесв волну окраску black.
Мы будем полагать, что волна по ходу своего движенияимеет окраску white, если ни один процесс еще не привнес в нее окраску black',если же хотя бы одни процесс привнес в волну окраску black, то и вся волнабудет иметь цвет black. Таким образом, всякий процесс после посещения еговолной либо привносит в волну окраску white, сохраняя ее цвет неизменным,либо привносит окраску black и окрашивает тем самым всю волну в цвет black.Требование Р замещается еще более ослабленным условием (Ро V Р\ V Рг),гдеРг = волна имеет окраску black.Это условие сохраняется при выполнении Это условие сохраняется при выполнении следующего правила.Правило 3. Всякий процесс, который посетила волна, придает волне своютекущую окраску.И действительно, обмен базовыми сообщениями, равно как и действия, связанные с прохождением волны, сохраняют указанное условие, и оно, таким образом, становится инвариантом.
Волна оканчивается безрезультатно, если процессы, принимающие решения, находят, что волна окрашена в цвет black. Нов таком случае просто запускается очередная волна. Эта новая волна можетпривести к успеху только тогда, когда процессы приобретут окраску white, а этослучится сразу после того, как их посетит эта волна.Правило 4. Процесс, принявший решение в том случае, когда волна имелаокраску black, запускает новую волну.Правило 5. Каждый процесс приобретает окраску white сразу после того,как его посетила очередная волна.314Гл. 8. Обнаружение завершенияЭти правила позволяют гарантировать, что рано или поздно после завершения базового вычисления прохождение очередной волны будет успешным.
Действительно, если базовое вычисление завершилось, то первая волна, запущеннаяпосле этого завершения вычисления, окрасит все процессы в цвет white и следующая за ней волна успешно завершится.В этом алгоритме в каждый момент времени может распространяться толькоодна волна. Если две волны, назовем их А и В, распространяются параллельно,то «побелка» процесса волной В может нарушить инвариант для волны А. Поэтому если возникает необходимость в децентрализованном алгоритме обнаружениязавершения вычисления, то децентрализованный волновой алгоритм должен бытьприменен так, чтобы все инициаторы алгоритма обнаружения работали совместнонад одной и той же волной. Можно воспользоваться также и другим принципомобнаружения, согласно которому разные волны могут вычисляться параллельно,не вызывая нарушений в правильной работе алгоритма обнаружения завершениявычислений (см.
§8.4.2).8.4. Прочие решенияВ этом параграфе мы обсудим два других метода решения задачи обнаружениязавершения вычислений: алгоритм возвращения кредита и алгоритм штемпелявремени.8.4.1. Алгоритм возвращения кредитаВ статье [142] Маттерн предложил алгоритм, позволяющий обнаруживатьзавершение вычисления очень быстро, точнее говоря, спустя не более одной единицы времени, после того как это случилось (принимая во внимание идеализированные допущения о времени, представленные в определении 6.31).
Алгоритмобнаруживает завершение централизованного вычисления при условии, что каждый процесс способен отправить сообщение непосредственно самому инициаторувычисления (т. е., сеть содержит подграф, имеющий форму звезды, в центре которой расположен инициатор).В этом алгоритме каждому сообщению и каждому процессу вручается некоторый кредит ; его значением служит вещественное число, расположенное междуОи 1 (включительно). Алгоритм стремится сохранить инвариантность следующихутверждений.5 1. Суммарный кредит, выданный сообщениям и процессам, равен 1.52. Всякому базовому сообщению вручается положительный кредит.53. Всякому активному процессу вручается положительный кредит.Процессы, имеющие положительный кредит и не подпадающие под перечисленные законы (т. е. пассивные процессы), возвращают кредит инициатору.
Инициатор поступает подобно банку и собирает все кредиты, которые ему отправляют,в переменной ret (возвращенные кредиты).Когда инициатор владеет всеми кредитами, из требований, предписывающихактивным процессам и базовым сообщениям обладать положительным креди8.4. Прочие решения315том, следует, что таковые процессы и сообщения отсутствуют. Следовательно,предикат term будет истинен.Правило 1.
Если ret = 1, то инициатор вызывает процедуру Announce.Чтобы выполнялось необходимое условие корректности, нужно обеспечитьвозвращение всех кредитов инициатору по завершении базового вычисления.Если базовое вычисление завершилось, то никаких базовых сообщений уже нети нам нужно разобраться с теми кредитами, которыми обладают процессы.Правило 2. Как только процесс становится пассивным, он отправляет свойкредит инициатору.var statepcredpret: (active, passive) init if p = po then active else passive ;: fractioninit if p = po then 1 else 0 ;: fractioninit 0 ; for po onlySp: { statep = active } (* Правило 3 *)begin send (mes, credp/2 ) ; credp := credp/2 endRp: { сообщение (mes, с) поступило процессу p }begin receive (mes, c) ; statep := active ;credp ■= credp + с (* Правила 4 и 5b *)endIp\ { statep = active )begin statep := passive ;send (ret, credp) to po ; credp := 0end(* Правило 2 *)APo: { Сообщение (ret, с) поступило процессу po }begin receive (ret, c) ; ret := ret + c ;if ret = 1 then Announce (* Правило 1 *)endАлгоритм 8.9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
