Analysis and design of distributed algorithms and protocols are difficult issues. An important cause for those difficulties is the fact that the logical structure of the solution is often invisible in the actual implementation. We introduce a framework that allows for a formal treatment of the design process, from an abstract initial design to an implementation tailored to specific architectures. A combination of algebraic and axiomatic techniques is used to verify correctness of the derivation steps. This is shown by deriving an implementation of a distributed minimum weight spanning tree algorithm in the style of [GHS].
|Title of host publication||11th Annual ACM Symposium on Principles of Distributed Computing|
|Place of Publication||Vancouver|
|Publisher||Association for Computing Machinery (ACM)|
|Number of pages||13|
|Publication status||Published - 10 Aug 1992|
Janssen, W., Janssen, W. P. M., & Zwiers, J. (1992). From Sequential Layers to Distributed Processes, Deriving a minimum weight spanning tree algorithm. In 11th Annual ACM Symposium on Principles of Distributed Computing (pp. 215-227). Vancouver: Association for Computing Machinery (ACM). https://doi.org/10.1145/135419.135461