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

Общие принципы построения логических часов

В обычной жизни мы говорим, что некоторое событие произошло в 9:30, если оно наступило после того, как наши часы показали 9:30, и до того, как показания часов изменились на 9:31. При этом с каждым
интересующим нас событием мы ассоциируем отметку времени (англ.
timestamp), соответствующую этому событию.
Описание принципов построения логических часов мы также начнем с понимания того, что такие часы должны обеспечивать механизм, позволяющий каждому событию в распределенной системе приписывать некоторое числовое значение, которое можно интерпретировать как время наступления этого события. Поэтому логическими часами (англ. logical clock) назовем всякую функцию Θ, отображающую множество событий распределенного вычисления в некоторое упорядоченное множество (T, <), где Т представляет собой совокупность допустимых значений логического времени (англ. time domain). В распределенных системах каждый процесс P_i может управлять работой только своих часов Θ_i независимо от часов других процессов. При этом отметка логического времени события e_i, происходящего в процессе P_i, будет определяться показаниями часов этого процесса на момент наступления e_i, т.е. Θ(e_i) = Θ_i(e_i) для всех событий e_i процесса P_i. Как было указано выше, показания часов Θ_i должны изменяться между наступлением событий процесса P_i, т.е. сам факт изменения показаний Θ_i событием не является.
Несмотря на то, что такие часы работают в независимых процессах, отметки логического времени, назначаемые событиям, должны удовлетворять фундаментальному условию монотонного возрастания времени. А именно, все события, принадлежащие конусу прошлого любого события e_i, должны быть отмечены временем меньшим, чем время Θ(e_i) события e_i. И наоборот, все события из конуса будущего события e_i должны иметь время наступления большее, чем Θ(e_i):
e_i, e_j'  : e_i → e_j'  Θ(e_i) < Θ(e_j').
Данное требование монотонного возрастания времени называют условием непротиворечивости логических часов (англ. clock consistency) или условием непротиворечивости отметок времени событий. Оно отражает последовательную природу выполнения каждого отдельного процесса и соглашение о том, что на передачу любого сообщения затрачивается ненулевое конечное время. Действительно, из определения отношения причинно-следственного порядка следует, что требование непротиворечивости логических часов будет выполнено при выполнении следующих двух условий: