DocumentCode :
2627721
Title :
Broadcasting multiple messages in simultaneous send/receive systems
Author :
Bar-Noy, Amotz ; Kipnis, Shlomo
Author_Institution :
IBM T.J. Watson Res. Center, Yorktown Heights, NY, USA
fYear :
1993
fDate :
1-4 Dec 1993
Firstpage :
344
Lastpage :
347
Abstract :
We investigate the problem of broadcasting multiple messages in a message-passing system that supports simultaneous send and receive. The system consists of n processors, one of which has m messages to broadcast to the other n-1 processors. The processors communicate in rounds. In each round, a processor can simultaneously send a message to one processor and receive a message from another processor. The goal is to broadcast the m messages among the n processors in the minimal number of communication rounds. The lower bound on the number of rounds required is (m-1)+[log n]. We present an algorithm for this problem that requires at most m+[log n] communication rounds, for any values of m and n
Keywords :
distributed memory systems; message passing; multiprocessing systems; multiprocessor interconnection networks; broadcasting; communication rounds; message-passing system; multiple messages; simultaneous send/receive systems; Algorithm design and analysis; Broadcasting; Computer network management; Computer networks; Distributed processing; Hypercubes; Multimedia communication; Multimedia databases; Protocols; Transaction databases;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Processing, 1993. Proceedings of the Fifth IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-4222-X
Type :
conf
DOI :
10.1109/SPDP.1993.395513
Filename :
395513
Link To Document :
بازگشت