Логические часы. Алгоритм Лампорта

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

Лампорт определил отношение: «Происходит раньше». Оно обозначается: a à b. Это значит, что все процессы согласны, что событие а происходит первым, а все остальные за ним. Если это в одном процессе, то вообще это отношение выполняется.

Если процесс посылает сообщение, а второй процесс это сообщение принимает, то это отношение тоже выполняется. Это отношение транзитивное. В этом алгоритме каждому событию a ставится метка времени C(a). Эта метка должна быть принята как достоверно правильная всеми процессами. То есть если действительно a à b, то C(a) < C(b).

Будем передавать сообщения.

Передачи метки времени.

Рис. 4.9.

Коррекция: b ставится метка 201. А если часы шли вперед, то метка так и принимается. И так все события расставляются в последовательности.