Premium
Multiple message broadcasting in the postal model
Author(s) -
BarNoy Amotz,
Kipnis Shlomo
Publication year - 1997
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199701)29:1<1::aid-net1>3.0.co;2-p
Subject(s) - broadcasting (networking) , computer science , message passing , partition (number theory) , latency (audio) , upper and lower bounds , broadcast communication network , computer network , parallel computing , binary logarithm , distributed computing , message broker , algorithm , theoretical computer science , telecommunications , discrete mathematics , mathematics , combinatorics , mathematical analysis
Broadcasting is an important operation in many message‐passing systems that has been widely investigated. Most existing broadcasting algorithms, however, do not address several emerging trends in distributed‐memory parallel computers and high‐speed communication networks. These trends include (i) treating the system as being fully connected with all processors equally distant, (ii) packetizing large amounts of data into sequences of messages, and (iii) tolerating communication latencies. In this paper, we explore the broadcasting problem in the postal model that addresses these issues. We provide two efficient algorithms for broadcasting m messages in a fully connected message‐passing system with n processors and communication latency λ. A lower bound on the time required for this problem is ( m ‐ 1) + f λ ( n ), where f λ ( n ) is the optimal time for broadcasting one message. We present two algorithms: The first is Algorithm PARTITION, the running time of which is at most m + n + 2λ when m ≥ n and 3 m + f λ ( n ) + 2λ when m ≤ n . The second is Algorithm D‐D‐TREES, the running time of which is at most m + 2 f λ ( n ) + O (λ) for any value of m . © 1997 John Wiley & Sons, Inc.