DocumentCode :
980578
Title :
Continuous Delivery Message Dissemination Problems under the Multicasting Communication Mode
Author :
Gonzalez, Teofilo F.
Author_Institution :
Dept. of Comput. Sci., Univ. of California, Santa Barbara, CA
Volume :
19
Issue :
8
fYear :
2008
Firstpage :
1034
Lastpage :
1043
Abstract :
We consider the continuously delivery message dissemination (CDMD) problem over the n processor single-port complete (all links are present and are bi-directional) static network with the multicasting communication primitive. This problem has been shown to be NP-complete even when all messages have equal length. For the CDMD problem we present an efficient approximation algorithm to construct a message routing schedule with total communication time 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.
Keywords :
computational complexity; message passing; multicast communication; telecommunication network routing; NP-complete; continuous delivery message dissemination problems; message-routing schedule; multicasting communication mode; n-processor single-port complete; Data communications aspects; Graph algorithms; Parallelism and concurrency; Routing and layout;
fLanguage :
English
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
1045-9219
Type :
jour
DOI :
10.1109/TPDS.2007.70801
Filename :
4384477
Link To Document :
بازگشت