Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 20

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 20)

Тогда достаточнопроверить, что значения / никогда не увеличиваются, зато всегда уменьшаютсяпри выполнении переходов определенного вида.В некоторых случаях мы будем использовать следующий результат, которыйявляется специальным вариантом теоремы 2.17.66Гл. 2. МодельТеорема 2.18. Если S правильно завершает выполнения и при этом су­ществует такое число К, что в каждом выполнении совершается не болееК переходов , то в каждом выполнении существует конфигурация, в ко­торой утверждение Р истинно.2.3. Причинно-следственный порядок событийи логические часыПредставляя выполнение в виде последовательности переходов, мы тем са­мым естественно привносим в модель понятие времени.

Будем говорить, что пере­ход а происходит раньше, чем переход Ь, если в последовательности переходовсобытие а предшествует событию Ь. Сопоставим выполнению Е = (уо, у ь ...)связанную с ним последовательность событий Е = (ео, в\, ...), где е, обознача­ет событие преобразования конфигурации у, в конфигурацию у,+ь Будем иметьв виду, что каждому выполнению таким образом сопоставляется единственнаяпоследовательность событий. Для визуализации выполнения можно использо­вать пространственно-временные диаграммы-, пример одной из таких диа­грамм изображен на рис. 2.1.

В такой диаграмме каждому процессу соответству­ет горизонтальная прямая линия, и каждое событие отмечается точкой на этойпрямой в том месте, где происходит это событие. Если отправление соообщеният происходит при осуществлении события s, а его прием — при осуществлениисобытия г, то в диаграмме проводится дуга из точки s в точку г; в этом случаебудем называть события s и г взаимосвязанными.конфигурация уКак будет показано в §2.3.1, порядок следования событий в распределенномвыполнении может быть изменен так, что это никак не отразится на последую­щих конфигурациях. Поэтому представление о времени как о линейном поряд­ке на множестве событий выполнения не совсем подходит для распределенныхвычислений; вместо этого предлагается воспользоваться отношением причинноследственной зависимости.

Эквивалентность выполнений при изменении поряд­ка следования событий рассматривается в §2.3.2. В §2.3.3 мы обсудим, каким2.3. Причинно-следственный порядок событий и логические часы67образом можно создать такие часы, по которым можно вести отсчет причинноследственной зависимости, а не времени, и приведем один важных примеров ча­сов такого рода — логические часы Лампорта.2.3.1.

Зависимые и независимые событияКак уже отмечалось ранее, переходы в распределенных системах зависяти оказывают влияние только на часть конфигураций. Это наводит на мысль о том,что два последовательно происходящих события, оказывающих воздействие надва множества конфигураций, которые не пересекаются друг с другом, являютсянезависимыми и могут осуществляться в другом порядке. Для систем с асин­хронным обменом сообщениями это наблюдение приводит к следующей теореме.Теорема 2.19. Пусть у — конфигурация распределенной системы (с асин­хронным обменом сообщениями), и пусть ер и eq — события, которые про­исходят в разных процессах р и q, и при этом оба события допустимыв конфигурации у.

Тогда событие ер допустимо в конфигурации eq(y), а со­бытие eq — в конфигурации ер(у) и при этом ep(eq(y)) = eq(ep(y)).Д о к а з а т е л ь с т в о . Чтобы избежать поочередного разбора разных слу­чаев в зависимости от того, с событиями какого типа (внутренними, отправлениясообщения или приема сообщения) мы имеем дело, введем единообразное обо­значение (с, х, у, d) для каждого события.

Здесь символы с и d обозначают со­стояния процесса до осуществления события и после его осуществления, х — этосовокупность сообщений, принятых по ходу осуществления события, a y — этосовокупность сообщений, отправленных при осуществлении этого события. Та­ким образом, внутреннее событие (с, d ) будет обозначаться записью (с, 0 , 0 , d),событие отправления сообщения (с, т, d) — записью (с, 0 , {т}, d), а событиеприема сообщения (с, т, d) — записью (с, {т}, 0 , d). В рамках введенной си­стемы обозначений событие е = (с, х, у, d) процесса р допустимо в конфигурацииу = (сР1, .

. . , ср, ... , cPN, М), если ср = с и х С М. В этом случаее(у) = (сР1, . . . , d, . . . , ( M \ x ) U y ) .Теперь предположим, что события ер = (bp, хр, ур, dp) и е , = (bq, xq, yq, dq)допустимы в конфигурацииУ = (••., ср, . . . , cq, .

. . , М),т. е. ср = Ьр, cq = bq, хр С М и xq С М. Важную роль здесь играет то обстоятель­ство, что множества хр и xq не пересекаются5^; адресатом сообщения хр (еслитаковое имеется) является процесс р, тогда как адресатом сообщения x q (еслитаковое имеется) является процесс q.Рассмотрим конфигурацию ур = ер(у) и заметим, чтоур = (..., dp, .

.., cq, . . . , (М \ хр) U ур ).5Д то следует из замечания в конце §2.1.2. — Прим, перев.Гл. 2. МодельТак как xqCM и xqC\xp = 0, справедливо включение xq С ( M\ x pUyp), и поэтомусобытие eq является допустимым в конфигурации ур. Рассмотрим конфигурациюypq = eq(yp) и заметим, чтоТpq = (• • • >dp, . . . , dq, . . . , ((М \ хр U ур) \ xq) U yq )■Учитывая, что рассматриваемые процессы равноправны, мы можем, применяя теже рассуждения, показать, что событие ер является допустимым в конфигурацииуq = eq(y). Рассмотрим конфигурацию y qp = ep(yq) и заметим, чтоТqp = (• • • >dp, .

.., dq, . . . , ((М \ xq U yq) \ хр U ур))Поскольку М — это мультимножество сообщений и при этом xp Q M и xq С М,справедливо равенство((М \ хр U Ур) \ xq U yq) = ((М \ xq U yq) \ хр U Ур),и поэтому ypq = yqp.□Пусть ер и eq — это два события, которые происходят последовательно в неко­тором выполнении, т. е. для некоторой конфигурации у выполнение содержит под­последовательность. . . , у , ер(у), еч(ер(у)), ...Условия применения теоремы 2.19 не выполняются для событий ер и eq в следу­ющих двух случаях:1) р = q или2) ер — это событие отправления сообщения, a eq — это взаимосвязанноесобытие приема сообщения.Действительно, в этой теореме явно оговорено, что речь идет о разных процессахр и q, и, кроме того, если eq — это событие приема того сообщения, которое былоотправлено при осуществлении события ер, то событие приема сообщения eq неможет быть допустимым в исходной конфигурации у, как того требуют условиятеоремы.

Таким образом, если имеет место одно из двух указанных соотношений,то эти события не могут произойти в другом порядке; в остальных случаях по­рядок, в котором они совершаются, может быть изменен, но в результате будетдостигнута та же самая конфигурация. Заметим, что с глобальной точки зренияпереходы нельзя переставлять, потому что если обратиться к теореме 2.19, топереход из конфигурации ур в конфигурацию ypq отличается от перехода из кон­фигурации у в конфигурацию y q. Однако с точки зрения поведения отдельныхпроцессов эти два события неразличимы.То, что какие-то два события нельзя поменять местами, означает, что междуэтими событиями есть причинно-следственная зависимость. Это отношениеможно распространить на все множество событий выполнения, введя тем самымпричинно-следственное отношение частичного порядка.Определение 2.20.

Пусть задано выполнение Е. Отношением причинноследственного порядка -< называется наименьшее отношение, удовлетворяю­щее следующим условиям:2.3. Причинно-следственный порядок событий и логические часы691) если е и / — два разных события одного и того же процесса и при этомсобытие е происходит прежде события /, то е -< /;2) если s — это событие отправления сообщения, а г — вазаимосвязанноес ним событие приема сообщения, то s -< г;3) Отношение -< обладает свойством транзитивности.Будем использовать запись а ■<b для обозначения отношения, которое опре­делятся формулой (а -< 6 V а = Ь).

Поскольку ■ < является отношением ч а с т и ч ­н о г о порядка, могут найтись события а и Ь, для которых не выполняется а ■<bи b < а . Такие события будем называть п а р а л л е л ь н ы м и и будем использоватьдля обозначения этого факта запись а || Ь. Например, для выполнения, изобра­женного на рис 2.1, имеют место b || /, d || г, и т. п..Причинно-следственный порядок был впервые введен в работе Лампорта[124], и он играет значительную роль при проведении логического анализа рас­пределенных алгоритмов.

Как следует из определения отношения -<, события,связанные причинно-следственной зависимостью, могут образовывать п р и ч и н н о с л е д с т в е н н ы е ц е п о ч к и . Это означает, что выполнимость отношения а -< b пред­полагает существование такой последовательности событий а = во, е \, . .

. , е*. == b, что для каждой пары соседних ее членов выполняется либо п. 1), либоп. 2) определения 2.20. Можно выбрать такую причинно-следственная цепочку,в которой любые два события, удовлетворяющие п. 1), происходят в том про­цессе, к которому они относятся, последовательно, т. е. между ними не проис­ходит никаких событий. Для выполнения, изображенного на рис. 2.1, причинноследственной цепочкой между событием а и событием / может служить после­довательность а, /, g , h , /', k , l.2.3.2.

Эквивалентность выполнений: вычисленияВ этом параграфе мы покажем, что любая перестановка событий в выпол­нении, сохраняющая причинно-следственный порядок, не оказывает влияния нарезультат выполнения. Такая перестановка событий приводит к другой последо­вательности конфигураций, но полученное при этом выполнение будет считатьсяэквивалентным исходному выполнению.Пусть задана последовательность событий / = (/о, /ь /г, ...).

Характеристики

Список файлов книги