Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 95
Текст из файла (страница 95)
Сложность по времени рассмотренного алгоритма составляет величину0(D).10.2.2. Алгоритм Лая—ЯнгаАлгоритм Лая—Янга (см. [122]) не опирается на свойство поддержания очередности сообщений в каналах. Поэтому отделить предмоментальные событияот постмоментальных при помощи маркеров, как это сделано в алгоритме Ченди—Лэмпорта, уже невозможно. Вместо этого каждое базовое сообщение снабжается пометкой, которая позволяет понять, является ли это сообщение предмоментальным или постмоментальным; для этого процесс р, отправляя сообщениепо ходу вычисления С, добавляет к нему значение takenp.
Так как содержаниесообщений, относящихся к вычислению С, не играет здеь никакой роли, мы будемобозначать такие сообщения просто (mes, с), где с — это значение переменной,включенное в состав сообщения процессом-отправителем. Алгоритм построениямоментального состояния проверяет поступающие сообщения и записывает моментальное локальное состояние в том виде, в каком оно было до поступленияпервого постмоментального сообщения (см. алгоритм 10.5).var takenp : boolinit false ;Для запуска алгоритма:begin запомнить локальное состояние; taken := true endДля отправления сообщения по ходу вычисления С:send (mes, takenp)Если поступило сообщение (mes, с);begin receive (mes, с) ;if с and not takenp thenbegin запомнить локальное состояние ; taken := true end;изменить состояние на то, в котором пребывал процесспри получении сообщения в вычислении САлгоритм 10.5.
Алгоритм Лая-Янга построения моментального состояния360Гл. 10. Моментальные состояния системыВ алгоритме 10.5 нет обмена контрольными сообщениями, но он не можетгарантировать того, что каждый процесс рано или поздно запишет свое состояние; на самом деле бывает и так, что этой записи не происходит. Рассмотримпроцесс р , не являющийся инициатором алгоритма построения моментальногосостояния, и предположим, что ни один из соседей процесса р не отправляетпроцессу р сообщений, после того как этот сосед запечатлел свое моментальноелокальное состояние.
В таком случае р никогда не проведет запись своего состояния, и алгоритм построения моментального состояния завершит работу, имеянеполное моментальное состояние.Решение этой проблемы зависит от того, что нам известно о вычислении С;если мы имеем гарантию, что связь с каждым процессом рано или поздно осуществится, то и полное моментальное состояние всегда можно будет запечатлеть.В противном случае алгоритм можно снабдить блоком, проводящим первоначальный обмен контрольными сообщениями между всеми процессами, как и в алгоритме 10.4. Эти сообщения всего лишь гарантируют, что каждый процесс раноили поздно запишет свое состояние (как это установлено в лемме 1 0 .6 ), но онине понадобятся при доказательстве осуществимости построенного моментальногосостояния системы.
Так или иначе, вычисление полного моментального состояниясистемы обеспечено.Теорема 10.8. А л г о р и т м Л а я — Я н г а (а л г о р и т мзн а ч и м ы е м о м ен т а ль н ы е со ст о ян и я сист ем ы .10.5) в ы ч и с л я е тт олькоД о к а з а т е л ь с т в о . Рассмотрим моментальное состяние, вычисленноеалгоритмом, и пусть т = (mes, с) — это постмоментальное сообщение, отправленное процессом р процессу q. Это значит, что с = tr u e , и поэтому q запечатлевает свое состояние таким, каким оно было до получения сообщения т .
Такимобразом, в состоянии, которое записал процесс q , не учитывается поступлениет , и прием сообщения т относится к числу постмоментальных событий. (Следует напомнить, что существенным здесь является то, какое состояние записать,а не то, когда провести эту запись; в нашем случае запись состояния проводитсяодновременно с получением первого постмоментального события.)□Использование подавления (замораживания). В алгоритме Ченди—Лэмпорта (алгоритм 10.4) маркеры используются для отделения предмоментальныхсообщений от постмоментальных, и поэтому в каналах требуется соблюдениеочередности сообщений.
В алгоритме Л ая—Янга (алгоритм 10.5) в базовые сообщения явно вставляется пометка о том, является ли сообщение предмоментальным или постмоментальным, и, следовательно, здесь процессам должна бытьпредоставлена возможность реализовать принцип « о с е д л а й п о р о с е н к а » по отношению к информации, содержащейся в базовом сообщении. Тейлор в работе [186] показал, что если в канале не поддерживается очередность сообщений и «оседлать поросенка» невозможно, всякое решение проблемы построениямоментального состояния системы обязано быть и н г и б и т о р н ы м , т.
е. полученоза счет временного приостановления базового вычисления. Классификация разных типов подавления и описание необходимых средств подавления при различ10.3. Применение алгоритмов построения моментальных состояний361ных допущениях относительно коммуникационной среды представлены в работеКритчлоу и Тейлора [57].10.3. Применение алгоритмов построения моментальныхсостояний10.3.1. Вычисление состояния каналаДо сих пор предполагалось, что состояние каждого процесса включает историю обмена информацией процесса и поэтому состояние всякого канала можновычислить на основе состояний примыкающих к нему процессов.
В большинствеслучаев, однако, хранить в явном виде все сообщения, которые когда-либо отправлял или получал процесс, слишком накладно. Мы покажем здесь, как можновосстанавливать состояние канала более эффективно.Редукция к значимой информации. В зависимости от предназначения моментального состояния системы может оказаться достаточным хранить толькоограниченный объем значимых сведений об истории обмена информацией. Н апример, мы можем вознамериться построить моментальное состояние алгоритма обмена маркерами (наподобие алгоритма Корача—Каттена—Морана), чтобыопределить, сколько маркеров все еще являются активными. Чтобы определитьколичество маркеров в каждом канале, каждому процессу достаточно запоминать, сколько маркеров он отправил и сколько маркеров он получил.
Вторымпримером может служить моментальное состояние системы для проверки завершенности вычисления (см. гл. 8 ). Для этого нужно всего лишь помнить о том, пустканал или нет, а для этого достаточно уметь считать сообщения, а не хранить ихв явном виде. (В обоих примерах при записи состояния каждого процесса можнотакже ограничиться небольшим объемом значимой информации, а именно числом маркеров, которыми обладает процесс, или, соответственно, указанием того,является ли процесс активным или пассивным.)Явное восстановление состояния канала. Состояние канала можно восстановить в явном виде, опираясь на следующую лемму.Лемма 10.9. Если моментальное состояние системы является осуществимым, то sentpg \ rcvd*q образует в точности множество тех сообщений, отправление которых процессом р является предмоментальнымсобытием, а получение этих сообщений процессом q — постмоментальным событием.Д о к а з а т е л ь с т в о .
С одной стороны, нетрудно видеть, что сообщениет € sent*q \ rcvcLpq отправлено предмоментально, а получено постмоментально.А с другой стороны, если сообщение т отправлено предмоментально и полученопостмоментально, то оно по определению включается в sent*pq, но не включаетсяв rcvd*q. Следовательно, такое сообщение принадлежит sent*q \ rcvd*q.□Процесс q восстанавливает состояние канала pq путем записи всех предмоментальных сообщений, которые были получены им постмоментально.
Коль362Гл. 10. Моментальные состояния системыскоро все такие сообщения получены процессом q после запечатления его моментального состояния, q приступает к записи сообщений, после того как он записал свое состяние, и запись прекращается, как только все предмоментальныесообщения будут получены.Алгоритм Ченди—Лэмпорта. Все предмоментальные сообщения от р к qполучены перед тем, как сообщение (mkr) было отправлено процессом р процессу q; даже, более того, только предмоментальные сообщения были получены допоступления маркера. Восстановить состояния канала в таком случае будет чрезвычайно просто: состояние канала pq представляет собой совокупность сообщений, полученных процессом q, после того как он сделал запись своего состояния,но до того, как он получил сообщение (mkr) от процесса р.Алгоритм Лая —Янга. Если в канале не поддерживается очередность сообщений, процесс q может получать предмоменталные и постмоментальные сообщения поочередно; получение постмоментального сообщения не означает, чтовсе предмоментальные сообщения уже были доставлены.
Поэтому, хотя и ясно,какие сообщения должны быть записаны процессом q (только те, которые помечены ярлыком false, являются предмоментальными), непонятно, в какой жемомент этот процесс уже завершил восстановление полного состояния каналаи может прекратить запись.Решение этой проблемы, предложенное Маттерном в работе [144], состоитв том, чтобы заставить процесс р вести подсчет общего числа предмоментальныхсообщений, отправленных им процессу q, и уведомлять q об этом числе (либов отдельном сообщении, либо присоединяя это число к какому-либо постмоментальному сообщению по принципу «оседлать поросенка»).
Процесс q подсчитывает число полученных им предмоментальных сообщений (получение которыхбыло связано как с предмоментальными, так и с постмоментальными событиями) и завершает работу по восстановлению состояния канала, как только будетполучено достаточно большое число предмоментальных сообщений.10.3.2. Своевременность моментальных состояний системыМожно гарантировать, что моментальные состояния системы, которые строятся при помощи алгоритмов, рассмотренных в этой главе, являются значимымив тех вычислениях, для которых они были построены. Но помимо этого нам хотелось бы, чтобы моментальное состояние было «свежим» в том смысле, чтоизвлеченная из такого состояния информация не должна быть слишком устаревшей. Коль скоро для оценки своевременности информации необходимо понятиевремени, мы будем привязывать моментальное состояние системы к конфигурациям, которые возникают при распределенном выполнении.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
