Abstract
Designers of network algorithms give elegant informal descriptions of the intuition behind their algorithms (see [GHS83, Hu83, MS79, Se82, Se83, ZS80]). Usually, these descriptions are structured as if tasks or subtasks are performed sequentially. From an operational point of view, however, they are performed concurrently. Here, we present a design principle that formally describes how to develop algorithms according to such sequentially phased explanations. The design principle is formulated using Manna and Pnueli's linear time temporal logic [MP83]. This principle, together with Chandy and Misra's technique [CM88] or Back and Sere's technique [BS89] for designing parallel algorithms, is applicable to large classes of algorithms, such as those for minimum-path, connectivity, network flow, and minimum-weight spanning trees. In particular, the distributed minimum-weight spanning tree algorithm of Gallager, Humblet, and Spira [GHS83] is structured according to our principle.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Apt K.R., Francez N., and de Roever W.P., A proof system for communicating sequential processes, ACM TOPLAS, 2–3 (1980).
Boruvka O., O jistém problému minimálním, Práca Moravské Prírodovedecké Spolecnosti (1926) (in Czech.).
Back R.J.R. and Sere K., Stepwise refinement of action systems, Proc. of the international conference of mathematics and program construction (1989).
Chou C.T. and Gafni E., Understanding and verifying distributed algorithms using stratified decomposition, Proc. of the ACM Symp. on Principles of Distr. Comp. (1988).
Chandy K.M and Lamport L., Distributed snapshots: determining global states of distributed systems, ACM Trans. on Comp. Syst. 3-1 (1985).
Chandy K.M. and Misra J., Parallel program design: a foundation, Addison-Wesley Publishing Company, Inc. (1988).
Dijkstra E.W. and Scholten C.S., Termination detecting for diffusing computations, Letters 1–4 (1980).
Even S., Graph algorithms, Computer Science Press, Inc.(USA), (1979).
Elrad T. and Francez N., Decomposition of distributed programs into communication closed layers, Science of Computer programming, 2 (1982).
Francez N., Distributed termination, ACM-TOPLAS, 2-1 (1980).
Fix L. and Francez N., Semantics-driven decompositions for the verification of distributed programs, manuscript (1989).
Gallager R.T., Humblet P.A., and Spira P.M., A distributed algorithm for minimum-weight spanning trees, ACM TOPLAS, 5-1 (1983).
Gerth R.T. and Shrira L., On proving closedness of distributed layers, LNCS-241 (1986).
Humblet P.A., A distributed algorithm for minimum-weight directed spanning trees, IEEE Trans. on Comm., 31-6 (1983).
Katz S. and Peled D., Interleaving set temporal logic, Proc. of the ACM Symp. on Principles of Distr. Comp. (1987).
Katz S. and Peled D., An efficient verification method for parallel and distributed programs, Proc. of the REX-workshop (1988).
Lamport L., Paradigms for distributed programs: computing global states. LNCS-190 (1985).
Manna Z. and Pnueli A., Verification of concurrent programs: A temporal proof system, Foundations of computer science IV, part 2, MC-tracts 159 (1983).
Merlin P.M. and Segall A., A failsafe distributed routing protocol, IEEE Trans. on Comm., 27-9 (1979).
Pandya P.K., Compositional verification of distributed programs, Ph.D. thesis, Tata institute of fundamental research, Bombay, India (1988).
Segall A., Decentralized maximum-flow algorithms, Networks 12 (1982).
Segall A., Distributed network protocols, IEEE Trans. on Inf. Theory. IT29-1 (1983).
Stomp F.A. and de Roever W.P., A correctness proof of a distributed minimum-weight spanning tree algorithm (extended abstract), Proc. of the 7th ICDCS (1987).
Stomp F.A. and de Roever W.P., A fully worked out correctness proof of Gallager, Humblet, and Spira's minimum-weight spanning tree algorithm, Internal Report 87-4, University of Nijmegen (1987).
Stomp F.A. and de Roever W.P., A formalization of sequentially phased intuition in network protocols, Internal Report 88-15, University of Nijmegen (1988).
Stomp F.A. and de Roever W.P., Designing distributed algorithms by means of sequentially phased reasoning (full paper), Internal Report 89-8, University of Nijmegen (1989).
Schlichting R.D. and Schneider F.B., Using message passing for distributed programming, Proof rules and disciplines, ACM TOPLAS 6-3 (1984).
Welch J.L., Lamport L., and Lynch N.A., A lattice-structured proof of a minimum spanning tree algorithm, Proc. of the ACM Symp. on Principles of Distr. Comp. (1988).
Zerbib F.B.M. and Segall A., A distributed shortest path protocol, Internal Report EE-395, Technion-Israel Institute of Technology, Haifa, Israel (1980).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Stomp, F.A., de Roever, W.P. (1989). Designing distributed algorithms by means of formal sequentially phased reasoning. In: Bermond, JC., Raynal, M. (eds) Distributed Algorithms. WDAG 1989. Lecture Notes in Computer Science, vol 392. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-51687-5_47
Download citation
DOI: https://doi.org/10.1007/3-540-51687-5_47
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-51687-3
Online ISBN: 978-3-540-46750-2
eBook Packages: Springer Book Archive