On the Design and Verification of a Simple Distributed Spanning Tree Algorithm 1
Manfred Broy · 1995
The design of a distributed algorithm for computing a minimal distance spanning tree is carried out as a case study for the systematic derivation of a distributed algorithm in a functional setting. A distributed algorithm is derived and proved correct. 1. Introduction In designing algorithms for the solution of informally given problems the major steps consist in the adequate formalisation of the problem, the design of an algorithmic solution, its verification and optimization. It has been proved useful not to do all these steps isolated, but structuring and connecting them in some adequate way. Such a proceeding has been widely recognized as possible and demonstrated useful for numerous cases of sequential programs. Maybe, it is less widely recognized that such a proceeding also works for distributed algorithms. 1 This work was supported by the Sonderforschungsbereich 342 Werkzeuge und Methoden für die Nutzung paralleler Architekturen PARSTA 2 05.05.1995 In the following we use tr...