Распределенные алгоритмы (стр. 16 из 85)

Определение 2.22 Вычисление распределенного алгоритма – это класс эквивалентности (при ~) исполнений алгоритма.

Не имеет смысла говорить о конфигурациях вычисления, потому что различные исполнения вычисления могут не иметь одних и тех же конфигураций. Имеет смысл говорить о наборе событий вычисления, потому что все исполнения вычисления состоят из одного и того же набора событий. Также, каузальный порядок событий определен для вычисления. Мы будем называть вычисление конечным, если его исполнения конечны. Все исполнения вычисления начинаются в одной конфигурации и, если вычисление конечно, завершаются в одной конфигурации (теорема 2.21). Эти конфигурации называются начальными и конечными конфигурациями вычисления. Мы будем определять вычисление с помощью частично упорядоченного множества событий, принадлежащих ему.

Результат из теории частичных порядков подразумевает, что каждый порядок может встречаться для пары конкурирующих событий вычислений.

Факт 2.23 Пусть (Х, <) будет частичным порядком и а, b Î Х удовлетворяют b ³ a. Существует линейное расширение <₁ операции < такое, что а <₁b.

Следовательно, если а и b – конкурирующие события вычисления С, существуют исполнения Е_а и Е_b этого вычисления такие, что а имеет место раньше, чем b в Е_а, и b имеет место раньше, чем а в Е_b. Процессы в исполнении не имеют средств, чтобы решить, какое из двух событий произошло раньше.

Синхронная передача сообщений Версия теоремы 2.19 может быть сформулирована также для систем с синхронной передачей сообщений. В таких системах два последовательных событий независимы, если они воздействуют на различные процессы, как сформулировано в следующей теореме.

Теорема 2.24 Пусть g будет конфигурацией распределенной системы с синхронной передачей сообщений и пусть е₁ будет переходом процессов р и q, и е₂ будет переходом процессов r и s, отличных от р и q, такие, что и е₁ и е₂ применим в g. Тогда е₁ применим в е₂(g), е₂ применим в е₁(g), и е₁(е₂(g)) = е₂(е₁(g)).

Доказательство этой теоремы, которое основывается на тех же аргументах, что и доказательство теоремы 2.19, оставлено для упражнения 2.9. Понятие казуальности в синхронных системах может быть определено подобно определению 2.20. Интересующегося читателя можно отослать к [CBMT92]. Теорема 2.21 также имеет своего двойника для синхронных систем.

2.3.3 Логические часы

По аналогии с физическими часами, которые измеряют реальное время, в распределенных вычислениях часы могут быть определены, чтобы выразить каузальность. На протяжении всего этого раздела, Q - функция, действующая из набора событий в упорядоченное множество (Х, <)

Определение 2.25 Часы есть функция Q, действующая из событий на упорядоченное множество такое, что

a í b Þ Q(а) < Q(b).

Далее в этом разделе обсуждаются некоторые примеры часов.

(1) Порядок в последовательности. В исполнении Е, определенном последовательностью событий (е₀, е₁, е₂, …), множество Q_g(е_i) = i. Таким образом, каждое событие помечается своей позицией в последовательности событий.

Эта функция может использоваться глобальным наблюдателем системы, кто имеет доступ к порядку, в котором происходят события. Однако, невозможно наблюдать этот порядок внутри системы, или, иначе говоря, Q_g не может быть вычислена распределенным алгоритмом. Это следствие теоремы 2.19. Предположим, что некоторый распределенный алгоритм сохраняет значение Q_g(е_i) = i для события е_i (что удовлетворяет посылке теоремы). В эквивалентном исполнении, в котором это событие меняется со следующим событием, и следовательно имеет другое значение Q_g, то же значение i сохраняется в процессе. Говоря другими словами, Q_g определено для исполнений, но не для вычислений.

(2) Часы реального времени. Имеется возможность расширить модель, что является предметом обсуждения этой главы, с помощью снабжения каждого процесса аппаратными часами. Этим путем возможно записывать для каждого события реальное время, в которое оно произошло. Полученные числа удовлетворяют определению часов.

Распределенные системы с часами реального времени не удовлетворяют определению 2.6, потому что физические свойства часов синхронизируют изменения состояний в разных процессах. Время идет во всех процессах, и это порождает переходы, которые меняют состояние (а именно, считыванием часов) всех процессов. Оказывается, что эти «глобальные переходы» ужасно меняют свойства модели. В самом деле, теорема 2.19 больше не действует, если приняты часы реального времени. Распределенные системы с часами реального времени используются на практике, однако, и они будут рассматриваться в этой книге (см. раздел 3.2) и главы 11 и 14.

Алгоритм 2.3 Логические часы Лампорта

(3) Логические часы Лампорта. Лампорт [Lam78] представил часовую функцию, которая приписывает событию а длину k самой длинной последовательности (е₁, …, е_k) событий, удовлетворяющей

е₁ í е₂ í … íе_k = a

В самом деле, если а í b, эта последовательность может быть расширена, чтобы показать, что Q_L(a) < Q_L(b). Значение Q_L может быть вычислено для каждого события распределенным алгоритмом, базируясь на следующих отношениях.

(а) Если а есть внутреннее событие или событие посылки, и а’ – предыдущее событие в том же процессе, то Q_L(a) = Q_L(a’) + 1.

(b) Если а – событие получение, а’ – предыдущее событие в том же процессе, и b –событие посылки, соответствующее а, то Q_L(a) = max(Q_L(a’), Q_L(b)) + 1.

В обоих случаях Q_L(a’) предполагается нулевым, если а – первое событие в процессе.

Чтобы вычислить значения часов распределенным алгоритмом, значение часов последнего события процесса р сохраняется в переменной q_р (инициализируемой в 0). Для того, чтобы вычислить значение часов события получения, каждое сообщение m содержит значение часов q_m события е, при котором оно было послано. Логически часы Лампорта даны как алгоритм 2.3. Для события е в процессе р, Q_L(е) есть значение q_р сразу же после появления е, т.е. в момент, когда происходит изменение состояния процесса р. Оставлена для упражнения демонстрация того, что с этим определением Q_L является часами.

Не указывается при каких условиях сообщение должно быть послано или как меняется состояние процесса. Часы –это дополнительный механизм, который может быть добавлен к любому распределенному алгоритму, чтобы упорядочивать события.

(4) Векторные часы. Для некоторых целей полезно иметь часы, который выражают не только каузальный порядок (как требуется по определению 2.25), но также и конкуренцию. Конкуренция выражается часами, если конкурентные события помечаются несравнимыми значениями часов, то есть, следствие в определении 2.25 заменяется на эквиваленцию, давая

a í b Û Q(а) < Q(b). (2.1)

Существование конкурирующих событий подразумевает, что область таких часов (множество Х) – не-полностью-упорядоченное множество.

В векторных часах Маттерна [Mat89b] X = N^N, т.е. Q_v(a) есть вектор длины N. Вектора длины n естественным образом упорядочены векторным порядком, определенным следующим образом:

(а₁, …, а_n) £_v (b₁, …, b_n) Û "i (1 £ i £ n) : a_i £ b_i. (2.2)

(Векторный порядок отличается от лексикографического порядка, определенного в упражнении 2.5, последний порядок абсолютен). Часы, определяемые Q_v(a) = (а₁, …, а_N), а_i – это число событий е в процессе р₁, для которого е í а. Как и часы Лампорта, эта функция может быть вычислена распределенным алгоритмом.

Чаррон-Бост [CB89] показал, что невозможно использовать более короткие векторы (с векторным порядком как в (2.2)). Если события произвольного исполнения из N процессов отображаются на вектора длины n таких, что (2.1) удовлетворяется, то n ³ N.

2.4 Дополнительные допущения, сложность

Определений сделанных до сих пор в этой главе достаточно, чтобы развивать оставшиеся главы. Определенная модель служит как основа для представления и проверки алгоритмов, так и для доказательств невозможности для решения распределенных проблем. В различных главах используются дополнительные допущения и нотация, если требуется. Этот раздел обсуждает некоторую терминологию, которая также общеупотребительна в литературе по распределенным алгоритмам. До сих пор, мы моделировали коммуникационную подсистему распределенной системы набором сообщений, находящихся в данный момент в процессе передачи. Далее, мы будем предполагать, что каждое сообщение может передаваться только одним процессом, называемым назначением сообщения. В общем, не обязательно чтобы каждый процесс мог посылать сообщения каждому другому процессу. Вместо этого, для каждого процесса определено подмножество других процессов (называемых соседями процесса), к которым он может посылать сообщения. Если процесс р может посылать сообщения процессу q, говорят, что существует канал от р до q. Если не утверждается обратное, предполагается, что каналы двунаправленные, то есть, тот же канал позволяет посылать q сообщения процессу p. Канал, который осуществляет только однонаправленный трафик от р к q, называется однонаправленным (или направленным) каналом от р до q.