Abstract
We consider the problem of disseminating messages in networks. We are interested in information dissemination algorithms in which machines operate independently without any knowledge of the network topology or size. Three communication tasks of increasing difficulty are studied. In blind broadcasting (BB) the goal is to communicate the source message to all nodes. In acknowledged blind broadcasting (ABB) the goal is to achieve BB and inform the source about it. Finally, in full synchronization (FS) all nodes must simultaneously enter the state terminated after receiving the source message. The algorithms should be efficient both in terms of the time required and the communication overhead they put on the network. We limit the latter by allowing every node to send a message to at most one neighbor in each round. We show that BB is achieved in time at most 2n in any n-node network and show networks in which time 2n-o(n) is needed. For ABB we show algorithms working in time (2+∈)n, for any fixed positive constant ε and sufficiently large n. Thus for both BB and ABB our algorithms are close to optimal. Finally, we show a simple algorithm for FS working in time 3n.The optimal time of full synchronization remains an open problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
H. Attiya and J. Welch, Distributed Computing, McGraw-Hill.
B. Awerbuch, O. Goldreich, D. Peleg and R. Vainish, A Tradeoff Between Information and Communication in Broadcast Protocols, J. of ACM 37, (1990), 238–256.
R. Bar-Yehuda, O. Goldreich, and A. Itai, On the time complexity of broadcastin radio networks: An exponential gap between determinism and randomization, Proc. 6th ACM PODC (1987), 98–108.
Y. Beritbart, M. Garofalakis, R. Rastogi, S. Seshadri, A. Silbershatz, Topology Discovery in Heterogeneous IP networks, Proceedings of INFOCOM’99.
B.S. Chlebus, L. Gasieniec, A. Gibbons, A. Pelc, W. Rytter, Deterministic broadcasting in unknown radio networks, Proc. SODA’2000, 861–870.
K. Diks, E. Kranakis and A. Pelc, Broadcasting in unlabeled tori, Par. Proc. Lett. 8 (1998), 177–188.
K. Diks, E. Kranakis and A. Pelc, Perfect broadcasting in unlabeled networks, Discrete Applied Mathematics 87 (1999), 33–47.
K. Diks, S. Dobrev, E. Kranakis, A. Pelc and P. Ruzicka, Broadcasting in unlabeledhypercubes with linear number of messages, IPL 66 (1998), 181–186.
U. Feige, D. Peleg, P. Raghavan and E. Upfal, Randomized broadcast in networks, Random Structures and Algorithms 1 (1990), 447–460.
R. Gavindan, H. Tangmunarunkit, Heuristics for Internet map discovery, Proceedings of INFOCOM’99.
M. Harchol-Balter, T. Leighton, D. Lewin, Resource Discovery in Distributed Networks, Proceedings of PODC’99, 229–237.
H. Harutyunyan and A. Liestman, Messy broadcasting, PPL 8(1998), 149–160.
S.M. Hedetniemi, S.T. Hedetniemi and A.L. Liestman, A survey of Gossiping and Broadcasting in Communication Networks, Networks 18 (1988), 319–349.
J. Hromkovič, R. Klasing, B. Monien, and R. Peine, Dissemination of Information in Interconnection Networks, in: Ding-Zhu Du and D. Frank Hsu (Eds.) Combinatorial Network Theory, Kluwer, 1995, 125–212.
A. Pelc, Fault Tolerant Broadcasting and Gossiping in Communication Networks, NETWORKS 28 (1996), 143–156.
R. Reischuk and M. Koshors, Lower bound for Synchronous Systems and the Advantage of Local Information, Proc. of 2nd WDAG, (1987), pp. 374–387.
A. Segall, Distributed Network Protocols, IEEE Trans. Inf. Th. 29 (1983), 23–35.
G. Tel, Introduction to distributed algorithms, Cambridge University Press, 1994.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gargano, L., Pelc, A., Perennes, S., Vaccaro, U. (2000). Efficient Communication in Unknown Networks. In: Brandes, U., Wagner, D. (eds) Graph-Theoretic Concepts in Computer Science. WG 2000. Lecture Notes in Computer Science, vol 1928. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-40064-8_17
Download citation
DOI: https://doi.org/10.1007/3-540-40064-8_17
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41183-3
Online ISBN: 978-3-540-40064-6
eBook Packages: Springer Book Archive