Access Restriction

Author Awerbuch, Baruch ♦ Goldreich, Oded ♦ Vainish, Ronen ♦ Peleg, David
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1990
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract This paper concerns the message complexity of broadcast in arbitrary point-to-point communication networks. $\textit{Broadcast}$ is a task initiated by a $\textit{single}$ processor that wishes to convey a message to all processors in the network. The widely accepted model of communication networks, in which each processor initially knows the identity of its neighbors but does not know the entire network topology, is assumed. Although it seems obvious that the number of messages required for broadcast in this model equals the number of links, no proof of this basic fact has been given before.It is shown that the message complexity of broadcast depends on the exact complexity measure. If messages of unbounded length are counted at unit cost, then broadcast requires $&THgr;(↿\textit{V}↾)$ messages, where $\textit{V}$ is the set of processors in the network. It is proved that, if one counts messages of bounded length, then broadcast requires $&THgr;(↿\textit{E}↾)$ messages, where $\textit{E}$ is the set of edges in the network. Assuming an intermediate model in which each vertex knows the topology of the network in radius $\textit{&rgr;}$ ≥ 1 from itself, matching upper and lower bounds of $&THgr;(min{↿\textit{E}↾,$ $↿\textit{V}↾1+&THgr;(l)/&rgr;})$ is proved on the number of messages of bounded length required for broadcast. Both the upper and lower bounds hold for both synchronous and asynchronous network models.The same results hold for the construction of spanning trees, and various other global tasks.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1990-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 37
Issue Number 2
Page Count 19
Starting Page 238
Ending Page 256

Open content in new tab

   Open content in new tab
Source: ACM Digital Library