Abstract-
We discuss algorithms, complexity issues, and applications
for message dissemination problems under the multicasting
communication mode. These problems arise while
executing in a parallel or distributed computing environment
iterative methods for solving scientific computation
applications, dynamic programming procedures, sparse matrix
multiplication, etc. Our message communication problems
also arise when disseminating information over ad-hoc
wireless networks.
Given a communication environment and a set of messages
that need to be exchanged, the message dissemination
problem is to find a schedule to transmit all the messages
in the least total number of communication rounds.
Generating an optimal communication schedule (with the
least total number of communication rounds) for message
dissemination problems over a wide range of communication
environments is an NP-hard problem. To cope with intractability
efficient message dissemination approximation
algorithms have been developed for different types of communication
environments and message communication patterns
(the communications that must take place). The communication
environment consists of the communication network
(the direct communications allowed for each processor),
primitive operations (the basic communication operations
allowed by the system), and the communication model
(possible operations during each communication round or
step).
DOWNLOAD FULL REPORT
