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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

Примечания[править | править вики-текст]

  1. 1 2 Chapter 3: Logical Time // Ajay Kshemkalyani and Mukesh Singhal, Distributed Computing: Principles, Algorithms, and Systems, Cambridge University Press, 2008

Ссылки[править | править вики-текст]