Browse Prior Art Database

Derivation of a Distributed Algorithm for Finding Paths in Directed Networks

IP.com Disclosure Number: IPCOM000148336D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2007-Mar-29

Publishing Venue

Software Patent Institute

Related People

McCurley, Robert: AUTHOR [+3]

Abstract

i- 9 .. I. Derivation of r Distributed 2 L, I-. Algorithl for Finding Paths 5 in Directed letworks* TT : f a : , : -':I *. Robert McCurley ,- . .; I.!.' L , -4 Fred B. Schneider i:, 'a. -7 'CR 83-586 rl. December 1 983 ., I ,.- C' (1 :< Department of Computer Science Cornell UniversityIthaca, New York 14853 This work is supported in part by NSF Grant MCS-81030605. Schneider i s also supported by an IBM Faculty Development Award. Derivation of a Distributed Algorithm for Finding Paths in Directed ~etworks* Robert McCurley Fred B. Schneider Department of Computer Science Cornell UniversityIthaca, New York 14853 December 14, 1983 ABSTRACT A distributed algorithm is developed that can be used to compute the topology of a network, given that each site starts with information about sites it is adja- cent to, the network is strongly connected, and communication channels are uni- directional. The program is derived and proved correct using assertional reason- ing.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 15% of the total text.

Page 1 of 20

i-

9

.. I. Derivation of r Distributed

2 L, I-. Algorithl for Finding Paths

5 <$ in Directed letworks*

TT : f a :

, '

-+

: -':I

*. Robert McCurley ,- . .; I.!.'

L , -4 Fred B. Schneider

i:, - 'a.

--

-7 'CR 83-586

rl. December 1 983

., I ,.-

C'

>

(1

:<

Department of Computer Science Cornell University
Ithaca, New York 14853

* This work is supported in part by NSF Grant MCS-81030605. Schneider i s also supported by an IBM Faculty Development Award.

[This page contains 1 picture or other non-text object]

Page 2 of 20

[This page contains 1 picture or other non-text object]

Page 3 of 20

 Derivation of a Distributed Algorithm for Finding Paths in Directed ~etworks*

Robert McCurley

Fred B. Schneider

Department of Computer Science Cornell University
Ithaca, New York 14853

December 14, 1983

ABSTRACT

A distributed algorithm is developed that can be used to compute the topology of a network, given that each site starts with information about sites it is adja- cent to, the network is strongly connected, and communication channels are uni- directional. The program is derived and proved correct using assertional reason- ing.

h his work is supported in part by NSF Grant MCS-8103605. Schneider is also supported by an ISM

Faculty Development Award.

[This page contains 1 picture or other non-text object]

Page 4 of 20

[This page contains 1 picture or other non-text object]

Page 5 of 20

I. Introduction

   Computer-communication networks implemented by radio channels present some interesting problems. Due to local terrain and antenna placement, sites might be able to send messages directly to sites from which they cannot receive messages directly. We call such a network a directed network. If there is a path between every pair of sites in a

directed network, then every site can communicate with all other sites. To do this, sites must be aware of the topojogy of the network so that messages can be forwarded over appropriate routes.

   An algorithm to compute and disseminate the topology of a directed network is derived in this paper. The algorithm is actually more general, since it can be used to disseminate the union of the information known to each site to all sites in the network. While the algorithm is itself interesting, our major concern in this paper is with its derivation. Techniques usually associated with developing sequential programs [Dijkstra
76][Gries 81) are used in developing our distributed program.

   Section 2 gives some definitions pertaining to directed networks. In 'section 3, the algorithm is derived and proved correct. Section 4 contains some conclusions.

2. Directed Networks

   A directed network is modeled by a set of sites P and a set of linka L E P x P. L models the communication structure of the network; link (i, j) E L iff site j can receive directly messages sent by site i. Communication between all pain of sites is...