Алгоритм с нулевыми сообщениями

Первыми консервативными алгоритмами считаются алгоритмы, разработанные Bryant, Chandy, Misra.

Алгоритм предполагает:

- Топология процессов, которые посылают сообщения друг другу, известна и фиксирована.

- Каждый логический процесс посылает сообщения с неубывающими временными метками.

- Коммуникационная среда обеспечивает доставку сообщений в том порядке, в котором они были посланы.

Исходя из этих предположений, можно сделать следующее заключение:

- Временная метка сообщения, которое было получено последним на линии связи, является нижней границей временных меток (LBTS) всех будущих сообщений, передаваемых по этой линии связи.

- Нижняя временная метка (LBTS) логического процесса определяется как минимальная из всех нижних временных меток, полученных процессом по всем входным линиям связи.

Сообщения каждой линии связи находятся в очереди, которая обрабатывается по дисциплине FIFO. Очередь упорядочена также в соответствии с временными метками. Каждая линия связи имеет своё локальное время, которое равно временной отметке первого сообщения в очереди (если таковые имеются) или временной отметке последнего принятого сообщения (рис.13). Все события, которые планирует сам процесс для себя, находятся в другой очереди. Алгоритм периодически выбирает линию связи с наименьшим временем и, если в ней есть события, то он обрабатывает это событие. Если очередь пуста, то процесс блокируется. Процесс никогда не блокируется при проверке состояния очереди сообщений, которые он планирует для себя. Итак, этот алгоритм гарантирует, что каждый логический процесс будет обрабатывать события в хронологическом порядке.

Цель: Необходимо, чтобы события выполнялись в хронологическом порядке: