Синхронизация часов: различия между версиями

Теорема 1 сразу же дает алгоритм синхронизации часов: каждый процессор поддерживает известное ему представление части графа синхронизации. Это можно сделать с помощью протокола полной информации: этот граф отправляется в каждом исходящем сообщении, и всякий раз, когда приходит сообщение, граф расширяется, чтобы включить новую информацию из графа в пришедшем сообщении. Согласно теореме 2, полученный таким образом граф синхронизации представляет в любой момент времени всю доступную информацию, необходимую для оптимальной синхронизации. Для примера рассмотрим внешнюю синхронизацию. Непосредственно из определений следует, что все события, связанные с часами без дрейфа (например, события в узле-источнике), находятся на расстоянии 0 друг от друга в графе синхронизации и поэтому могут рассматриваться при вычислении расстояния как один узел s. Теперь, предполагая, что часы источника действительно показывают реальное время, легко увидеть, что для любого события p <math>RT(p) \in [LT(p) - d(s, p), LT(p) + d(p, s)]</math> и, более того, никаким корректным алгоритмом нельзя получить лучшие границы.

Наконец, отметим, что асинхронная модель также может рассматриваться как частный случай этой общей теории, в котором событие <math>p</math> «происходит раньше» события <math>q</math> тогда и только тогда, когда <math>d(p, q) \le 0</math>.