Логические часы — механизм определения хронологической и причинно-следственной связи событий в распределённых системах, не имеющих единых физических часов. Алгоритмы логических часов позволяют получать частичное упорядочение событий по времени и обнаруживать нарушения причинно-следственных связей. Состояние логических часов может включаться в состав внутренних сообщений, пересылаемых между узлами системы. Впервые предложен и реализован Лэмпортом в 1978 году, его работа была отмечена Премией Тьюринга 2013 года.
Знание хронологической последовательности событий полезно для анализа вычислений, при создании распределённых алгоритмов, отслеживании отдельных событий или хода вычисленийChapter 3: Logical Time // Ajay Kshemkalyani and Mukesh Singhal, Distributed Computing: Principles, Algorithms, and Systems, Cambridge University Press, 2008.
При реализации алгоритмов логических часов каждый процесс распределённой системы имеет собственные структуры данных для представления логического времени и использует специальный протокол при их обновлениях. Обычно в них хранится логическое локальное время для получения отметок времени для локальных событий и логическое глобальное время, соответствующее представлениям процесса о глобальном времени. Протокол задаёт правила обновления локального логического времени при выполнении событий и правила обновления логического глобального времени для отслеживания прогресса во всей распределённой системе.
Известные примеры логических часов: Часы Лэмпорта Векторные часы Вектор версий Матричные часы
Примечания
Ссылки 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
Категория:Распределённые вычисления