Синхронизация

Волновые алгоритмы могут использоваться для случаев, когда должна быть достигнута глобальная синхронизация процессов. Задача синхронизации формулируется следующим образом. В каждом процессе q должно быть выполнено событие a_q , и в некоторых процессах должны быть выполнены события b_p , причем все события a_q должны быть выполнены по времени раньше, чем будет выполнено какое-либо событие b_p . Алгоритм должен использовать конечное количество сообщений.

В алгоритмах синхронизации события b_p будут рассматриваться как события return(OK).

Любой волновой алгоритм может использоваться как алгоритм синхронизации. Действительно, пусть A – волновой алгоритм. Чтобы преобразовать A в алгоритм синхронизации, потребуем, чтобы каждый процесс q выполнял a_q до того, как q пошлет сообщение в A или примет решение в A. Событие b_p происходит после события return(OK) в p.