WikiSort.ru - Не сортированное

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

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

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

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

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

Примечания

Ссылки

• 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

Это заготовка статьи по информатике. Вы можете помочь проекту, дополнив её.