[attachment=6800]

Continuous Delivery Message Dissemination
Problems under the Multicasting
Communication Mode


Teofilo F. Gonzalez, Member, IEEE

---

Abstract—..

We consider the Continuous Delivery Message Dissemination (CDMD) problem over the n-processor single-port complete
(all links are present and are bidirectional) static network with the multicasting communication primitive. This problem has been shown
to be NP-complete, even when all messages have the same length. For the CDMD problem, we present an efficient approximation
algorithm to construct a message-routing schedule with a total communication time of at most 3:5d, where d is the total length of the
messages that each processor needs to send or receive. The algorithm takes OðqnÞ time, where n is the number of processors and q is
the total number of messages that the processors receive.