Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 21
Текст из файла (страница 21)
Выполнение, диаграмма которого изображена нарис. 2.1, содержит конфигурацию , в которой оба сообщения, отправленныепри осуществлении событий e и l, пребывают на этапе пересылки одновременно.А выполнение, диаграмма которого изображена на рис.
2.2, не содержит ни од-72Гл. 2. Модельp1p2p3p4F̄a.r..B..B. Bf. BN.r. .. .. .. ... .. .. .. .. ..r .ra fg.r..........rgh.r. j.J. J. ^..r. .. .. .. .. ..r .rh jb.r.Z.d. ZZ.r. ~......... k ... .r .. . .. . .. . .. .. . .. . ..r .r .rb k di.r..l.r ... .. .. .. ... ..r .rl i2.3. Причинно-следственный порядок событий и логические часыc.r..e.r ... .. .. ..
.. .. .. .. .. .. .. .. ..r .re cРис. 2.2. Пространственно-временная диаграмма, эквивалентная диаграмме,изображенной на рис. 2.1.ной такой конфигурации, поскольку сообщение, отправленное при осуществлениисобытия l, достигает адресата раньше, чем происходит событие e.Сторонний наблюдатель, который имеет возможность видеть подлинную последовательность событий, способен отличить одно эквивалентное выполнениеот другого, т. е. он всякий раз видит только одно из возможных выполнений. Однако процессы не могут отличить два эквивалентных выполнения, так как с точкизрения процессов невозможно понять, какое из двух эквивалентных выполненийпроисходит на самом деле.
Это можно объяснить на следующем примере. Предположим, что нужно выяснить, действительно ли сообщения, отправленные приосуществлении событий e и l, пребывают на этапе пересылки одновременно. Заведем в одном из процессов булеву переменную sim, значение которой положимравным true, если сообщения пребывают на этапе пересылки одновременно, иравным false в противном случае. Тогда в последней конфигурации выполнения,изображенного на рис.
2.1, значение переменной sim должно быть равно true,а в последней конфигурации выполнения, изображенного на рис. 2.2, значениепеременной sim должно быть равно false. Но по теореме 2.21 эти конфигурации должны быть эквивалентны, и поэтому ожидаемого присваивания значенийпеременной sim достичь невозможно.Класс эквивалентности выполнений по отношению эквивалентности ∼ однозначно определяется множеством событий и действующим на нем причинноследственным порядком; эти классы эквивалентности называются вычислениямиалгоритма.Определение 2.22. Вычислением распределенного алгоритма называетсякласс эквивалентности выполнений алгоритма по отношению эквивалентности ∼.Нет смысла говорить о конфигурациях вычисления, потому что различныевыполнения одного и того же вычисления могут иметь разные конфигурации. Нопри этом имеет смысл говорить о совокупности событий вычисления, так как вовсех выполнениях одного и того вычисления происходят одни и те же события.Причинно-следственный порядок на множестве событий также однозначно опре-73деляется вычислением.
Мы будем называть вычисление конечным, если конечныего выполнения. Все выполнения одного и того же вычисления начинаются изодной и той же конфигурации и завершаются, если вычисление конечно, в однойи той же конфигурации (см. теорему 2.21); эти конфигурации называются начальной и заключительной конфигурациями вычисления. Мы будем отождествлятьвычисление с частично упорядоченным множеством событий, которые происходят в нем.Как следует из теории частично упорядоченных множеств, два параллельныхсобытия одного и того же вычисления могут происходить в произвольном порядке.Утверждение 2.23. Пусть (X, <) — частично упорядоченное множество и для двух элементов a, b ∈ X выполняется соотношение b 6< a. Тогдасуществует такая линеаризация < l частичного порядка <, для которойвыполняется соотношение a < l b.Это означает, что если a и b — параллельные события вычисления C, то существуют два таких выполнения Ea и Eb этого вычисления, в одном из которыхсобытие a происходит раньше события b, а в другом, наоборот, событие b происходит раньше события a.
Процессам же по ходу выполнения неведомо, какоеиз этих двух событий происходит первым.Синхронный обмен сообщениями. Модифицированный вариант теоремы 2.19можно сформулировать и для систем с синхронным обменом сообщениями. Какутверждается в этой теореме, в таких системах два последовательно произошедших события будут независимыми, если они затрагивают разные процессы.Теорема 2.24. Предположим, что — конфигурация распределеннойсистемы с синхронным обменом сообщениями, и пусть e1 — синхронныйпереход в процессах p и q, а e2 — синхронный переход в процессах r и s,отличных от p и q, и при этом оба события e1 и e2 допустимы в конфигурации .
Тогда переход e1 допустим в конфигурации e2 ( ), переход e2допустим в конфигурации e1 ( ) и при этом e1 (e2 ( )) = e2 (e1 ( )).Доказательство этой теоремы, в котором можно использовать те же рассуждения, что в доказательстве теоремы 2.19, оставлено читателям в качествеупражнения (см. упражнение 2.9). Понятие причинно-следственной зависимостив синхронных системах можно определить подобно тому, как это было сделанов определении 2.20; заинтересованные читатели могут обратиться к работе [48] .Теорема, аналогичная теореме 2.21, будет также справедлива для синхронныхсистем.Выполнения и вычисления. По ходу изложения мы вначале ввели понятие выполнения как пути в системе переходов и лишь затем ввели понятие вычисления как класса эквивалентности на множестве выполнений.
Такой порядок расположения материала соответствует операционной точке зрения на функционирование распределенных систем. Во многих других работах предпочтениеотдается более формальному подходу, при котором вначале определяется поня-Гл. 2. Модельvarp: integerinit 0 ;(* Внутреннее событие *)p := p + 1 ;Изменение состояния(* Событие отправления сообщения *)p := p + 1 ;send (messg, p) ; Изменение состояния(* Событие приема сообщения *)receive (messg, ) ; p := max( p , ) + 1 ;Изменение состоянияАлгоритм 2.3. Логические часы ЛампортаДалее мы рассмотрим и обсудим некоторые примеры таких часов.1.
Последовательное упорядочение. Для выполнения E, представленногов виде последовательности событий (e0 , e1 , e2 , . . .), положим Θg (ei) = i. Такимобразом, каждое событие помечается порядковым номером, которое оно имеетв этой последовательности.Такой функцией может воспользоваться сторонний наблюдатель системы, который может наблюдать последовательность происходящих событий. Однако этупоследовательность нельзя наблюдать, пребывая внутри системы; иначе говоря, распределенный алгоритм не способен вычислять функцию Θ g .
Это следуетиз теоремы 2.19. Предположим, что какой-то распределенный алгоритм записывает значение Θg (ei) = i для одного из тех событий ei , которые фигурируютв предпосылке теоремы. Рассмотрим теперь эквивалентное выполнение, в котором изменен порядок осуществления двух событий; хотя значение функции Θ gизменилось, процесс будет записывать то же самое значение i. Иными словами,функция Θg определена на множестве выполнений, а не вычислений.2. Часы реального времени. Можно расширить модель, рассматриваемуюнами в этой главе, снабдив каждый ее процесс встроенным часовым механизмом.Итак, для каждого события можно зафиксировать время его осуществления, ивычисляемые таким образом значения удовлетворяют определению часов.Распределенные системы с часами реального времени не подпадают под определение 2.6, потому что физические свойства часов позволяют синхронизироватьизменения состояний в разных процессах.
Течение времени происходит во всехпроцессах, и это приводит к тому, что возникают переходы, которые изменяютсостояния (а именно показания часов) во всех процессах системы. Оказывается,эти «глобальные переходы» решительным образом изменяют всю модель: еслипредполагать наличие часов реального времени, то теорема 2.19 перестает бытьa ≺ b =⇒ Θ (a) < Θ (b).Действительно, если a ≺ b, то эту последовательность можно продолжить так,чтобы выполнялось соотношение ΘL (a) < ΘL (b). Значение ΘL для каждого события может быть вычислено распределенным алгоритмом по следующим правилам:а) если a — это внутреннее событие процесса или событие отправления сообщения, и a0 — это предшествующее событие в том же самом процессе,то ΘL (a) = ΘL (a0) + 1;б) если a — событие приема сообщения, a0 — предшествующее событие в томже самом процессе, и b — событие отправления сообщения, соответствующее a, то ΘL (a) = max(ΘL (a0), ΘL (b) ) + 1.Значение ΘL (a0) полагается равным 0, если a — первое событие в процессе.Чтобы распределенный алгоритм мог вычислять показания часов, часовая отметка последнего события, произошедшего в процессе p, записывается в переменную p (ее начальное значение равно 0).
Чтобы вычислить часовую отметкусобытия приема, каждое сообщение m снабжается часовой отметкой m событияотправления этого сообщения e. Показания логических часов Лампорта вычисляются алгоритмом 2.3. Для события e в процессе p значение Θ L (e) равно величинеp сразу после осуществления события e, т. е.
в тот момент, когда происходит изменение состояния в процессе. В качестве упражнения читателям предлагаетсядоказать, что введенная таким образом функция Θ L удовлетворяет определениючасов.Определение 2.25. Часами назовем всякую функцию Θ, отображающуюмножество событий в некоторое упорядоченное множество так, что при этом выполняется соотношениеe1 ≺ e2 ≺ .
. . ≺ ek = a.Мы можем снабдить распределенные системы часами, при помощи которыхможно «отсчитывать» причинно-следственную зависимость, подобно тому какфизические часы отсчитывают реальное время. В этом параграфе букву Θ будем использовать для обозначения функции, отображающей множество событийв некоторое упорядоченное множество (X, <).2.3.3. Логические часы75справедливой. Однако распределенные системы с часами реального времени имеют практическое применение, и мы исследуем их в нашей книге в § 3.3.2 и в гл. 12и 15.3. Логические часы Лампорта. Лампорт в работе [124] предложил использовать часовую функцию, которая приписывает событию a число k, равное длинесамой протяженной последовательности событий (e 1 , . . .
, ek), удовлетворяющейусловиютие вычисления как частично упорядоченного множества событий и лишь затемвводится понятие выполнения как линеаризации этого частично упорядоченного множества. Такому подходу следуют, например, Чаррон-Бост и др. в работе[48] , а также разработчики стандартного языка спецификаций Message SequenceCharts в работе [164] . Эти два подхода совершенно равноправны.2.3. Причинно-следственный порядок событий и логические часы7476Гл. 2. Модель2.4. Дополнительные допущения. СложностьВ алгоритме не оговорены условия отправления сообщения или изменения состояния процесса. Эти часы играют роль вспомогательного механизма, которымможет быть снабжен любой распределенный алгоритм, для того чтобы оцениватьпорядок осуществления событий.4.
Векторные часы. Иногда бывает удобно иметь часы, при помощи которых можно отмечать не только причинно-следственный порядок (как того требуетопределение 2.25), но также и параллелизм. Параллелизм можно зафиксировать,если часовые пометки параллельных событий оказываются несравнимыми; этопроисходит, если в определении 2.25 место импликации занимает эквивалентность и возникает соотношениеa ≺ b ⇐⇒ Θ (a) < Θ (b).(2.1)Существование параллельных событий возможно только тогда, когда областьюзначений X функции часов является множество, которое упорядоченно частично,но не линейно.В векторных часах Маттерна [144] X = NN , т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
