Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 80
Текст из файла (страница 80)
И хотя сложность базового вычисления равна Т (речь идет о сложности по времени), но есливычисление обладает достаточным параллелизмом, то его сложность по числу304Гл. 8. Обнаружение завершениясообщений может оценена величиной Q,{NT). Если параллелизм позволяет каждому процессу отправлять некоторое постоянное число а сообщений за единицувремени, сложность базового вычисления по числу сообщений может достигатьвеличины NTa, т. е. Cl(NT).
Таким образом, количество контрольных сообщений,оцениваемое величиной 0(N-\-T), оказывается тогда гораздо меньшим, чем можнобыло бы ожидать исходя из сложности задачи обнаружения завершения вычисления в наихудшем случае.8.3.2. Подсчет базовых сообщений: алгоритм СафрыСинхронный обмен сообщениями, присущий базовому вычислению валгоритме Дейкстры—Фейджена—ван Гастерена, существенно ограничивает общее применение этого алгоритма. Ряд авторов обобщили указанный алгоритм на случайвычислений с асинхронным обменом сообщениями (см., например, алгоритм 8 .
1 ).В данном параграфе мы обсудим решение Сафры (см. [63]); оно обладает темсвойством, что его сложность в среднем сравнима со сложностью алгоритмаДейкстры—Фейджена—ван Гастерена.Для каждой конфигурации обозначим символом В число сообщений, находящихся на этапе пересылки. Тогда предикат term эквивалентен следующей формуле:(Vp: statep = passive) А В = 0.Разработаем вновь инвариант Р таким образом, чтобы заключение о завершениивычисления можно было вынести на основе Р, равенства t = 0 и некоторойинформации, предоставленной процессом ро. Инвариант должен соблюдаться,когда ро запускает волну, т.
е. при t = N — 1.Чтобы сделать информацию о значении В доступной процессам (хотя быв распределенном виде), снабдим процесс р счетчиком сообщений тср так, чтобыпроцессы придерживались как инварианта условия Р т следующего вида:Рт = В = ^ тср.perИнвариантность условия Рт будет соблюдена, если первоначально полагать тср == 0 для каждого процесса р и потребовать, чтобы все процессы подчинялисьследующему правилу.Правило М. Когда процесс р отправляет сообщение, он увеличивает значение своего счетчика; когда процесс р получает сообщение, он уменьшает значениесвоего счетчика.Такой инвариант должен предоставлять процессу р о возможность принятьрешение о выполнимости условия term , после того как он получит маркер ( t == 0). Так как term теперь включает ограничение, налагаемое на значение В ,мы будем использовать маркер для передачи целого числа q , чтобы суммироватьпоказания счетчиков сообщений всех тех процессов, в которых побывал этотмаркер.
В качестве первого приближения положим Р = Р т A P q , где предикат Р о8.3. Решения на основе волновых алгоритмов305задается следующим образом:(V/ (N > i > 7): statePi = passive ) Л ( q = ^mcPiN>i>tИ действительно, Ро обращается в истину, когда t = N — 1 ив случае t = 0 из условия Р следует утверждение<7= 0, причем(V/ > 0: statePi = passive ) Л (mcPo + q = В).Поэтому ро может обнаружить завершение базового вычисления, если будут выполнены равенства statePo = passive и тсРо + <7 = 0 .Утверждение Ро выполняется, когда процесс ро запускает волну, передаваямаркер процессу p n - \ с пометкой <7 = 0. При передаче маркера утверждение Робудет оставаться верным в том случае, когда в передаче маркера участвуют только пассивные процессы, и при этом к пометке маркера добавляется показаниесчетчика сообщений. Таким образом, мы вводим следующее правило.Правило 1. Только пассивный процесс может работать с маркером, и еслипроцесс передает маркер, то он добавляет к пометке маркера q значение своегосчетчика сообщений.При таком режиме работы условие Р сохраняется как при передаче маркера,так и при выполнении внутренних действий.
К сожалению, Р не сохраняется приполучении сообщения таким процессом pi, для которого i > t. Опровержениепредиката Ро происходит, как только будет получено некоторое сообщение, т. е.это возможно только при условии В > 0. Поскольку до получения этого сообщения утверждение Ро было верно, это означает, что в таком случае должновыполняться условие Р \, которое задается следующим соотношением:Утверждение Р\ остается справедливым и после получения сообщения процессом pi, номер i которого удовлетворяет неравенству / > t; следовательно, болееслабое утверждение Р, которое определяется формулой Рт Л(Р0УР\), сохраняетсвою справедливость и в случае получения сообщения процессом pt, i > t.Уточненное таким образом условие Р тем не менее позволяет процессу рообнаружить завершение базового вычисления по тем же самым признакам: при7 = 0 утверждение Р\ верно лишь при тсРо + q > 0, а это означает, с учетомравенства тсРо + q = 0 (проверку которого требуется провести для обнаружения завершения вычисления), что имеет место -1Р\.
Передача маркера, равно каки отправление базового сообщения, сохраняет предикат Р \ . К сожалению, условие Р\ может быть опровергнуто при получении некоторого сообщения процессомpi, номер / которого удовлетворяет неравенству i ^ 7. Как и в §8.3.1, такую ситуацию можно исправить, снабдив каждый процесс окраской и введя следующееправило.Правило 2.
Процесс-получатель окрашивается в цвет black.306Гл. 8. Обнаружение завершенияvar s t a t e pco lo rpm cp: (a c t i v e , p a s s i v e ) ;: [w h ite , bla ck ) ;: integer init 0 ;{ s ta te p = active }begin send (mes) ;m c p \ = m c p +1(* Rule M *)endRp: { Сообщение (mes) доставлено процессу p }begin receive (mes) ; s t a t e p : = a c t i v e ;m c p := m c p — 1 ;(* Правило M *)c o l o r p := b l a c k(* Правило 2 *)endSp:{ s ta te p = active }begin s t a t e p := p a s s i v e endПриступить к обнаружению завершения вычисления,выполняется один раз процессом р о :begin send (tok, w h i t e , 0) to р ц - i endI p . (* Процесс p обрабатывает маркер (tok, c , q )*){ sta te p = p a ssive )(* Правило 1 *)begin if p = p athen i f [c = w h i t e ) A [ c o l o r p = w h i t e ) A ( m c p + q = 0)then A n n o u n c eelse send (tok, w h i t e , 0) to р ц - i (* Правило 4 *)else if (c o l o r p = w h i t e ) (* Правила 1 и 3 *)then send (tok, c , q + m c p ) to N e x t pelse send (tok, b l a c k , q + m c p ) to N e x t p ,c o l o r p := w h i t e(* Правило 5 *)end\p\Алгоритм 8.7.
Алгоритм СафрыПосле этого заменим прежнее условие Р на новое, которое будет представленоформулой Рт А (Р0 V Pi V Рг), гдеРг = 3/ (/ > / > 0 ) : colorр. = black.Каждое получение сообщения, влекущее за собой опровержение утверждения P i,делает истинным Рг, и поэтому ни одно базовое действие не приводит к опровержению утверждения Р. Поскольку верна импликация (Р A colorРо = white At == 0 ) => —>Рг, новое утверждение оставляет возможность обнаружить завершение вычисления. Это можно сделать, проверив, окрашен ли процесс ро в цветwhite (будучи при этом пассивным), когда он обладает маркером.Ослабленный вариант утверждения Р нельзя опровергнуть в результате выполнения базовых действий; но и его можно опровергнуть, если принять во внимание передачу маркера, например, когда процесс pt, передающий маркер, — этоединственный процесс цвета black.
Спасти ситуацию может дальнейшее ослабление утверждения Р. Мы вновь будем полагать, что маркер также имеет окраску8.3. Решения на основе волновых алгоритмов307(white или black), а само утверждение Р ослабим, приведя его к виду РтА(Ро\/Р\ VP2 VP3 )гдеР 3 = the token is black.При передаче маркера предикат Р 3 остается истинным, если процессы цветаblack передают маркер, также имеющий окраску black.Правило 3. Когда процесс цвета black передает маркер, маркер приобретаетокраску black.Поскольку верна импликация «маркер окрашен в цвет white » =£• - Р 3 ,процесс ро тем не менее способен обнаружить завершение вычисления.
Для этогонужно проверить, верно ли, что этот процесс получил маркер цвета white (будучипри этом пассивным и окрашенным в цвет white).Действительно, теперь можно убедиться, что утверждение Р сохраняет справедливость при выполнении внутренних действий, обмене базовыми сообщениями и при передаче маркера. Прохождение волны не приводит к успеху, еслипри возвращении маркера процессу ро оказывается, что этот маркер окрашен вцвет black, ро окрашен в цвет black или тсРо + <7 ^ 0 .
Если одна волна быланеудачной, то нужно запустить новую.Правило 4. Когда прохождение волны заканчивается неудачно, процесс розапускает новую волну.Очередная волна, впрочем, может оказаться столь же неудачной, как и еепредшественница, если процесс цвета black не будет иметь возможности сменитьсвою окраску на white. И в самом деле, процессы, окрашенные в цвет black, припередаче маркера придают ему ту же окраску, вследствие чего новая волна такжепотерпит неудачу.Обратим внимание на то, что, переменив окраску на white, процесс pi неопровергнет тем самым утверждение Р, если i > t, а само утверждение Р всегда остается истинным, когда ро запускает волну, передавая маркер процессуP- \ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
