Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 19
Текст из файла (страница 19)
Рассмотрим произвольное выполнение E = ( 0 , 1 , 2 , . . .)системы S. Если E — конечная последовательность, то последняя конфигурацияявляется заключительной, и, коль скоро в системе S всегда верно соотношение term =⇒ P, утверждение P выполняется в этой конфигурации. Если выполнение E продолжается бесконечно долго, то выделим в нем самый длинныйначальный отрезок E0 , не содержащий ни одной конфигурации, в которой выполнялось бы утверждение P. Рассмотрим последовательность s = (f( 0), f( 1), . .
.)для всех конфигураций i , содержащихся в E0 . Согласно выбору E0 и в соответствии с определением функции нормировки f последовательность s являетсяубывающей. Коль скоро W — фундированное множество, последовательность sявляется конечной. Это означает также, что E 0 является конечным префиксом( 0 , 1 , . . . , k) выполнения E. Тогда, помятуя о выборе E0 , приходим к заключению о том, что P( k+1) имеет истинное значение.Если в расчет принять свойства справедливости, то доказать, что P наверняка станет истинным, можно исходя из более слабых предпосылок, нежели те,которые фигурируют в теореме 2.17; значения функции нормировки не обязательно должны убывать после каждого перехода. Допущение справедливостиможно использовать для того, чтобы показать, что в бесконечных выполненияхпереходы определенного вида совершаются бесконечно часто. Тогда достаточнопроверить, что значения f никогда не увеличиваются, зато всегда уменьшаютсяпри выполнении переходов определенного вида.В некоторых случаях мы будем использовать следующий результат, которыйявляется специальным вариантом теоремы 2.17.66Гл.
2. Модель2.3. Причинно-следственный порядок событий и логические часыТеорема 2.18. Если S правильно завершает выполнения и при этом существует такое число K, что в каждом выполнении совершается не болееK переходов, то в каждом выполнении существует конфигурация, в которой утверждение P истинно.2.3. Причинно-следственный порядок событийи логические часыp1p2p3p4Ēa b.r .r. .Z.J .d.
. ZZ.r. J. ~. . J f ... .J. . ^..r ... . . .. . . .. .. . . ... . . .. . . .. . .. . . .. . . ..r .r .r .ra b f dg.r..........rgh.r. j.J. J. ^..r. .. .. .. .. ..r .rh jk.r.......rkконфигурацияc.r.>e ...r ... i.. .r.. ...>. l ... .. .r .. ... .
. .. . . .. . . .. . . .. . . ..r .r .r .re l c iПредставляя выполнение в виде последовательности переходов, мы тем самым естественно привносим в модель понятие времени. Будем говорить, что переход a происходит раньше, чем переход b, если в последовательности переходовсобытие a предшествует событию b. Сопоставим выполнению E = ( 0 , 1 , . . .)связанную с ним последовательность событий Ē = (e0 , e1 , . . .), где ei обозначает событие преобразования конфигурации i в конфигурацию i+1 . Будем иметьв виду, что каждому выполнению таким образом сопоставляется единственнаяпоследовательность событий. Для визуализации выполнения можно использовать пространственно-временные диаграммы; пример одной из таких диаграмм изображен на рис.
2.1. В такой диаграмме каждому процессу соответствует горизонтальная прямая линия, и каждое событие отмечается точкой на этойпрямой в том месте, где происходит это событие. Если отправление соообщенияm происходит при осуществлении события s, а его прием — при осуществлениисобытия r, то в диаграмме проводится дуга из точки s в точку r; в этом случаебудем называть события s и r взаимосвязанными.образом можно создать такие часы, по которым можно вести отсчет причинноследственной зависимости, а не времени, и приведем один важных примеров часов такого рода — логические часы Лампорта.2.3.1. Зависимые и независимые событияКак уже отмечалось ранее, переходы в распределенных системах зависяти оказывают влияние только на часть конфигураций. Это наводит на мысль о том,что два последовательно происходящих события, оказывающих воздействие надва множества конфигураций, которые не пересекаются друг с другом, являютсянезависимыми и могут осуществляться в другом порядке.
Для систем с асинхронным обменом сообщениями это наблюдение приводит к следующей теореме.Теорема 2.19. Пусть — конфигурация распределенной системы (с асинхронным обменом сообщениями), и пусть ep и eq — события, которые происходят в разных процессах p и q, и при этом оба события допустимыв конфигурации . Тогда событие ep допустимо в конфигурации eq ( ), а событие eq — в конфигурации ep ( ) и при этом ep (eq ( )) = eq (ep ( )).Д о к а з а т е л ь с т в о.
Чтобы избежать поочередного разбора разных случаев в зависимости от того, с событиями какого типа (внутренними, отправлениясообщения или приема сообщения) мы имеем дело, введем единообразное обозначение (c, x, y, d) для каждого события.
Здесь символы c и d обозначают состояния процесса до осуществления события и после его осуществления, x — этосовокупность сообщений, принятых по ходу осуществления события, а y — этосовокупность сообщений, отправленных при осуществлении этого события. Таким образом, внутреннее событие (c, d) будет обозначаться записью (c, ∅, ∅, d),событие отправления сообщения (c, m, d) — записью (c, ∅, {m}, d), а событиеприема сообщения (c, m, d) — записью (c, {m}, ∅, d). В рамках введенной системы обозначений событие e = (c, x, y, d) процесса p допустимо в конфигурации= (cp1 , .
. . , cp , . . . , cpN , M), если cp = c и x ⊆ M. В этом случаеe( ) = (cp1 , . . . , d, . . . , (M \ x) ∪ y ).Теперь предположим, что события ep = (bp , xp , yp , dp) и eq = (bq , xq , yq , dq)допустимы в конфигурации= (. . . , cp , . . . , cq , . . . , M),Рис. 2.1. Пример пространственно-временной диаграммыКак будет показано в § 2.3.1, порядок следования событий в распределенномвыполнении может быть изменен так, что это никак не отразится на последующих конфигурациях. Поэтому представление о времени как о линейном порядке на множестве событий выполнения не совсем подходит для распределенныхвычислений; вместо этого предлагается воспользоваться отношением причинноследственной зависимости. Эквивалентность выполнений при изменении порядка следования событий рассматривается в § 2.3.2.
В § 2.3.3 мы обсудим, каким67т. е. cp = bp , cq = bq , xp ⊆ M и xq ⊆ M. Важную роль здесь играет то обстоятельство, что множества xp и xq не пересекаются 5) ; адресатом сообщения xp (еслитаковое имеется) является процесс p, тогда как адресатом сообщения x q (еслитаковое имеется) является процесс q.Рассмотрим конфигурацию p = ep ( ) и заметим, чтоp5) Это= (. . . , dp , . . . , cq , . . . , (M \ xp) ∪ yp ).следует из замечания в конце § 2.1.2. — Прим. перев.Гл.
2. Модель= (. . . , dp , . . . , dq , . . . , ((M \ xq ∪ yq) \ xp ∪ yp)).Поскольку M — это мультимножество сообщений и при этом xp ⊆ M и xq ⊆ M,справедливо равенство((M \ xp ∪ yp) \ xq ∪ yq) = ((M \ xq ∪ yq) \ xp ∪ yp),и поэтому pq = qp .Пусть ep и eq — это два события, которые происходят последовательно в некотором выполнении, т.
е. для некоторой конфигурации выполнение содержит подпоследовательность. . . , , ep ( ), eq (ep ( )), . . .Условия применения теоремы 2.19 не выполняются для событий e p и eq в следующих двух случаях:1) p = q или2) ep — это событие отправления сообщения, а eq — это взаимосвязанноесобытие приема сообщения.Действительно, в этой теореме явно оговорено, что речь идет о разных процессахp и q, и, кроме того, если eq — это событие приема того сообщения, которое былоотправлено при осуществлении события ep , то событие приема сообщения eq неможет быть допустимым в исходной конфигурации , как того требуют условиятеоремы. Таким образом, если имеет место одно из двух указанных соотношений,то эти события не могут произойти в другом порядке; в остальных случаях порядок, в котором они совершаются, может быть изменен, но в результате будетдостигнута та же самая конфигурация.
Заметим, что с глобальной точки зренияпереходы нельзя переставлять, потому что если обратиться к теореме 2.19, топереход из конфигурации p в конфигурацию pq отличается от перехода из конфигурации в конфигурацию q . Однако с точки зрения поведения отдельныхпроцессов эти два события неразличимы.То, что какие-то два события нельзя поменять местами, означает, что междуэтими событиями есть причинно-следственная зависимость. Это отношениеможно распространить на все множество событий выполнения, введя тем самымпричинно-следственное отношение частичного порядка.Определение 2.20.
Пусть задано выполнение E. Отношением причинноследственного порядка ≺ называется наименьшее отношение, удовлетворяющее следующим условиям:2.3.2. Эквивалентность выполнений: вычисленияВ этом параграфе мы покажем, что любая перестановка событий в выполнении, сохраняющая причинно-следственный порядок, не оказывает влияния нарезультат выполнения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
