Вот есть, допустим, такой граф узлов в сети, которые имеют возможность пересылать сообщения друг другу напрямую:
A------C
║ |
B------D
Узлы А и В находится в одной группе (потому что, например, находятся географически рядом), С и D для этой группы узлы удаленные. Узлы C и D единственные в своих группах.
Далее отправляется сообщение из узла В на все остальные узлы. Для этого сначала из В посылаем сообщение в А, как в близкий узел. Потом из В в D как в связанный с В «дальний» узел. В это время А получает сообщение от В с пометкой, что оно «широковещательное» и отсылает его в свой «дальний» узел, т.е. в С.
Теперь сообщение есть во всех узлах, но С и D этого не знают. Поэтому они отсылают сообщение дальше (C в D и А, D в В и С), получают ответ, что такое сообщение в этих узлах уже есть и прекращают пересылку. На этом все.
Такая схема как будто лучше, чем просто из узла В переслать сообщение сразу во все имеющиеся узлы. Особенно, если таких узлов, например, не 4, а тысяча. Но есть явная избыточность пересылки с проверкой, что такое сообщение уже принято в узле.
Как сделать такую широковещательную рассылку сообщения по всем узлам с наименьшей избыточностью? При условии, что правильная очередность отправленных сообщений должна согласовано соблюдаться во всех узлах.
