Синхронизация часов: различия между версиями

Система состоит из фиксированного множества взаимосвязанных ''процессоров''. Каждый процессор имеет свои ''локальные часы''. Выполнение системы представляет собой последовательность событий, в которой каждое событие является либо ''событием отправки'', либо ''событием получения'', либо ''внутренним событием''. Что касается коммуникации, то предполагается, что каждое событие получения сообщения <math>m</math> имеет уникальное соответствующее событие отправки <math>m</math>. Это означает, что сообщения могут быть произвольно потеряны, продублированы или переупорядочены, но не повреждены. Каждое событие <math>e</math> происходит в одном определенном процессоре и имеет два вещественных числа, связанных с ним: его ''локальное время'', обозначаемое LT(e), и его ''реальное время'', обозначаемое RT(e). Локальное время события моделирует показания локальных часов в момент наступления этого события, и локальный процессор может использовать это значение, например, для вычислений или для передачи другому процессору. В отличие от этого, реальное время события не наблюдается процессорами: это абстрактное понятие, существующее только в анализе.

В данной работе генерация и доставка сообщений полностью отделены от информации о них. Формально предполагается, что сообщения генерируются некоторым «модулем отправки», а доставляются «системой коммуникации». Задача алгоритмов заключается в том, чтобы добавить содержимое в сообщения и переменные состояния в каждом узле. (Идея отделения информации о синхронизации от генерации сообщений была предложена в работе [1]). Алгоритм располагает только локальной информацией, то есть содержимым локальных переменных состояния и показаниями локальных часов, а также содержимым входящего сообщения, если мы имеем дело с событием приема. Также предполагается, что алгоритму известна спецификация реального времени. Совокупность событий, их … и локальных времен (но не реальных времен) называется ''ракурсом'' данного выполнения.  Алгоритмы, таким образом, могут использовать в качестве входных данных только ракурс выполнения и его спецификацию реального времени.