Случай 1: fi - первое событие в р из f, тогда ср – это начальное состояние р. Но тогда fi – также первое событие в р из Е’, что подразумевает, что с – это начальное состояние р. Следовательно, с = ср.
Случай 2: fi – не первое событие в р из f. Пусть последнее событие в р из f перед fi будет fi' = (c’, x’, y’, d’), тогда ср = d’. Но тогда fi' также последнее событие в р перед fi из Е’, что подразумевает, что с = d’. Следовательно, с = ср.
Чтобы показать, что х Í М мы должны помнить, что соответствующие события приема и посылки встречаются в одном порядке и в f и в Е’. Если fi не событие посылки, то х = Æ и х Í М выполняется тривиально. Если fi – это событие посылки, пусть fi будет соответствующим событием посылки. Так как fj í fi , j < i выполняется, т.е., событие посылки предваряет fi в f, следовательно, х Í М.
Мы сейчас показали, что для каждого i, fi применимо в di, и di+1 может быть взято как fi(di). Мы должны, наконец, показать, что последние конфигурации из F и Е совпадают, если Е конечно. Пусть gk будет последней конфигурацией из Е. Если Е’ не содержит события в р, то состояние р в gk равно его начальному состоянию. Так как f также не содержит события в р, то состояние р в dk также равно начальному состоянию, отсюда состояние р в dk равняется его состоянию в gk. Иначе, состояние р в gk есть состояние после последнего события в р из Е’. Это также последнее событие в р из f, так что это также состояние р в dk.
Сообщения в процессе передачи в gk есть такие сообщения, для которых событию посылки нет соответствующего события получения в Е’. Но так как Е’ и f содержат один и тот же набор событий, те же сообщения в процессе передачи в последней конфигурации из F.
Рис. 2.2 Пространственно-временная диаграмма эквивалентная рис. 2.1
Исполнения F и Е имеют один набор событий, и каузальный порядок этих событий – один и тот же для Е и F. Поэтому, также, в этом случае Е – это перестановка событий из F, которая согласуется с каузальным порядком исполнения F. Если применить условие теоремы 2.21, мы можем сказать, что Е и F – эквивалентные исполнения, что обозначается как E ~ F.
Рис. 2.2 показывает временную диаграмму исполнения, эквивалентного исполнению, изображенному на рис. 2.1. Эквивалентные временные диаграммы могут быть получены с помощью «трансформаций резиновой ленты» [Mat89c]. Полагая, что временная ось процесса может быть сжата и растянута пока стрелки сообщений продолжают указывать направо, рис. 2.1 может быть деформирован до рис. 2.2.
Хотя изображенные исполнения эквивалентны и содержат одинаковый набор событий, они не могут содержать одинаковый набор конфигураций. Рис. 2.1 содержит конфигурацию (g”), в которой сообщение, посланное в событии е и сообщение, посланное в событии l, передаются одновременно . Рис. 2.2 не содержит такой конфигурации, потому что сообщение, посланное в событии l, получено перед свершением события е.
Глобальный наблюдатель, кто имеет доступ к действительной последовательности событий, может различать два эквивалентных исполнения, т.е. может наблюдать либо одно, либо другое исполнение. Однако, процессы не могут различать две эквивалентных исполнения, т.к. для них невозможно решить, какое из двух исполнений имеет место. Это иллюстрируется следующим. Предположим, что мы должны решить будут ли посылаться сообщения в событии е и будут в передаче одновременно. Существует булевская переменная sim в одном из процессов, которая должна установлена в истину, если сообщения были в передаче одновременно, и ложь иначе. Таким образом, в последней конфигурации рис. 2.1 значение sim – истина, и в последней конфигурации на рис 2.2 значение – ложь. По теореме 2.21, конфигурации равны, что показывает, что требуемое присваивание sim невозможно.
Класс эквивалентности при отношении ~ полностью характеризуется набором событий и каузальным порядком на этих событиях. Классы эквивалентности называются вычислениями алгоритма.
Определение 2.22 Вычисление распределенного алгоритма – это класс эквивалентности (при ~) исполнений алгоритма.
Не имеет смысла говорить о конфигурациях вычисления, потому что различные исполнения вычисления могут не иметь одних и тех же конфигураций. Имеет смысл говорить о наборе событий вычисления, потому что все исполнения вычисления состоят из одного и того же набора событий. Также, каузальный порядок событий определен для вычисления. Мы будем называть вычисление конечным, если его исполнения конечны. Все исполнения вычисления начинаются в одной конфигурации и, если вычисление конечно, завершаются в одной конфигурации (теорема 2.21). Эти конфигурации называются начальными и конечными конфигурациями вычисления. Мы будем определять вычисление с помощью частично упорядоченного множества событий, принадлежащих ему.
Результат из теории частичных порядков подразумевает, что каждый порядок может встречаться для пары конкурирующих событий вычислений.
Факт 2.23 Пусть (Х, <) будет частичным порядком и а, b Î Х удовлетворяют b ³ a. Существует линейное расширение <1 операции < такое, что а <1 b.
Следовательно, если а и b – конкурирующие события вычисления С, существуют исполнения Еа и Еb этого вычисления такие, что а имеет место раньше, чем b в Еа, и b имеет место раньше, чем а в Еb. Процессы в исполнении не имеют средств, чтобы решить, какое из двух событий произошло раньше.
Синхронная передача сообщений Версия теоремы 2.19 может быть сформулирована также для систем с синхронной передачей сообщений. В таких системах два последовательных событий независимы, если они воздействуют на различные процессы, как сформулировано в следующей теореме.
Теорема 2.24 Пусть g будет конфигурацией распределенной системы с синхронной передачей сообщений и пусть е1 будет переходом процессов р и q, и е2 будет переходом процессов r и s, отличных от р и q, такие, что и е1 и е2 применим в g. Тогда е1 применим в е2(g), е2 применим в е1(g), и е1(е2(g)) = е2(е1(g)).
Доказательство этой теоремы, которое основывается на тех же аргументах, что и доказательство теоремы 2.19, оставлено для упражнения 2.9. Понятие казуальности в синхронных системах может быть определено подобно определению 2.20. Интересующегося читателя можно отослать к [CBMT92]. Теорема 2.21 также имеет своего двойника для синхронных систем.
2.3.3 Логические часы
По аналогии с физическими часами, которые измеряют реальное время, в распределенных вычислениях часы могут быть определены, чтобы выразить каузальность. На протяжении всего этого раздела, Q - функция, действующая из набора событий в упорядоченное множество (Х, <)
Определение 2.25 Часы есть функция Q, действующая из событий на упорядоченное множество такое, что
a í b Þ Q(а) < Q(b).
Далее в этом разделе обсуждаются некоторые примеры часов.
(1) Порядок в последовательности. В исполнении Е, определенном последовательностью событий (е0, е1, е2, …), множество Qg(еi) = i. Таким образом, каждое событие помечается своей позицией в последовательности событий.
Эта функция может использоваться глобальным наблюдателем системы, кто имеет доступ к порядку, в котором происходят события. Однако, невозможно наблюдать этот порядок внутри системы, или, иначе говоря, Qg не может быть вычислена распределенным алгоритмом. Это следствие теоремы 2.19. Предположим, что некоторый распределенный алгоритм сохраняет значение Qg(еi) = i для события еi (что удовлетворяет посылке теоремы). В эквивалентном исполнении, в котором это событие меняется со следующим событием, и следовательно имеет другое значение Qg, то же значение i сохраняется в процессе. Говоря другими словами, Qg определено для исполнений, но не для вычислений.
(2) Часы реального времени. Имеется возможность расширить модель, что является предметом обсуждения этой главы, с помощью снабжения каждого процесса аппаратными часами. Этим путем возможно записывать для каждого события реальное время, в которое оно произошло. Полученные числа удовлетворяют определению часов.
Распределенные системы с часами реального времени не удовлетворяют определению 2.6, потому что физические свойства часов синхронизируют изменения состояний в разных процессах. Время идет во всех процессах, и это порождает переходы, которые меняют состояние (а именно, считыванием часов) всех процессов. Оказывается, что эти «глобальные переходы» ужасно меняют свойства модели. В самом деле, теорема 2.19 больше не действует, если приняты часы реального времени. Распределенные системы с часами реального времени используются на практике, однако, и они будут рассматриваться в этой книге (см. раздел 3.2) и главы 11 и 14.
Алгоритм 2.3 Логические часы Лампорта
(3) Логические часы Лампорта. Лампорт [Lam78] представил часовую функцию, которая приписывает событию а длину k самой длинной последовательности (е1, …, еk) событий, удовлетворяющей
е1 í е2 í … íеk = a
В самом деле, если а í b, эта последовательность может быть расширена, чтобы показать, что QL(a) < QL(b). Значение QL может быть вычислено для каждого события распределенным алгоритмом, базируясь на следующих отношениях.
(а) Если а есть внутреннее событие или событие посылки, и а’ – предыдущее событие в том же процессе, то QL(a) = QL(a’) + 1.
(b) Если а – событие получение, а’ – предыдущее событие в том же процессе, и b –событие посылки, соответствующее а, то QL(a) = max(QL(a’), QL(b)) + 1.
В обоих случаях QL(a’) предполагается нулевым, если а – первое событие в процессе.
Чтобы вычислить значения часов распределенным алгоритмом, значение часов последнего события процесса р сохраняется в переменной qр (инициализируемой в 0). Для того, чтобы вычислить значение часов события получения, каждое сообщение m содержит значение часов qm события е, при котором оно было послано. Логически часы Лампорта даны как алгоритм 2.3. Для события е в процессе р, QL(е) есть значение qр сразу же после появления е, т.е. в момент, когда происходит изменение состояния процесса р. Оставлена для упражнения демонстрация того, что с этим определением QL является часами.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90
