Логические часы — это механизм для фиксации хронологических и причинно-следственных связей в распределенной системе . Часто распределенные системы могут не иметь физически синхронных глобальных часов. Во многих приложениях (таких как распределенный GNU make ), если два процесса никогда не взаимодействуют, отсутствие синхронизации ненаблюдаемо, и в этих приложениях достаточно, чтобы процессы согласовали порядок событий (т. е. логические часы), а не время на настенных часах. [1] Первая реализация логических часов, временные метки Лампорта , была предложена Лесли Лампортом в 1978 году ( премия Тьюринга в 2013 году).
В системах логических часов каждый процесс имеет две структуры данных: логическое локальное время и логическое глобальное время . Логическое локальное время используется процессом для отметки собственных событий, а логическое глобальное время — это локальная информация о глобальном времени. Специальный протокол используется для обновления логического локального времени после каждого локального события и логического глобального времени, когда процессы обмениваются данными. [2]
Логические часы полезны при анализе вычислений, разработке распределенных алгоритмов, отслеживании отдельных событий и исследовании хода вычислений.
Вот некоторые заслуживающие внимания алгоритмы логических часов: