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

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

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

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

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

Примечания

Ссылки

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