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

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

5.1.

Синхронизация часов 281

Время по часам, с

Время UTC, t

Рис. 5.4. Соотношение между временем по часам и временем UTC

при различной частоте тиков

Алгоритм Кристиана

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

машин имеет приемник WWV, а наша задача состоит в синхронизации всех ос-

тальных машин по ней. Назовем машину с приемником WWV

сервером

времени

{time

server).

Наш алгоритм [113] основан на работах Кристиана (Cristian) и более

ранних. Периодически, гарантировано не реже, чем каждые 5/2р с, каждая машина

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

так быстро, как это возможно, отвечает сообщением, содержащим ее текущее вре-

мя,

Сутсу

как показано на рис. 5.5.

То и Ti отсчитываются по одним и тем же часам

Клиент

Сервер

времени

Время обработки прерывания, I Время-

Рис. 5.5. Получение текущего времени с сервера времени

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

жет просто выставить свои часы в значение

Сите-

Однако такой алгоритм имеет

две проблемы: главную и второстепенную. Главная проблема состоит в том, что

время никогда не течет назад. Если часы отправителя спешат.

Сите

может ока-

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

Сите

способна вызвать серьезные проблемы, связанные с тем, что объектные файлы,

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

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

до изменения времени.

282 Глава 5. Синхронизация

Изменения могут вноситься постепенно. Один из способов таков. Предполо-

жим, что таймер настроен так, что он генерирует 100 прерываний в секунду.

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

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

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

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

одновременно.

Менее серьезная проблема состоит в том, что перенос ответного сообщения с

сервера времени отправителю требует ненулевого времени. Хуже всего, что эта

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

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

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

дом ответа. То и другое время (начальное Го и конечное Т\), измеряется по од-

ним и тем же часам, а значит, интервал будет относительно точно измерен даже в

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

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

жением времени прохождения сообщения будет (Т\~ То)/2. После получения от-

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

жащееся в сообщении, следует увеличить на это число. Если теоретическое

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

ры времени.

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

времени сервер времени обрабатывает прерывание и работает с пришедшим со-

общением. Обозначим время обработки прерывания /. Тогда величина интерва-

ла времени между

TQHTU

затраченного на прохождение сообщения, будет равна

T\~TQ-

лучшей оценкой времени на прохождение сообщения в одну сторону

будет половина этой величины. Существуют системы, в которых сообщение из А

в В постоянно движется по одному маршруту, а из В в Л

—

по другому. Они бу-

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

случаи.

Для повышения точности Кристиан предложил производить не одно измере-

ние,

а серию. Все измерения, в которых разность Т\-То превосходит некоторое

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

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

гут быть усреднены для получения наилучшего значения. С другой стороны, со-

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

скольку оно предположительно попало в момент наименьшего трафика и потому

наиболее точно отражает чистое время прохождения.

Алгоритм Беркли

В алгоритме Кристиана сервер времени пассивен. Прочие машины периодически

запрашивают у него время. Все, что он делает,

—

это отвечает на запросы. В опе-

рационной системе UNIX разработки университета Беркли (Berkeley) принят

прямо противоположный подход

[188].

Здесь сервер времени (а на самом деле де-

мон времени) активен, он время от времени опрашивает каждую из машин, какое

5.1.

Синхронизация часов 283

время на ее часах. На основании ответов он вычисляет среднее время и предлага-

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

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

ших вперед часах. Этот метод применим для систем, не имеющих машин с прием-

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

тором. Это продемонстрировано на рис. 5.6.

Демон времени

3:00

0 Q

3:00 0

\ 1 1 /

ШШ

,+25

3:05 +5

1^ ]

ШШ

-20

2:50 3:25 2:50 3:25 2:50 3:25

Рис. 5.6. Демон времени запрашивает у всех остальных машин значения их часов (а).

Ответы машин (б). Демон времени сообщает всем, как следует подвести их часы (е)

В 3:00 демон времени сообщает всем машинам свое время и запрашивает эти

машины об их времени (рис. 5.6, а). Затем демон времени получает ответ о том,

насколько спешат или отстают часы машин от часов демона (рис. 5.6, б). Зная

эти числа, демон времени вычисляет среднее и сообщает каждой из машин, как

ей следует подвести свои часы (рис. 5.6, в).

Усредняющие алгоритмы

Оба ранее описанных алгоритма сильно централизованы с неизбежно вытекаю-

щими отсюда недостатками. Известны также и децентрализованные алгоритмы.

Один из классов алгоритмов децентрализованной синхронизации часов работает

на основе деления времени на синхронизационные интервалы фиксированной

продолжительности. В этом случае z-й интервал начинается в момент времени

Го

+ iR и продолжается до Го + (/ + 1)72, где Го

—

заранее согласованный прошед-

ший момент, а i?

—

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

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

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

скоростью, эти широковещательные рассылки будут сделаны не одновременно.

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

и начинает собирать все остальные широковещательные пакеты в течение некото-

рого интервала 5. Когда будут собраны все широковещательные пакеты, запуска-

ется алгоритм вычисления по ним нового времени. Простейший алгоритм состо-

ит в усреднении значений всех остальных машин. Незначительные его вариации

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

ких значений и усреднении оставшихся. Отбрасывание крайних значений можно

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

284 Глава 5. Синхронизация

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

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

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

времени прохождения эха.

Дополнительные алгоритмы синхронизации часов рассматриваются в [274,

369,

429]. Один из наиболее часто используемых алгоритмов в Интернете

—

это

протокол сетевого времени {Network Time

Protocol,

NTP), описанный в

[293].

NTP

известен тем, что позволяет обеспечить точность (глобальную) 1-50 мс. Такая

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

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

[294].

Множественные внешние источники точного времени

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

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

точников иТС. Однако из-за врожденной неточности самих источников времени

и флуктуации на пути сигнала лучшее, что могут сделать операционные систе-

мы,

—

это установить интервал, в который попадает UTC. В основном различные

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

к которым они присоединены, должны прийти к какому-то общему соглашению.

Чтобы достичь этого соглашения, каждый процессор с источником UTC мо-

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

мер,

точно в начале каждой минуты по UTC. Ни один процессор не получит

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

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

через которые должен будет пройти пакет. Эти значения различны для каждой

пары (источник UTC, процессор). Будут также играть свою роль и другие факто-

ры,

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

ся послать что-то по Ethernet в один и тот же момент. Более того, если процессор

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

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

тельную неясность.

5.1.3. Использование синхронизированных часов

За прошедшие несколько лет стали легкодоступными необходимая аппаратура

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

ном масштабе (то есть во всем Интернете). Благодаря этим новым технологиям

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

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

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

ру не более одного сообщения, даже в случае сбоев

[269].

Традиционный подход

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

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

чтобы можно было отличить новое сообщение от повторной посылки. Проблема

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

5.2. Логические часы 285

таблицу номеров сообщений. Неясно также, сколько времени хранить эти номера

сообщений.

С использованием времени традиционный алгоритм модифицируется сле-

дующим образом. Итак, каждое сообщение имеет идентификатор связи (выбран-

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

в таблицу последнюю полученную метку времени. Если какое-либо входящее со-

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

для этого соединения, сообщение считается дубликатом и не рассматривается.

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

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

определяемую следующим образом:

G =

CurrentTime

- MaxLifetime -

MaxClockSkew.

Здесь MaxLifetime

—

максимальное время жизни сообщения, а

MaxClockSkew

указывает на то, как далеко от времени UTC могут уйти часы. Любая метка вре-

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

старше С уже прошли. Если входящее сообщение имеет неизвестный идентифи-

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

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

общение

—

это, несомненно, дубликат. В действительности G

—

это сумма номе-

ров всех старых сообщений. Каждые AT текущее время сбрасывается на диск.

В случае сбоя и последующей перезагрузки сервера он загружает значение G

из файла, сохраненного на диске, и увеличивает его в ходе периода обновления, AT.

Любое входящее сообщение с отметкой времени старше G

—

это дубликат.

ре-

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

гается. Некоторые новые сообщения могут быть отвергнуты ошибочно, но при

соблюдении всех условий алгоритм поддерживает семантику «не более одного

сообщения».

Вдобавок к этому алгоритму в [269] также описано, как можно использовать

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

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

обработать обязательства по атомарным транзакциям. Мы обсудим некоторые из

этих алгоритмов в следующих пунктах. По мере улучшения синхронизации тай-

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

5.2. Логические часы

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

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

с истинным временем, которое каждый час объявляют по радио. Для работы про-

граммы

make,

например, достаточно, чтобы все машины считали, что сейчас 10:00,

даже если на самом деле сейчас 10:02. Так, для некоторого класса алгоритмов по-

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

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

логических

часах

{logical

clocks).

286 Глава 5. Синхронизация

В своей классической статье (см. [249]) Лампорт (Lamport) показал, что хотя

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

Если два процесса не взаимодействуют, нет необходимости в том, чтобы их часы

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

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

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

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

файл input.c был более старым или более новым, чем input.o, а не абсолютное вре-

мя их создания.

В этом пункте мы обсудим алгоритм Лампорта, предназначенный для син-

хронизации логических часов. Кроме того, мы рассмотрим расширение метода

Лампорта, векторные отметки времени. Лампорт сделал дополнения к своей ра-

боте в

[251].

5.2.1.

Отметки времени Лампорта

Для синхронизации логических часов Лампорт определил отношение под названи-

ем «происходит раньше». Выражение а-^Ь читается как

«а

происходит раньше

Ь»

и означает, что все процессы согласны с тем, что первым происходит событие а,

а позже

—

событие

Ь,

Отношение «происходит раньше» непосредственно испол-

няется в двух случаях.

Если а и й

—

события, происходящие в одном и том же процессе, и а про-

исходит раньше, чем й, то отношение а-^Ь истинно.

"¥ Если а

—

это событие отсылки сообщения одним процессом, а

й —

событие

получения того же сообщения другим процессом, то отношение а-^Ь так-

же истинно. Сообщение не может быть получено до отсылки или даже

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

необходимо конечное ненулевое время.

Отношение «происходит раньше» — это транзитивное отношение, то есть

в случае, если

а->Ь

и Ь-^с, выполняется условие а-^с. Если два события, х и г/,

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

посредственно, ни через третий процесс), то отношение х-^у не истинно, впро-

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

{concurrent).

В дан-

ном случае это означает только то, что никто не может (или не хочет) знать о

том, где и какое из этих событий произошло.

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

бы поставить в соответствие каждому событию а отметку времени С(<2), которая

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

при <2->6 соблюдалось соотношение С(а)<С(Ь). Перефразируя условие, которое

мы ранее установили, если аи b

—

два события одного процесса и а происходит

раньше, чем 6, то С(а)<С(Ь). Например, если а

—

это посылка сообщения одним

процессом,

Sib —

прием этого сообщения другим процессом, то С(а) и

С(Ь)

долж-

ны быть назначены так, чтобы значения С(а) и

С(Ь)

соответствовали отношению

С(а)<С(Ь).

Кроме того, время по часам. С, всегда идет вперед (увеличивается).

5.2. Логические часы

287

—

никогда (не уменьшается). Коррекция времени должна производиться

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

нему положительного значения,

не его вычитанием.

Давайте теперь рассмотрим алгоритм Лампорта, применяемый

для

присвое-

ния времен событиям. Обсудим три процесса, описанные

на

рис. 5.7, а. Процес-

сы запущены

на

различных машинах, каждая

из

которых имеет собственные

ча-

сы

скорость работы.

Как

можно увидеть

по

рисунку, когда часы процесса О

поставят отметку времени 6,

процессе

они покажут 8,

в процессе 2

—

10.

Ка-

ждые часы идут

постоянной скоростью, но эти скорости различны из-за разни-

цы

кристаллах.

Го"

-->,,^А

^^^

-..В^

0^-^

100|

Го~

--^^А

D...---

Т"

--..В

0^^

^^^^^.^

~о"

100

Рис. 5.7. Три процесса, каждый

собственными часами, которые ходят

разной

скоростью (а). Подстройка часов по алгоритму Лампорта

(б)

В момент 6 процесс

посылает сообщение А процессу 1. Сколько времени это

сообщение проведет

пути, зависит

от

того, каким часам

мы

верим.

любом

случае, когда оно придет

процесс 1, его часы будут показывать 16. Если сооб-

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

процесс

сочтет,

что на

пересылку

ушло 10 тиков. Это значение вполне разумно. В соответствии

этими рассужде-

ниями сообщение

В от

процесса 1 процессу

будет доставлено

за

16 тиков,

это

вновь разумное значение.

Перейдем

самой забавной части наших рассуждений. Сообщение С от про-

цесса

процессу 1 будет послано

на

отметке 60

достигнет цели

на

отметке

56.

Сообщение

D от

процесса 1 процессу

будет послано

на

отметке 64

достигнет

цели

на

отметке 54. Эти цифры абсолютно невозможны. Это

та

ситуация, кото-

рую мы должны предотвратить.

Решение, найденное Лампортом, прямо вытекает

из

отношения «происходит

раньше». Поскольку

посылается

на

отметке

60,

оно должно достичь цели

на

отметке

61 или

позднее. Поэтому каждое сообщение содержит время отправки

по часам отправителя. Когда сообщение достигает цели, но часы получателя по-

288 Глава 5. Синхронизация

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

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

правки. На рис. 5.7, б мы видим, что теперь сообщение

приходит на отметке 61.

Таким же образом сообщение D приходит теперь на отметке 70.

С одним небольшим дополнением этот алгоритм удовлетворяет нашим требо-

ваниям по глобальному времени. Это добавление состоит в том, что между лю-

быми двумя событиями часы должны «протикать» как минимум один раз. Если

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

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

жутке между сообщениями.

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

нию:

никакие два сообщения не должны происходить одновременно. Чтобы выпол-

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

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

кой. Таким образом, если в процессах 1 и 2 в момент времени 40 происходят со-

бытия, то первый из них будет происходить в

40.1,

а второй в 40.2.

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

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

ловия.

4 Если а происходит раньше b в одном и том же процессе, то С(а)<С(Ь),

Если аи b представляют собой отправку и получение сообщения, соответ-

ственно С(а)<С(Ь),

Для всех различимых событий аиЬ выполняется соотношение С(а) ^ С(Ь).

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

в системе. В отличие от этого множество других распределенных алгоритмов для

устранения неясностей требуют упорядоченности, так что этот алгоритм широко

цитируется в литературе.

Пример

—

полностью упорядоченная групповая рассылка

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

гда необходима репликация базы данных на нескольких сайтах. Например, для

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

данных по счетам в двух разных местах, скажем в Нью-Йорке и Сан-Франциско.

Запросы всегда пересылаются к ближайшей копии. Ценой быстрого ответа на за-

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

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

На самом деле в отношении изменений существуют более точные требования.

Предположим, клиент в Сан-Франциско хочет добавить $100 на свой счет, на

котором в настоящее время лежит $1000. В то же самое время сотрудник банка в

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

на процент по вкладу

—

1 %. Оба изменения должны быть внесены в обе копии

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

ния могут дойти в ином порядке (рис. 5.8).

5.2. Логические часы

289

Обновление 1

выполняется раньше,

чем обновление 2

Реплицированная

база данных

Обновление 2

выполняется раньше,

чем обновление 1

Рис. 5.8. Обновление реплицированной базы данных, после которого

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

Пользовательская операция обновления будет выполнена в Сан-Франциско

раньше обновления для начисления процентов. В Нью-Йорке же наоборот, ко-

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

а уж после этого по ней будет проведена операция с депозитом в $100. Соответ-

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

$1,111,

а база данных в Нью-Йорке

—

$1,110.

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

ления должны быть выполнены в одинаковом порядке в каждой из копий. Хотя

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

но не важна. Важно, чтобы обе копии были абсолютно одинаковыми. Обычно та-

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

{totally-ordered

multicasting),

то есть такой операции групповой рассылки, при ко-

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

стью.

Для реализации такой рассылки абсолютно распределенным методом мо-

гут использоваться отметки времени Лампорта.

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

групповой рассылки. Каждое из сообщений всегда имеет отметку времени с те-

кущим временем (логическим) отправителя. Если сообщение передается путем

групповой рассылки, оно по идее приходит также и отправителю. Кроме того,

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

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

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

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

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

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

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

Интересный аспект такого подхода состоит в том, что все процессы будут

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

всем процессам, включая

подтверждения,

а предполагает ответ от всех процес-

сов.

Напомним также, что мы решили, что сообщения принимаются в порядке их

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

очередь в соответствии с отметкой времени на этом сообщении. Часы Лампорта

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

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

290 Глава 5. Синхронизация

Процесс может доставить поставленное в очередь сообщение приложению, ко-

торое работает, только если это сообщение находится на вершине очереди и его

получение подтверждено всеми остальными процессами. В этот момент сообще-

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

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

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

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

5.2.2. Векторные отметки времени

Отметки времени Лампорта приводят к ситуации, когда все события в распреде-

ленной системе имеют единую последовательность, такую, что если событие а

происходит раньше события 6, то а оказывается перед

/?,

то есть С{а) < С(Ь).

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

связи между двумя сообщениями аи

Ь,

просто сравнивая их временные отметки,

соответственно С(а) и С{Ь). Другими словами, если С(а) <

С{Ь),

это не обяза-

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

Ь.

Для это-

го необходимо что-то еще.

Чтобы понять это, рассмотрим систему рассылки сообщений. Один из наибо-

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

тронных досок сообщений в Интернете,

сетевые новости

(например, описанные

в [110]). Пользователи, а следовательно, процессы, выбирают определенные дис-

куссионные группы. Послания в такую группу, будь то письма или реакция на

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

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

мы можем попытаться использовать описанную выше схему полностью упоря-

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

ние В пришло после сообщения Л, значит, В представляет собой отклик на то,

что было послано в сообщении А. На самом деле они могут быть абсолютно неза-

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

ком строга для этого случая.

Проблема состоит в том, что отметки времени Лампорта не в состоянии уло-

вить

причинно-следственную

связь. В нашем примере получение письма из со-

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

него.

Соответственно, если в группе процессов поддерживаются отношения при-

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

вать за получением этого письма. Не более, но и не менее. Если два письма или

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

важен.

Причинно-следственная связь может быть соблюдена посредством

векторных

отметок времени

(vector

timestamps).

Векторная отметка времени VT{d) присво-

енная событию а, имеет следующее свойство: если

VT{d)

< VT(b) для события 6,

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

Ь.

Векторные

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

Р,

вектора

с перечисленными ниже свойствами.