Continuous Delivery Message Dissemination problems under the multicasting communication mode
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.
multicasting approximation algorithms network communications message routing message forwarding