Логические часы

Логические часы — механизм определения хронологической и причинно-следственной связи событий в распределённых системах, не имеющих единых физических часов. Алгоритмы логических часов позволяют получать частичное упорядочение событий по времени и обнаруживать нарушения причинно-следственных связей. Состояние логических часов может включаться в состав внутренних сообщений, пересылаемых между узлами системы. Впервые предложен и реализован Лэмпортом в 1978 году, его работа была отмечена Премией Тьюринга 2013 года.

Знание хронологической последовательности событий полезно для анализа вычислений, при создании распределённых алгоритмов, отслеживании отдельных событий или хода вычислений.

При реализации алгоритмов логических часов каждый процесс распределённой системы имеет собственные структуры данных для представления логического времени и использует специальный протокол при их обновлениях. Обычно в них хранится логическое локальное время для получения отметок времени для локальных событий и логическое глобальное время, соответствующее представлениям процесса о глобальном времени. Протокол задаёт правила обновления локального логического времени при выполнении событий и правила обновления логического глобального времени для отслеживания прогресса во всей распределённой системе.

Известные примеры логических часов:

• Часы Лэмпорта
• Векторные часы
• Вектор версий
• Матричные часы

Ссылки

• Distributed System Logical Time // Roberto Baldoni, Silvia Bonomi. MIDLAB, Sapienza University of Rome
• Chapter 3: Logical Time // Ajay Kshemkalyani and Mukesh Singhal, Distributed Computing: Principles, Algorithms, and Systems, Cambridge University Press, 2008
• Distributed Systems 06. Logical Clocks // Paul Krzyzanowski, Rutgers University, Fall 2014