article

Free access

A correctness proof of a topology information maintenance protocol for a distributed computer network

Author:

William D. TajibnapisAuthors Info & Claims

Communications of the ACM, Volume 20, Issue 7

Pages 477 - 485

https://doi.org/10.1145/359636.359701

Published: 01 July 1977 Publication History

PDF eReader

Abstract

In order for the nodes of a distributed computer network to communicate, each node must have information about the network's topology. Since nodes and links sometimes crash, a scheme is needed to update this information. One of the major constraints on such a topology information scheme is that it may not involve a central controller. The Topology Information Protocol that was implemented on the MERIT Computer Network is presented and explained; this protocol is quite general and could be implemented on any computer network. It is based on Baran's “Hot Potato Heuristic Routing Doctrine.” A correctness proof of this Topology Information Protocol is also presented.

References

[1]

Aupperle, E.M. The MERIT network re-examined. Digest of Papers, COMPCON 73, Feb. 1973, pp. 25-29.

Google Scholar

[2]

Baran, P. On distributed communication networks. IEEE Trans. Comm. Syst. CS-12 (March 1964), 109.

Google Scholar

[3]

Cocanower, A.B., Fischer, W., Gerstenberger, W.S., and Read, B.S. The communications computer operating system-the initial design. No. PB203 552, Nat. Tech. Inform. Service, Springfield, Va., Oct. 1970, p. 94.

Google Scholar

[4]

Frank, H., Kahn, R.E., and Kleinrock, L. Computer communication network design-experience with theory and practice. Proc. AFIPS 1972 SJCC, Vol. 40, AFIPS Press, Montvale, N.J.; pp. 255-270 (Contains an extensive bibliography on computer networks).

Google Scholar

[5]

Heart, F.W., Kahn, R.E., Ornstein, S.M., Crowther, W.R., and Walden, D.C. The interface message processor for the ARPA computer networks. Proc. AFIPS 1970 SJCC, Vol. 36, AFIPS Press, Montvale, N.J., pp. 551-567.

Google Scholar

[6]

Herzog, B. Computer networks. Proc. Int. Comptg. Symp., Venice, Italy, April 1972, pp. 12-14.

Google Scholar

[7]

Tajibnapis, W.D. Message-switching protocols in distributed computer networks. Ph.D. Diss., Pub. MCN-0676-TR-22, MERIT Computer Network, Ann Arbor, Mich., 1976.

Digital Library

Google Scholar

Cited By

View all

Kameyama SOkumura KTamura YDéfago X(2021)Active Modular Environment for Robot Navigation2021 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA48506.2021.9561111(8636-8642)Online publication date: 30-May-2021
https://dl.acm.org/doi/10.1109/ICRA48506.2021.9561111
Dobrev SKrálovič RPardubská D(2020)Exploration of Time-Varying Connected Graphs with Silent AgentsStructural Information and Communication Complexity10.1007/978-3-030-54921-3_9(146-162)Online publication date: 29-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-54921-3_9
Kolcun RBoyle DMcCann J(2016)Efficient Distributed Query ProcessingIEEE Transactions on Automation Science and Engineering10.1109/TASE.2016.253094113:3(1230-1246)Online publication date: Jul-2016
https://doi.org/10.1109/TASE.2016.2530941
Show More Cited By

Recommendations

The design of a topology information maintenance scheme for a distributed computer network
ACM '74: Proceedings of the 1974 annual conference - Volume 1

In order for the nodes of a distributed computer network to communicate, each node must have information about the network's topology. Since nodes and links sometimes crash, a scheme is needed to update this information. One of the major constraints on ...
A routing protocol for finding two node-disjoint paths in computer networks
ICNP '95: Proceedings of the 1995 International Conference on Network Protocols

In this paper, we present a routing protocol for finding two node-disjoint paths between each pair of nodes in a computer network. In the proposed protocol, each node in the network has the same procedure, which is driven by local information with ...
Composite routing protocols
SPDP '90: Proceedings of the 1990 IEEE Second Symposium on Parallel and Distributed Processing

A novel routing protocol for computer networks is designed by combining two routing protocols that adapt to changes in the network topology. The first routing protocol is expensive to operate but yields shortest-paths in the networks; therefore, it is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 20, Issue 7

July 1977

75 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/359636

Editor:
Robert L. Ashenhurst
Univ. of Chicago, Chicago, IL

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1977

Published in CACM Volume 20, Issue 7

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

93
Total Citations
View Citations
690
Total Downloads

Downloads (Last 12 months)113
Downloads (Last 6 weeks)12

Reflects downloads up to 28 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kameyama SOkumura KTamura YDéfago X(2021)Active Modular Environment for Robot Navigation2021 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA48506.2021.9561111(8636-8642)Online publication date: 30-May-2021
Dobrev SKrálovič RPardubská D(2020)Exploration of Time-Varying Connected Graphs with Silent AgentsStructural Information and Communication Complexity10.1007/978-3-030-54921-3_9(146-162)Online publication date: 29-Jun-2020
Kolcun RBoyle DMcCann J(2016)Efficient Distributed Query ProcessingIEEE Transactions on Automation Science and Engineering10.1109/TASE.2016.253094113:3(1230-1246)Online publication date: Jul-2016
Kolcun RMcCann J(2014)Dragon: Data discovery and collection architecture for distributed IoT2014 International Conference on the Internet of Things (IOT)10.1109/IOT.2014.7030121(91-96)Online publication date: Oct-2014
(2014)Readings in Distributed Artificial IntelligenceundefinedOnline publication date: 5-Jun-2014
Holzer SWattenhofer RKowalski DPanconesi A(2012)Optimal distributed all pairs shortest paths and applicationsProceedings of the 2012 ACM symposium on Principles of distributed computing10.1145/2332432.2332504(355-364)Online publication date: 16-Jul-2012
Cournier ADubois SVillain V(2009)A snap-stabilizing point-to-point communication protocol in message-switched networksProceedings of the 2009 IEEE International Symposium on Parallel&Distributed Processing10.1109/IPDPS.2009.5160997(1-11)Online publication date: 23-May-2009
Turner YTamir Y(2007)Deadlock-free connection-based adaptive routing with dynamic virtual circuitsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2006.08.01267:1(13-32)Online publication date: 1-Jan-2007
Nguyen MSchwartz M(2006)MCMPIEEE Journal on Selected Areas in Communications10.1109/49.53648814:7(1404-1421)Online publication date: 1-Sep-2006
Adler D(2006)Switch-level simulation using dynamic graph algorithmsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.6778810:3(346-355)Online publication date: 1-Nov-2006
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations

The design of a topology information maintenance scheme for a distributed computer network

A routing protocol for finding two node-disjoint paths in computer networks

Composite routing protocols

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations