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

Правило 2: в каждое передаваемое сообщение добавляется значение логического времени L_i процесса-отправителя P_i на момент отправки этого сообщения. Когда процесс P_j получает такое сообщение, содержащее отметку времени L_msg, он выполняет следующие шаги:

1. 
   L_j = max(L_j, L_msg);
   
2. 
   исполняет Правило 1;
   
3. 
   доставляет сообщение и приступает к его обработке.
   

Нетрудно видеть, что это правило обеспечивает выполнение обоих Условий 1 и 2 непротиворечивости логических часов для события получения сообщения.
Поэтому такие логические часы являются непротиворечивыми, т.е. для любых двух событий e_i и e_j':
e_i → e_j'  L(e_i) < L(e_j').
Пример работы алгоритма скалярных часов Лэмпорта для d = 1 приведен на рис. 3.1. Рядом с каждым событием представлена его отметка времени. На стрелках указаны отметки времени, передаваемые с сообщениями.

Рис. 3.1. Пример работы алгоритма скалярных часов Лэмпорта.

1. Основные свойства

Линейное упорядочивание событий. Скалярные часы Лэмпорта могут быть использованы для введения на множестве событий распределенного вычисления отношения линейного порядка <, сохраняющего частичный причинно-следственный порядок событий →. Для этого мы просто будем упорядочивать события согласно их отметкам времени. Единственная сложность, с которой мы можем столкнуться, заключается в том, что некоторые события, происходящие в различных процессах, могут иметь одинаковую отметку времени. Например, на рис. 3.1 третье событие в процессе P₁ и второе событие в процессе P₂ имеют идентичную скалярную отметку времени, равную трем.
Для упорядочивания таких событий воспользуемся произвольным линейным порядком, заданным для процессов распределенной системы. К примеру, можно использовать линейно упорядоченные идентификаторы процессов. Тогда отношение линейного порядка <, связывающее любые два события e_i и e_j', происходящие в процессах P_i и P_j, будет определяться выражением:
e_i < e_j'  (L(e_i) < L(e_j')) ˅ ((L(e_i) = L(e_j')) ˄ (i < j)).
Благодаря тому, что скалярные часы удовлетворяют требованию непротиворечивости, событиями с одинаковыми отметками времени могут являться только параллельные события, т.е. L(e_i) = L(e_j')  e_i || e_j'. Такие события могут быть упорядочены любым способом без нарушения причинно-следственного порядка →, в том числе так, как представлено
выше. Поэтому, введенное нами отношение линейного порядка < сохраняет причинно-следственный порядок событий →: e_i → e_j'  e_i < e_j'.
Таким образом, мы показали, что скалярные часы могут быть использованы для определения одного из эквивалентных выполнений распределенной системы, т.е. для упорядочивания событий в последовательность, которая могла бы происходить в системе. В общем случае рассмотренный линейный порядок используется для обеспечения свойства живучести при построении различных распределенных алгоритмов: а именно, запросы, требующие обслуживания, снабжаются отметками скалярного времени и обслуживаются по порядку, задаваемому этими отметками, что позволяет каждому запросу, в конце концов, получить свое право на обслуживание.
Стоит отметить, что линейный порядок <, определенный выше, устанавливает статические приоритеты для процессов распределенной системы согласно значениям их идентификаторов. Если требуется "более справедливый метод", то отношение линейного порядка между процессами можно было бы задать как функцию логического времени. Например, в случае, когда L(e_i) = L(e_j') и i < j, мы могли бы определить, что e_i < e_j', если значение L(e_i) mod N попадает в полуинтервал (i, j], и e_j' < e_i в противном случае.