From Sequential Layers to Distributed Processes, Deriving a minimum weight spanning tree algorithm

Wil Janssen; W.P.M. Janssen; Jakob Zwiers

doi:10.1145/135419.135461

From Sequential Layers to Distributed Processes, Deriving a minimum weight spanning tree algorithm

Wil Janssen, W.P.M. Janssen, Jakob Zwiers

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

17 Citations (Scopus)

205 Downloads (Pure)

Abstract

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].

Original language	Undefined
Title of host publication	11th Annual ACM Symposium on Principles of Distributed Computing
Place of Publication	Vancouver
Publisher	Association for Computing Machinery
Pages	215-227
Number of pages	13
ISBN (Print)	9780897914956
DOIs	https://doi.org/10.1145/135419.135461
Publication status	Published - 10 Aug 1992
Event	PODC '92, the eleventh annual ACM symposium on Principles of distributed computing - Vancouver Duration: 1 Jan 1992 → 1 Jan 1992

Publication series

Name
Publisher	ACM

Conference

Conference	PODC '92, the eleventh annual ACM symposium on Principles of distributed computing
Period	1/01/92 → 1/01/92

Keywords

IR-101739
METIS-119894

Access to Document

10.1145/135419.135461

sequentia

Cite this

@inproceedings{2054134969c04494bc971b9a6186277e,

title = "From Sequential Layers to Distributed Processes, Deriving a minimum weight spanning tree algorithm",

abstract = "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].",

keywords = "IR-101739, METIS-119894",

author = "Wil Janssen and W.P.M. Janssen and Jakob Zwiers",

year = "1992",

month = aug,

day = "10",

doi = "10.1145/135419.135461",

language = "Undefined",

isbn = "9780897914956",

publisher = "Association for Computing Machinery",

pages = "215--227",

booktitle = "11th Annual ACM Symposium on Principles of Distributed Computing",

address = "United States",

note = "PODC '92, the eleventh annual ACM symposium on Principles of distributed computing ; Conference date: 01-01-1992 Through 01-01-1992",

}

Janssen, W, Janssen, WPM & 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. Association for Computing Machinery, Vancouver, pp. 215-227, PODC '92, the eleventh annual ACM symposium on Principles of distributed computing, 1/01/92. https://doi.org/10.1145/135419.135461

From Sequential Layers to Distributed Processes, Deriving a minimum weight spanning tree algorithm. / Janssen, Wil; Janssen, W.P.M.; Zwiers, Jakob.
11th Annual ACM Symposium on Principles of Distributed Computing. Vancouver: Association for Computing Machinery, 1992. p. 215-227.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - From Sequential Layers to Distributed Processes, Deriving a minimum weight spanning tree algorithm

AU - Janssen, Wil

AU - Janssen, W.P.M.

AU - Zwiers, Jakob

PY - 1992/8/10

Y1 - 1992/8/10

N2 - 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].

AB - 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].

KW - IR-101739

KW - METIS-119894

U2 - 10.1145/135419.135461

DO - 10.1145/135419.135461

M3 - Conference contribution

SN - 9780897914956

SP - 215

EP - 227

BT - 11th Annual ACM Symposium on Principles of Distributed Computing

PB - Association for Computing Machinery

CY - Vancouver

T2 - PODC '92, the eleventh annual ACM symposium on Principles of distributed computing

Y2 - 1 January 1992 through 1 January 1992

ER -