A Correctness Proof of a Topology Information
Main tenance Protocol for a Distributed Computer 
Network

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 constrain ts
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.

CACM July, 1977

Tajibnapis, W. D.

distributed computer network, correctness proofs,
computer networks, distributed control, network 
topology, routing problem in networks, distributed operating
system, store and forward packet switching, 
store and forward message switching, traffic control

3.81 4.32

CA770703 JB December 28, 1977  11:59 AM

2949	5	2949
2949	5	2949
2949	5	2949