Распространение информации с обратной связью

Важным применением волновых алгоритмов является случай, когда некоторая информация должна быть передана всем процессам и определенные процессы должны быть оповещены о завершении передачи. Эта задача распространения информации с обратной связью (PIF – propagation of information with feedback) формулируется следующим образом.

Формируется подмножество процессов из тех, кому известно сообщение M (одно и то же для всех процессов), которое должно быть распространено, т.е. все процессы должны принять M. Определенные процессы должны быть оповещены о завершении передачи; т.е. должно быть выполнено специальное событие notify, причем оно может быть выполнено только когда все процессы уже получили сообщение M. Алгоритм должен использовать конечное количество сообщений.

Оповещение в PIF-алгоритме можно рассматривать как событие return (OK).

Любой волновой алгоритм может использоваться как PIF-алгоритм. Действительно, пусть A – волновой алгоритм. Чтобы использовать A как PIF-алгоритм, возьмем в качестве процессов, изначально знающих M, инициаторы A. Информация M добавляется к каждому сообщению A. Это возможно, поскольку по построению стартеры A знают M изначально, а последователи не посылают сообщений, пока не получат хотя бы одно сообщение, т.е. пока не получат M. Событию return (OK) в волне предшествуют события в каждом процессе; следовательно, когда оно происходит, каждый процесс знает M, и событие return (OK) можно считать требуемым событием notify в PIF-алгоритме.