Таненбаум Э. Распределенные системы. Принципы и парадигмы

Подождите немного. Документ загружается.

7.5. Распределенное подтверждение 441

тверждение, сообщение GLOBALCOMMIT

будет

сначала записано в журнал,

по-

том разослано всем процессам. В противном случае координатор разошлет сообще-

ние С10ЛЛ1_ЛБ07?Г (предварительно также записав его в локальный журнал).

В листинге 7.2 приведены действия, осуществляемые участником. В начале

процесс ожидает запроса на голосование от коордрпгатора. Отметим, что это

ожидание выполняется в отдельном потоке выполнения, выполняющемся в ад-

ресном пространстве процесса. Если сообщение не поступает, транзакция просто

прерывается. По всей вероятности, причина отсутствия сообщения состоит в том,

что координатор отказал.

Листинг 7.2. Схема действий, предпринимаемых процессом-участником протокола

2РС

ДЕЙСТВИЯ УЧАСТНИКА:

записать состояние INIT

локальный журнал;

ожидать \/OTE_REQUEST

от

координатора;

если время вышло

{

записать GLOBAL_ABORT

локальный журнал;

выход;

}

если участник голосует

за

COMMIT

{

записать \/0ТЕ_С0ММ1Т

локальный журнал;

послать VOTE_COMMIT координатору;

ожидать решение

от

координатора;

если время вышло

{

разослать DECISION_REQUEST другим участникам;

ожидать прихода решения; /^процесс блокирован*/

записать решение

локальный журнал;

}

если решение

GLOBAL_COMMIT

записать GLOBAL^COMMIT

локальный журнал;

иначе если решение

GLOBAL_ABORT

записать GLOBAL_ABORT

локальный журнал;

} если

{

записать VOTE_ABORT

локальный журнал;

послать VOTE_ABORT координатору;

}

После получения запроса на голосование участник может решить голосовать

за подтверждение транзакции, для чего ему следует сначала записать это реше-

ние в локальный журнал, а затем проршформировать о нем координатора путем

посылки ему сообщения VOTECOMMIT. После этого участник должен дож-

даться глобального решения. Получив это решение (которое опять-таки должно

прийти от координатора), он записывает его в локальный журнал, а затем вы-

полняет.

Однако если участник ожидает решения координатора весь отведенный на

это срок и не получает его, он выполняет протокол прекращения ожидания, сна-

чала рассылая остальным процессам сообщения

DECISION_REQUESTy

а затем

блокируясь в ожидании ответа. Когда приходит ответ (возможно, от координато-

ра, который уже успел восстановиться), участник записывает решение в локаль-

ный журнал и поступает в соответствии с HPIM.

442 Глава 7. Отказоустойчивость

Каждый участник должен быть готов к тому, что другой участник запросит

у него глобальное решение. Для этого каждый из участников должен запустить

отдельный поток выполнения параллельно с главным потоком выполнения уча-

стника, как показано в листинге 7.3. Этот поток блокируется до получения за-

проса о решении. Он может ответить другим процессам, только если ассоцииро-

ванный с ним участник уже принял конечное решение. Другими словами, если в

локальный журнал было записано сообщение GLOBAL JCOMMIT \ит GLOBAL^

ABORT,

можно быть уверенным, что координатор послал свое решение как ми-

нимум этому процессу. Кроме того, как мы говорили ранее, что если ассоцииро-

ванный с потоком участник находится в состоянии /МГ, он может решить по-

слать сообщение

GLOBAL__АВОRT,

Во всех остальных случаях этот поток ничем

не сможет помочь задавшему вопрос процессу, и пославший запрос участник ос-

танется без ответа.

Листинг 7.3. Схема обработки входящих запросов о решении

ДЕЙСТВИЯ ПО ОБРАБОТКЕ ЗАПРОСА РЕШЕНИЯ:

/^выполняются

отдельном потоке выполнения*/

пока истина

(

ожидать любого сообщения DECISION^REQUEST: /^процесс блокирован*/

считать последнее записанное состояние из локального журнала

если состояние =» GLOBAL^COMMIT

послать GLOBAL__COMMIT запросившему решение участнику

иначе если состояние == INIT или состояние == GLOBAL_ABORT

послать GLOBAL_^ABORT запросившему решение участнику

иначе

пропустить /^участник блокирован*/

}

Как можно заметить, возможна ситуация, когда участнику придется устано-

вить блокировку до восстановления координатора. Такая ситуация может воз-

никнуть, если все участники получат и обработают сообщение координатора

VOTE_REQUEST

и в ходе этой работы координатор сломается. В этом случае

участники не смогут совместно решить, какое действие им предпринять. По этой

причине протокол 2PC также называют

протоколом блокирующего

подтвержде-

ния

{blocking commit

protocol).

Существует несколько способов избежать блокировки. Одно из них, описан-

ное в [22], состоит в использовании примитива групповой рассылки, когда полу-

чатель немедленно рассылает ответное сообщению всем остальным процессам.

Можно показать, что подобный подход позволяет участнику принять итоговое

решение даже в том случае, если координатор еще не восстановился. Другое ре-

шение

—

использование протокола трехфазного подтверждения, который явля-

ется последней темой этого раздела.

7.5.2. Трехфазное подтверждение

Проблема протокола двухфазного подтверждения состоит в том, что при поломке

координатора участники могут оказаться не в состоянии прийти к итоговому ре-

шению. В результате участникам приходится дожидаться восстановления коор-

7.5. Распределенное подтверждение 443

динатора, находясь в заблокированном состоянии. В [422] был предложен вари-

ант протокола 2PC, названный

протоколом трехфазного подтверждения

{Three-

phase

Commit

Protocol ЗРС), который предотвращает блокировку процессов при

появлении ошибок аварийной остановки. Хотя протокол ЗРС часто упоминается

в литературе, на практике он используется редко, потому что редко возникают

условия, в которых блокируется 2РС. Мы рассмотрим этот протокол, поскольку

он представляет собой дальнейшее развитие решений проблем отказоустойчиво-

сти в распределенных системах.

Как и 2РС, ЗРС формулируется в терминах координатора и набора участни-

ков.

Соответствующие им конечные автоматы показаны на рис. 7.14. Сущность

протокола состоит в том, что состояния координатора и любого из учадтников

удовлетворяют двум условиям.

4 Не существует такого состояния, из которого может быть осуществлен пря-

мой переход как в состояние

COMMIT,

так и в состояние

ABORT.

Не существует такого состояния, в котором невозможно принять итоговое

решение, но возможен переход в состояние

COMMIT.

Можно показать, что эти два условия необходимы и достаточны для того,

чтобы протокол подтверждения был неблокирующим

[424].

Vote-request

INIT ) Vote-abort ( INIT )

Commit

-'-^z^*

* .

CBID vote-commit V п.к„.,к.. CB^PD

Vote-request

Vote-abort

К ''"^'' J Vote-commit \ Global-abort ^ ^ Prepare-commit

Global-abort

/ NPrepare-commit

\подтверждение

NKeady-commit

(

ABORT ) ( PRECOMMIT) ^^'^->fABORT ) (

PRECOMMFT)

Ready-commit

I Global-commit

Global-commit

Подтверждение

[COMMIT] (COMMIT)

Рис.

7.14. Координатор в протоколе ЗРС в виде конечного автомата (а). Участник в виде

конечного

автомата(б)

Координатор ЗРС начинает с рассылки всем участникам сообщения VOTE_

REQUEST после чего ожидает прихода ответов. Если хотя бы один участник

голосует за прерывание транзакции, это становится итоговым решением и коор-

динатор рассылает участникам сообщение GLOBALABORT Однако если тран-

закция может быть подтверждена, рассылается сообщение PREPAREjCOMMIT.

Только после того, как все участники подтвердят свою готовность к подтвержде-

нию,

координатор посылает итоговое сообщение GL0BALC0MM1T в результа-

те которого транзакция действительно подтверждается.

И снова существует лишь несколько ситуаций, в которых процесс блокирует-

ся и ожидает сообщений. Во-первых, когда участник, находясь в состоянии

INIT,

ожидает прихода запроса на голосование, он может в итоге перейти в состояние

444 Глава 7. Отказоустойчивость

ABORT,

что будет означать поломку координатора. Эта ситуация идентична си-

туации для протокола 2РС. Также аналогично координатор может находиться в

состоянии

WAIT,

ожидая голосов участников. По истечении заданного времени

координатор решает, что участник отказал, и обрывает транзакцию путем рас-

сылки сообщения GLOBALABORT.

Рассмотрим теперь блокировку координатора в состоянии

PRECOMMIT.

слу-

чае истечения заданного времени он приходит к выводу, что один из участников

отказал, но прочие участники знают, что они голосовали за подтверждение тран-

закции. Соответственно, координатор приказывает работающим участникам под-

твердить транзакцию путем рассылки сообщения GLOBALCOMMIT. Кроме то-

го,

он полагает, что протокол восстановления отказавшего участника поможет

подтвердить его часть транзакции после

того,

как этот участник будет восстановлен.

Участник Р может блокироваться в состоянии READY или

PRECOMMIT.

По-

сле окончания отведенного участнику Р на ожидание времени, Р в состоянии по-

нять,

что координатор отказал и нужно решать, что делать дальше. Как и в 2РС,

если Р при контакте с другим участником обнаружит, что он находится в состоя-

нии COMMIT (или ABORT), Р также переходит в это состояние. Кроме того, ес-

ли все участники находятся в состоянии

PRECOMMIT,

транзакция может быть

без проблем подтверждена.

Опять-таки, аналогично схеме 2РС, если другой участник Q по-прежнему на-

ходится в состоянии

INIT,

транзакция может быть совершенно спокойно пре-

рвана. Важно отметить, что Q может находиться в состоянии INIT только в том

случае, если ни один из участников не находится в состоянии PRECOMMIT Уча-

стник может перейти в состояние

PRECOMMIT,

только если координатор перед

сбоем сам перешел в состояние

PRECOMMIT,

а значит, получил голоса всех уча-

стников. Другими словами, участник не может оставаться в состоянии

INIT,

ко-

гда другой участник переходит в состояние PRECOMMIT

Если каждый из участников, с которым может связаться Р, находится в со-

стоянии READY (и вместе они образуют большинство), транзакция должна быть

прервана. Здесь следует отметить, что если один из участников отказывает, поз-

же он будет восстановлен. Однако ни

Р,

пи любой другой активный участник не

знают, в каком состоянии будет находиться отказавший участник после восста-

новления. Если процесс будет восстановлен в состоянии

INIT,

решение о преры-

вании транзакцрш

—

единственно верное. В наихудшем случае процесс может

восстановиться в состоянии

PRECOMMIT,

но и в этом случае он не сможет поме-

шать прерыванию транзакции.

Этим ситуация сильно отличается от протокола 2РС, где отказавший участ-

ник может восстановиться в состоянии

COMMIT,

тогда как все прочие участни-

ки будут находиться в состоянии

READY.

В этом случае оставшиеся рабочие

процессы не смогут принять итогового решения и вынуждены будут ожидать

восстановления отказавшего процесса. В ЗРС, если какой-то из рабочих процес-

сов находится в состоянии

READY,

отказавшие процессы не смогут восстано-

виться ни в каком другом состоянии, кроме

INIT,

ABORT или

PRECOMMIT.

По

этой причине оставшиеся невредимыми процессы всегда смогут прийти к итого-

вому решению.

7.6. Восстановление 445

И, наконец, если процессы, такрте как Р, могут достичь состояния

PRECOMMIT

(и они составляют большинство), то можно без проблем подтвердить транзак-

цию.

И снова мы можем видеть, что все остальные процессы либо находятся в

состоянии

READYy

либо, как минимум, если они отказали, будут восстановлены

в состоянии

READY,

PRECOMMIT или

COMMIT.

Дополнительные подробности по ЗРС можно найти в [47, 103].

7.6. Восстановление

Теперь мы рассмотрим алгоритмы, позволяющие противостоять отказам. Следу-

ет понимать, что процесс, в котором произошел отказ, можно восстановить, при-

ведя его в корректное состояние. Из этого следует, что мы сосредоточимся снача-

ла на том, что такое «привести в корректное состояние», а уж затем

—

где и как в

случае распределенных систем это состояние может быть зафиксировано и как

восстановить его, используя контрольные точки и протоколирование сообщений.

7.6.1.

Основные понятия

Основа отказоустойчивости

—

исправление после ошибок. Напомним, что ошиб-

кой считается отказ части системы. Основная идея механизма исправления оши-

бок состоит в замене ошР1бочного состояния безошибочным. Существует два ос-

новных способа восстановления после ошибок.

При

обратном исправлении {backward recovery)

основная задача состоит в воз-

вращении системы из текущего ошибочного состояния к предыдущему безоши-

бочному состоянию. Чтобы сделать это, необходимо время от времени записы-

вать состояние системы и восстанавливать ее в предыдущем состоянии, если

дело пойдет плохо. При каждой записи текущего состояния системы (или его

части) говорят, что создается

контрольная точка

{checkpoint).

Другой вариант исправления ошибок — прямое исправление {fonoard reco-

very).

В этом случае при входе системы в ошибочное состояние вместо отката на-

зад,

к предыдущей контрольной точке, делается попытка перевести систему в но-

вое корректное состояние, в котором она могла бы продолжать работать. Основ-

ная проблема механизмов прямого исправления ошибок состоит в том, что для

них необходимо заранее знать о возможных ошибках. Только в этом случае уда-

стся исправить эти ошибки и перейти в новое состояние.

Разницу между прямым и обратным механизмами исправления ошибок легко

понять на примере реализации надежной связи. Основной способ восстановле-

ния потерянного пакета

—

попросить отправителя послать этот пакет повторно.

действительности повторная передача пакета означает отход назад, к предыду-

щему правильному состоянию, а именно к состоянию, когда начинал передавать-

ся потерянный пакет. Таким образом, надежная связь, организуемая посредством

повторной посылки пакетов,

—

это пример обратного исправления ошибок.

Альтернативный подход состоит в использовании так называемого метода

коррекции разрушенной информации. В этом случае потерянный пакет создает-

446 Глава 7. Отказоустойчивость

ся из других, успешно доставленных пакетов. Так, например, при использовании

блочного кодирования от потерь (п, k) набор из k исходных пакетов преобразует-

ся в набор п декодированных пакетов, так что любой набор из k декодированных

пакетов подходит для реконструкции k исходных пакетов. Типичные значения

—

16 и 32, причем k<n<2k

[383].

Если доставленных пакетов оказывается не-

достаточно, отправителю придется продолжать передавать пакеты до тех пор, пока

не удастся восстановить ранее потерянный пакет. Коррекция разрушенной ин-

формации представляет собой типичный пример прямого исправления ошибки.

Вообще говоря, для исправления ошибок в распределенных системах в каче-

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

Важное преимущество обратного исправления ошибок состоит в том, что это об-

щий метод, который не зависит от конкретной системы или процесса. Другими

словами, он может быть интегрирован в распределенную систему, например в ее

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

Однако обратное исправление ошибок также создает определенные проблемы

[421].

Во-первых, восстановление системы или процесса в предыдущем состоя-

нии

—

дело достаточно затратное с точки зрения производительности. Как мы

увидим далее, обычно восстановление, например, отказавшего процесса или сай-

та, обычно требует большого объема работы.

Во-вторых, поскольку механизмы обратного исправления ошибок не зависят

от конкретного распределенного приложения, в котором они используются, не-

возможно дать какие-либо гарантии того, что после исправления ошибок та же

самая или похожая ошибка не возникнет вновь. Если подобные гарантии необ-

ходимы, обработка ошибок обычно выполняется в цикле. Другими словами, при-

менение механизмов обратного исправления ошибок не позволяет добиться пол-

ностью прозрачного исправления ошцбок.

И, наконец, хотя при обратном исправлении ошибок используются контроль-

ные точки, в некоторые состояния вернуться просто невозможно. Например, ес-

ли некий человек (возможно, злоумышленнрж) из-за неисправного банкомата

внезапно получил 1000 долларов, шанс на то, что эти деньги удастся вернуть,

очень невелик. Также невозможно и восстановление в предыдущее состояние

большинства UNIX-CPICTCM после ввода следующей команды и выбора непра-

вильного каталога:

/bin/rm -fr *

Некоторые вещи просто необратимы.

Контрольные точки позволяют вернуться в предыдущее правильное состоя-

ние.

Однако создание контрольной точки часто вызывает значительные затраты

само по себе, что оборачивается значительными потерями производительности.

Поэтому многие отказоустойчивые распределенные системы сочетают создание

контрольных точек с

протоколированием

сообщений {message logging). В этом

случае после создания контрольной точки процесс записывает свои сообщения

перед отсылкой в журнал, что означает

протоколирование отправителем

{sender-

based losing). Альтернативное решение

—

позволить принимающему процессу

протоколировать приходящие сообщения перед их доставкой выполняемому

7.6. Восстановление 447

приложению. Эта схема известна под названием

протоколирования получателем

{receiver-based

logging).

Если в принимающем процессе возникает отказ, он дол-

жен восстановить состояние последней сохраненной контрольной точки, после

чего может повторно запустить все принятые после нее сообщения. Таким обра-

зом, комбинация из контрольных точек и протоколирования сообщений позво-

ляет восстановить значительно более позднее состояние, чем состояние, сохра-

ненное в последней контрольной точке, без дополнительных затрат на создание

контрольных точек.

Есть еще одно важное различие между контрольными точками и схемами, ос-

нованными на применении журналов. В системе, использующей только кон-

трольные точки, процесс может быть восстановлен только в состояние контроль-

ной точки. Но его поведение в этом состоянии может отличаться от поведения

перед ошибкой. Так, например, если периоды между сеансами заданы не жестко,

сообщения теперь могут приходить в ином порядке, вызывая другую реакцию

получателя. В противоположность этому в случае протоколирования сообщений

происходит повторение всех событий, имевших место с момента последней кон-

трольной точки. Это повторение облегчит взаимодействие системы с внешним

миром.

Так, например, рассмотрим случай, когда ошибка была вызвана неверными

данными, вводимыми пользователем. Если использовать исключительно кон-

трольные точки, максимум, что может система,

—

это вернуться в состояние кон-

трольной точки, предшествовавшей приему введенных пользователем данных. При

протоколировании сообщений можно использовать более старую контрольную

точку, после чего, повторяя события, выйти к точке, где пользователь должен

вводить данные. На практике комбинация небольшого количества контрольных

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

множеством контрольных точек.

Устойчивые хранилища

Чтобы иметь возможность восстановить предыдущее состояние системы, требу-

ется хранить нужную для восстановления информацию в безопасности. «В без-

опасности» в данном случае означает, что хранимая информация должна выдержи-

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

Устойчивые хранилища играют важную роль в восстановлении распределенных

систем. Здесь мы кратко обсудим этот вопрос.

Хранилища делятся на три категории. Первая

—

это стандартная оперативная

память, стирающаяся при отключении питания или перезагрузках машины. Сле-

дующая категория

—

дисковые хранилища, переживающие ошибки процессора,

но неспособные выжить при поломке головок диска.

И, наконец, существуют так называемые устойчивые хранилища {stable sto-

rage),

разработанные для выживания в любых «передрягах», кроме катастроф

вроде наводнений или землетрясений. Устойчивые хранилища могут быть реа-

лизованы в виде пары стандартных дисков, как это показано на рис. 7.15, а. Каж-

дый блок устройства 2 является точной копией соответствующего блока устрой-

448 Глава 7. Отказоустойчивость

ства

Если блок диска изменяется,

то

сначала изменяется

проверяется блок

устройства 1,

затем

та

же операция производится

и с

устройством

Другое значение сектора

Неправильная

контрольная

сумма

Рис. 7.15. Устойчивое хранилище (а). Отказ после обновления диска

(б).

Плохой участок диска

(s)

Представим себе, что система отказала после изменения содержимого устрой-

ства

1, но до

изменения содержимого устройства 2,

как

показано

на

рис. 7.15,

б.

Во время исправления ошибок диски должны сравниваться поблочно. Если два

соответствующих блока различны,

это

может означать,

что

правилен блок

на

устройстве 1 (поскольку устройство 1 всегда обновляется раньше устройства 2),

а значит, новый блок копируется с устройства

на устройство 2. По завершении

процесса восстановления оба диска снова будут идентичны.

Другая потенциальная проблема

—

самопроизвольное повреждение блока. Час-

тички пыли или безжалостное время способны внезапно, без каких-либо предва-

рительных признаков, вызвать ошибку контрольной суммы нормального ранее

блока,

как

показано

на

рис. 7.15,

е.

Если произойдет подобная ошибка, потерян-

ные блоки можно будет восстановить по соответствующим блокам другого диска.

Как видно

из

этого описания, устойчивые хранилища хорошо подходят при-

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

ные транзакции.

При

записи данных

устойчивое хранилище

последующим

чтением

их

оттуда

целью проверки правильности записи шанс

на

то, что впо-

следствии они окажутся потерянными, очень незначителен.

Ниже мы подробнее рассмотрим вопросы, связанные

контрольными точка-

ми

протоколированием сообщений. В [137] имеется обзор метода контрольных

точек

протоколирования

распределенных системах. Различные детали алго-

ритмов можно найти

[103].

7.6.2. Создание контрольных точек

в отказоустойчивых распределенных системах обратное исправление ошибок

требует, чтобы система регулярно записывала свое состояние

устойчивое хра-

нилище данных. Понятие состояния распределенных систем обсуждалось

гла-

7.6. Восстановление

449

ве 5. В частности, мы делали упор на необходимость записи непротиворечивого

глобального состояния, называемого также

распределенным

снимком состояния

{distributed

snapshot).

Если в распределенном снимке состояния процесс Р был со-

хранен в момент получения сообщения, должен также быть и процесс Q, сохра-

ненный в момент передачи сообщения. Правда, в виде исключения сообщение

может прийти и со стороны.

В схемах обратного исправления ошибок каждый процесс время от времени

записывает свое состояние в локальное устойчивое хранилище. Для восстанов-

ления после системной ошибки необходимо из этих локальных состояний вос-

создать непротиворечивое общее состояние. В частности, лучше всего восстано-

вить последний распределенный снимок состояния, именуемый также границей

восстановления {recovery

line).

Другими словами, граница восстановления соот-

ветствует последнему непротиворечивому срезу, что и показано на рис. 7.16.

Граница ^

/ Начальное состояние восстановления '^""^^^J^a"^''

^ ^ „ - Время •

Сообщение, Противоречивый

отправленное от Р2 к

Р1

срез

Рис. 7.16. Граница восстановления

Независимое создание контрольных точек

к сожалению, распределенная природа контрольных точек, когда каждый про-

цесс просто время от времени записывает свое локальное состояние, никак не ко-

ординируя свои действия с другими, может сильно затруднить поиски границы

восстановления. Для нахождения границы восстановления необходимо, чтобы

каждый из процессов откатился к последнему записанному состоянию. Если эти

локальные состояния не образуют распределенного снимка состояния, потребу-

ется новый откат и т. д. Этот процесс каскадного отката может привести к

эффек-

ту

домино {domino

effect), как показано на рис. 7.17.

Начальное

^ состояние

Контрольная точка

Рис. 7.17. Эффект домино

450 Глава 7. Отказоустойчивость

При ошибке в процессе Р2 необходимо восстановить его состояние, каким

оно было записано в последней контрольной точке. Процесс Р1 также придется

откатывать. К сожалению, два последних записанных локальных состояния не

образуют глобального непротиворечивого состояния: состояние, записанное в Р2,

указывает на прием сообщения т, но ни один процесс не может быть назван его

отправителем. Соответственно, Р2 нужно откатить к еще более раннему состоянию.

Однако следующее состояние, в котором будет восстановлен процесс

Р2,

так-

же не может использоваться в качестве части распределенного снимка состоя-

ния. В этом случае процесс Р1 записан принимающим сообщение

т \

а событие

его отправления записано снова не будет. Такрш образом, появится необходи-

мость откатить к более раннему состоянию также и процесс Р1. В этом примере

получается, что границей восстановления на самом деле является исходное со-

стояние системы.

Поскольку процессы создают локальные контрольные точки независимо друг

от друга, этот метод называется также методом

независимого создания

контроль-

ных точек {independent

checkpointing).

Альтернативой ему является глобально

координированное создание контрольных точек, которое мы обсудим ниже. Од-

нако координация требует глобальной синхронизации, которая может создать

проблемы с производительностью. Другой недостаток независимого создания

контрольных точек состоит в том, что любое локальное хранилище нужно время

от времени чистить, например, запуская специальную программу «сборки мусо-

ра».

Однако самый серьезный недостаток

—

это необходимость расчета границы

восстановления.

Независимое создание контрольных точек требует записи зависимостей, что-

бы процессы можно было откатить вместе, в непротиворечивое глобальное со-

стояние. Для этого обозначим т-ю контрольную точку процесса Р как CP[i\{m).

Пусть

INT[i]{rn)

обозначает интервал между контрольными точками CP[i]{m-\)

и CP[i]{m).

Когда процесс Pi отправляет сообщение в интервале ШТ[г\(т), он добавляет

к нему пару (/,т), пересылая ее принимающему процессу. Когда процесс Pj полу-

чает сообщение в интервале INT[j](n) вместе с парой

(i,m),

он записывает зави-

симость INT[i](m)

INT[j](n). Таким образом, когда Pj создает контрольную

точку CP[j](n), он дополнительно вместе с прочей информацией для восстанов-

ления, входящей в CP[j](n), записывает в локальное хранилище данных и эту

зависимость.

Предположим теперь, что в некоторый момент процесс Р1 необходимо отка-

тить в контрольную точку CP[i](m-l). Для того чтобы гарантировать глобаль-

ную непротиворечивость, нам следует убедиться, что все процессы, получавшие

от

Р1

сообщения, посланные в интервале INT[i](m), откачены назад к состоянию,

предшествующему получению этих сообщений. Так, например, процесс Pj в на-

шем примере следует откатить как минимум до контрольной точки CP[j](n-l).

Если CP[j](n-\) не приведет систему в глобально непротиворечивое состояние,

следует произвести дальнейший откат.

Расчет границы восстановления требует анализа РП1тервальных зависимостей,

сохраненных каждым из процессов при создании контрольных точек. Если даже