Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 93
Текст из файла (страница 93)
Проведя в режиме off-line анализ конфигурации, «выхваченной» из ошибочного выполнения, можно обнаружить причину,по которой программа ведет себя не так, как этого ожидают.10.1. Начальные сведенияРассмотрим вычисление С распределенной системы, состоящей из некоторого множества процессов Р ; обозначим символом Ev множество событий этоговычисления. Мы будем исходить из допущения слабой справедливости, которое заключается в том, что каждое сообщение будет доставлено по назначениюспустя конечный промежуток времени. Мы будем предполагать также, что сетьявляется сильно связной.
Локальное вычисление процесса р представляет собойпоследовательность c f \ с ^ \ ... состояний процесса, где c f * — это начальноесостояние процесса р. Переход из состояния Cp~v^ в состояние с® обусловленосуществлением события e f в процессе р (см. рис. 10.1). Таким образом, Ev =На множестве событий процесса р введем причинно-следственный порядок при помощи соотношенияКаждое событие может быть событием отправления сообщения, приема сообщения или внутренним событием (соответствующие определения представлены в гл. 2). Для упрощения описания алгоритмов и формулировки теорем мыбудем всегда придерживаться допущения о том, что вся история обмена информацией с процессом определяется его состоянием. Это означает, что если существует канал связи, ведущий из р в q, то состояние с^ процесса р включает в себясписок sentpq сообщений, которые процесс р отправил процессу q при осуществлении событий начиная с еР и оканчивая е^р .
Кроме того, состояние с® процессаq содержит список rcvdpq сообщений, которые процесс q получил от процесса рпри осуществлении событий, начиная с еР и оканчивая е$\ В § 10.3.1 будет показано, как можно устранить это допущение, чтобы избежать явного храненияв памяти историй обмена информацией в приложениях наших алгоритмов.Алгоритм построения моментального состояния системы предназначен дляреконструкции глобальной конфигурации, которая образуется из локальных состояний (моментальных состояний) всех процессов. Процесс р запечатлеваетсвое локальное состояние, записывая в память одно локальное состояние с*,10.1. Начальные сведения353которое называется моментальным локальным состоянием процесса р.
Еслимоментальным локальным состоянием процесса является ср(0 , т. е. р проводит моментальный снимок состояния в промежутке между осуществлением событий е®и е{р+{\ то события е®, для которых / < /, называются предмоментальнымисобытиями процесса р, а те события, для которых / > г, называются постмоментальными событиями процесса р. На временных диаграммах запечатлениелокального состояния процесса будет отмечаться незакрашенным кружком тогосостояния процесса, которое стало его моментальным состоянием (см.
рис 1 0 .1и 1 0 .2 ).----- •'t---------е --------------- • —•Ср1Начальное состояниеРис. 10.1.|•—V "Запечатлениемоментального состоянияВычисление процесса рГлобальное моментальное состояние S* образуется из моментальных состояний Ср всех процессов р, входящих в множество Р. Для обозначения этогомы будем использовать запись S* = (c*pi, . .
. , c*N). Так как локальные состояния включают в себя истории обменов информацией, моментальное состояниеS* определяет конфигурацию у*, если состоянием канала pq считать множествосообщений, отправленных процессом р (согласно состоянию с*), но еще недоставленных процессу q (согласно состоянию с*).
Иными словами, состояниеканала pq в моментальном состоянии S* определяется множеством сообщенийsent*q\rcvd*q. Конфигурацию, состоящую из моментальных состояний процессови определенных таким образом состояний каналов, обозначим символом у*.При построении указанной конфигурации появляются некоторые отклонения,если множество rcvd*q не является подмножеством sent*q (см.
рис 10.2). Судяпо локальному состоянию c*Pl в формируемом моментальном состоянии системы, сообщение было отправлено процессом р\ процессу рз, но, как отмеченов локальном состоянии с*3>никакого сообщения от р\ не было получено. Такимобразом, в данном моментальном состоянии системы канал р\ръ содержит одно сообщение; говорят, что в этом моментальном состоянии системы указанноесообщение пребывает «на этапе пересылки».Обратимся теперь к сообщению, которое процесс р\ отправил процессу р 2 .Отправление этого сообщения относится к числу постмоментальных событий,тогда как его получение является предмоментальным событием.
Значит, в соответствии с состоянием c*Pi никакие сообщения по каналу р\р 2 не отправлялись,тогда как в состоянии с*Р2 отмечено, что по этому каналу было получено некоторое сообщение. Поскольку rcvd*lP2 £sent*lP2, никакого осмысленного состояния‘>По этому каналу. — Прим, перев.354Гл. 10. Моментальные состояния системыканалу р\Р 2 придать нельзя.
Это побуждает нас обратиться к следующему определению.Определение 10.1. Моментальное состояние 5* называется осуществимым, если для всякой пары соседних процессов р и q выполняется включениеrcvd*pq С sent*pq.Осуществимость моментального состояния означает, что при построении соответствующей конфигурации в rcvd*pq не останется ни одного сообщения, котороенельзя удалить из sent*q. Сообщение, отправление которого является предмоментальным (постмоментальным) событием, будем называть предмоментальным(соответственно, постмоментальным) сообщением.Существует взаимнооднозначное соответствие между моментальными состояниями и конечными сечениями на совокупности событий вычисления. Сечениемназывается совокупность событий, замкнутая влево относительно отношения локальной причинно-следственной зависимости.Определение 10.2.
Сечением на множестве Ev называется такое подмножество L С Ev, для которого выполняется соотношениее £ L А е' ~^р ез е' £ L.Сечение Z.2 считается более поздним, чем сечение L\, если верно включениеЕ\ С UС одной стороны, нетрудно видеть, что для каждого моментального состоянияS* совокупность L всех пред-моментальных событий является конечным сечением. Рассмотрим теперь произвольное конечное сечение L. Для каждого процесса р либо ни одно событие, произошедшее в р, не входит в L (в таком случаебудем полагать тр = 0 ), либо в L существует наибольшее событие е'™'^ и приэтом все события е ~<р е'™'^ также содержатся в L. Поэтому L представляет собой в точности множество предмоментальных событий моментального состоянияS mPN)_ (S mrdS* =(С,pi)•l PnМоментальное состояние будет использоваться для извлечения информациио том вычислении, которое оно запечатлевает, но произвольно выбранное моментальное состояние системы дает очень мало информации о таком вычислении.Рассмотрим, например, алгоритм, в основу которого положена передача уникального маркера; к таковым относятся алгоритмы обхода из §6.6.3.
Допустим,что процесс р запечатлел свое состояние, когда он обладал маркером, и спустянекоторое время процесс q также запечатлел свое состояние, когда он, в своюочередь, обладал маркером. В построенной конфигурации два процесса обладаютмаркером, хотя подобной ситуации не может возникнуть ни в одном вычислениинашего алгоритма.Естественно, мы бы предпочли, чтобы алгоритм построения моментальногосостояния реконструировал конфигурацию, которая и «в самом деле» может возникнуть при вычислении. К сожалению, множество реализуемых конфигурацийне является инвариантом отношения эквивалентности, как это показано в § 2.3.2,10.1. Начальные сведения355и поэтому оно не определяется вычислением однозначно.
Таким образом, мы будем считать разумным всякий результат работы алгоритма, если он приводитк построению какой-либо конфигурации, которая окажется возможной для заданного вычисления (т. е. случится в некоторой реализации этого вычисления).Определение 10.3. Моментальное состояние 5* называется значимым в вычислении С, если существует такая реализация Е е С, что у* является конфигурацией Е.Мы будем требовать от алгоритма построения моментального состояния такойкоординации регистрации локальных моментальных состояний, чтобы полученное в результате этого глобальное моментальное состояние оказалось значимым.Своевременность запечатления моментальных состояний обсуждается в § 10.3.2.Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
