An efficient fault tolerant distributed shortest path program in ADA

A simple, elegant algorithm upon implementation presents innumerable problems. This paper provides insight into the difficulties of implementing a distributed algorithm. This is followed by an efficient, fault tolerant implementation of the Distributed Shortest Path Algorithm. The provision of fault tolerance has a large overhead in terms of the number of messages required. A modification of the algorithm is proposed to reduce the number of messages, using buffering in conjunction with Ada constructs to achieve this in the implementation. The unrestricted communication in a distributed system produces situations conducive to deadlock. This is particularly true if a synchronous form of message passing is used, as processes will wait indefinitely for each other. To ensure freedom from deadlock a variant of nondeterministic message sending based on Ada timed out entry calls is used. Distributed programs are also, by virtue of their complexity, difficult to verify. Even after extensive testing residual design inadequacies may be present Thus the concept of Communication Closed Layers is used to design the program. The Consensus-Global Tester is used to implement error detection and assist in error recovery. In the event of an error, a Backward error recovery scheme is used which saves the essential information. Thus, computation can be reinitiated using the saved values.