Временные метки Лампорта

Временны́е метки Лампорта — простой алгоритм определения порядка событий в распределённой системе. Так как синхронизировать все узлы полностью невозможно, вводится отношение частичного порядка с минимальными затратами. Данный метод является прообразом метода векторных часов.

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

• Счётчик увеличивается перед каждым внутренним событием процесса;
• при отправке сообщения значение счётчика прикрепляется к сообщению;
• при получении сообщения значение счётчика процесса-реципиента выставляется в максимум текущего и полученного значения и увеличивается на 1.

См. также

• Произошло-ранее
• Векторные часы

Ссылки

• Leslie Lamport (1978). «Time, clocks, and the ordering of events in a distributed system». Communications of the ACM 21 (7): 558–565. DOI:10.1145/359545.359563.