26-10-2010, 12:03 PM
[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.
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.
