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

РАЗДЕЛ 3. ЛОГИЧЕСКИЕ ЧАСЫ

Понятие времени является фундаментальным для нашего мышления; его течение отделяет все более раннее от всего более позднего. Большинство, наверное, скажет, что событие а произошло раньше события b, если a произошло в более ранее время, чем b.

В распределенных системах отсутствуют глобальные часы, отсчитывающие общее для всех процессов время, и к показаниям которых процессы могли бы получать мгновенный доступ. Поэтому нам пришлось определять отношение "произошло раньше", связывающее события процессов между собой, не опираясь на понятие единого физического времени. Мы показали, что традиционное представление о времени как о линейном порядке на множестве событий не совсем подходит для распределенного вычисления, т.к. отношение "произошло раньше" оказывается отношением частичного порядка, и с точки зрения процессов невозможно понять, какая последовательность событий происходит на самом деле.
В этом разделе мы рассмотрим механизм логических часов, который позволяет отслеживать причинно-следственный порядок событий распределенного вычисления и, как следствие, упорядочивать события в одну или несколько последовательностей, которые могли бы происходить в системе. Использование логического времени, отсчитываемого такими часами, значительно упрощает разработку алгоритмов для распределенных систем.
Следует подчеркнуть, что основная задача логических часов заключается только в отслеживании порядка событий, а не в определении каких-либо других свойств, обычно ассоциируемых с понятием времени. Например, логические часы не дают никакого количественного представления о физическом времени, прошедшем между двумя событиями. В отличие от физического времени, чей ход нельзя остановить или изменить, логическое время не течет само по себе. Оно поддается учету только при наступлении событий в распределенной системе, и потому – дискретно. Невозможно ничего не делать и ожидать наступления того или иного момента логического времени в будущем: если не происходит никаких событий, логическое время "останавливается", и ожидаемый момент может никогда не наступить.

1.