Abstract
This work concerns the problem of broadcasting a large message efficiently when each processor has partial prior knowledge about the contents of the broadcast message. The partial information held by the processors might be out of date or otherwise erroneous, and consequently, different processors may hold conflicting information.
The problem of Broadcast with Partial Knowledge (BPK) was introduced in the context of Topology Update — the task of updating network nodes about the network topology after topological changes. Awerbuch, Cidon, and Kutten gave a message optimal solution for BPK, yielding a message optimal Topology Update algorithm. However, the time complexity of both algorithms was not optimal. The time complexity was subsequently improved in two follow up papers, but the best known time complexity was still higher than optimal by at least a logarithmic factor.
In this paper we present a time-optimal, communication-optimal algorithm for BPK. The algorithm is randomized, and, similar to previous randomized algorithms, it does not require the additional knowledge assumptions essential for deterministic solutions. In addition to the theoretical interest in optimality, a logarithmic factor is often important in practice, especially when using the procedure as a component within a periodically activated Topology Update algorithm.
Supported by Air Force Contract TNDGAFOSR-86-0078, ARPA/Army contract DABT63-93-C-0038, ARO contract DAAL03-86-K-0171, NSF contract 9114440-CCR, DARPA contract N00014-J-92-1799, and a special grant from IBM.
Supported in part by an Allon Fellowship, by a Walter and Elise Haas Career Development Award and by a Bantrell Fellowship.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
Yehuda Afek, Baruch Awerbuch, and Eli Gafni. Applying static network protocols to dynamic networks. In 28th Annual Symposium on Foundations of Computer Science, October 1987.
Baruch Awerbuch, Israel Cidon, Inder Gopal, Marc Kaplan, and Shay Kutten. Distributed control for paris. In Proc. 9th ACM Symp. on Principles of Distributed Computing, 1990. To appear.
Baruch Awerbuch, Israel Cidon, and Shay Kutten. Optimal maintenance of replicated information. In Proc. 31st IEEE Symp. on Foundations of Computer Science. Comp. Soc. of the IEEE, IEEE, 1990.
Baruch Awerbuch, Israel Cidon, Shay Kutten, Yishay Mansour, and David Peleg. Broadcast with partial knowledge. In Proc. 10th ACM Symp. on Principles of Distributed Computing, 1991.
Baruch Awerbuch, Israel Cidon, Shay Kutten, Yishay Mansour, and David Peleg. Optimal broadcast with partial knowledge. Manuscript, available on request. 1995.
Baruch Awerbuch, Boaz Patt-Shamir, and George Varghese. Self-stabilization by local checking and correction. In Proc. 32nd IEEE Symp. on Foundations of Computer Science, pages 268–277, October 1991.
Baruch Awerbuch and Leonard J. Schulman. The maintenance of common data in a distributed system. In Proc. 32nd IEEE Symp. on Foundations of Computer Science, October 1991.
Y. Afek, S.Kutten, and M. Yung. Memory-efficient self-stabilization on general networks. In Proc. 4th Workshop on Distributed Algorithms, Italy, September 1990.
A. E. Baratz, J. P. Gray, P. E. Green Jr., J. M. Jaffe, and D.P. Pozefski. Sna networks of small systems. IEEE Journal on Selected Areas in Communications, SAC-3(3):416–426, May 1985.
Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorem for non-cryptographic fault tolerant distributed computing. In Proc. 20th ACM Symp. on Theory of Computing, May 1988.
Edsger W. Dijkstra. Self stabilizing systems in spite of distributed control. Commun. of the ACM, 17:643–644, 1974.
Shimon Even. Graph Algorithms. Computer Science Press, 1979.
Shmuel Katz and Kenneth Perry. Self-stabilizing extensions for message-passing systems. In Proc. 10th ACM Symp. on Principles of Distributed Computing, Quebec City, Canada, August 1990.
J. J. Metzner. An improved broadcast retransmission protocol. IEEE Trans. on Communications, COM-32(6):679–683, June 1984.
I. McQuillan, I. Richer, and E.C. Rosen. The new routing algorithm for the arpanet. IEEE Trans. on Commun., COM-28, May 1980.
M. Rabin. efficient dispersal of information for security, load balancing, and fault tolerance. J. of the ACM, 36(3):335–348, 1989.
John M. Spinelli and Robert G. Gallager. Broadcasting topology information in computer networks. IEEE Trans. on Commun., May 1989. to appear.
P. Tiwari. Lower bounds on communication complexity in distributed computer networks. In 25th Annual Symposium on Foundations of Computer Science, Singer Island, Florida, pages 109–117, 1984.
M.N. Wegman and J.L. Carter. Universal classes of hash functions. Journal of Computer and System Sciences, 18:143–154, 1979.
Andy Yao. Some complexity questions related to distributed computing. In Proceedings of the 11th Annual ACM Symposium on Theory of Computing, Atlanta, Georgia, pages 209–213. ACM SIGACT, ACM, April 1979.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Awerbuch, B., Kutten, S., Mansour, Y., Peleg, D. (1995). Optimal Broadcast with Partial Knowledge. In: Hélary, JM., Raynal, M. (eds) Distributed Algorithms. WDAG 1995. Lecture Notes in Computer Science, vol 972. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0022142
Download citation
DOI: https://doi.org/10.1007/BFb0022142
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60274-3
Online ISBN: 978-3-540-44783-2
eBook Packages: Springer Book Archive