Synchronous Geodetic Network

M. Kant (Canada)


Geodetic networks, broadcasting, gossiping, leader election


Communication scheme based on store and forward routing, in which a processor can communicate simultaneously with all its neighbors (in parallel) in a synchronous geodetic network is considered. The authors give efficient algorithms for leader election, broadcasting and gossiping on geodetic networks, and evaluate the corresponding time and communication complexity. The geodetic graphs are an interesting topology to be considered for the connection of ring networks. Connecting two ring networks by a bridge is a solution, but the communications between the rings using the bridge will be slow because all messages have to pass through a single pair of processors. For a geodetic network, as the one presented in the paper, we may direct the messages flow through many processors (in one direction or the other). Consequently, the communication speed will be ameliorated for the same amount of processors and messages in the network.

Important Links:

Go Back