Введение в распределенные

Упорядочивание событий

Очень часто имеет значение не точное время наступления того или иного события (например, события отправки или получения сообщения), а порядок, в котором эти события происходили, т.е. требуется определить произошло ли данное событие в данном процессе до или после другого события в другом процессе. В этих случаях выполнение процессов можно описывать в терминах последовательности событий в условиях отсутствия знания точного времени их происхождения.
Рассмотрим следующий пример групповой рассылки сообщений электронной почты между пользователями A, B, C и Х. Пользователь А отправляет всей группе письмо с темой "Общее собрание". Пользователи В и С отвечают на него всей группе своими сообщениями с темой "Re: Общее собрание".
В действительности события происходят в следующей последовательности:

1. 
   Первым отправляется сообщение от пользователя А.
   
2. 
   Пользователь В получает его, читает и отправляет ответ.
   
3. 
   Пользователь С получает оба сообщения от А и В и затем отправляет свой ответ, опирающийся на оба сообщения от А и В.
   

Однако в связи с произвольными и независимыми задержками доставки сообщений, некоторые пользователи могут видеть другую последовательность наступления событий. Например, согласно сценарию, приведенному на рис. 1.6, в почтовом ящике пользователя Х сообщения будут располагаться в следующем порядке:

1. 
   Сообщение от пользователя С с темой "Re: Общее собрание".
   
2. 
   Сообщение от пользователя А с темой "Общее собрание".
   
3. 
   Сообщение от пользователя В с темой "Re: Общее собрание".
   

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

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

бы содержать отметку времени отправки согласно локальным часам компьютера-отправителя. Для нашего примера, сообщения m₁, m₂ и m₃ содержали бы в себе отметки времени t₁, t₂ и t₃, где t₁<t₂<t₃. Тогда в почтовом ящике пользователя Х полученные сообщения можно было бы отображать согласно порядку, задаваемому их временными отметками.
Однако, как уже обсуждалось, в распределенных системах часы не могут быть синхронизированы с абсолютной точностью. Если рассинхронизация часов невелика, то описанный выше подход с использованием отметок реального времени в большинстве случаев будет давать верный результат. Но не всегда. Для преодоления проблем, связанных с использованием реального времени, Л. Лэмпорт предложил модель логических часов (англ. logical clock), отсчитывающих логическое время (англ. logical time), которая может быть применена для упорядочивания событий, происходящих в различных процессах распределенной системы. Логическое время позволяет определить порядок событий (или порядок сообщений для рассматриваемого примера рассылки электронной почты) без обращения к часам компьютеров. Вопросы, связанные с моделью логического времени, мы рассмотрим далее в соответствующем разделе.

4.