Derivation of data intensive algorithms by formal transformation: the Schorr-Waite graph marking algorithm

Date

2005-09-05

Advisors

Journal Title

Journal ISSN

ISSN

Volume Title

Publisher

Type

Article

Peer reviewed

Abstract

In this paper we consider a particular class of algorithms which present certain difficulties to formal verification. These are algorithms which use a single data structure for two or more purposes, which combine program control information with other data structures or which are developed as a combination of a basic idea with an implementation technique. Our approach is based on applying proven semantics-preserving transformation rules in a wide spectrum language. Starting with a set theoretical specification of “reachability” we are able to derive iterative and recursive graph marking algorithms using the “pointer switching” idea of Schorr and Waite. There have been several proofs of correctness of the Schorr-Waite algorithm, and a small number of transformational developments of the algorithm. The great advantage of our approach is that we can derive the algorithm from its specification using only general-purpose transformational rules: without the need for complicated induction arguments. Our approach applies equally well to several more complex algorithms which make use of the pointer switching strategy, including a hybrid algorithm which uses a fixed length stack, switching to the pointer switching strategy when the stack runs out.

Description

Dated September 19, 1996

Keywords

EPSRC

Citation

Ward, M., (1996) Derivation of data intensive algorithms by formal transformation: the Schorr-Waite graph marking algorithm. IEEE Transactions on Software Engineering, 22 (9), pp. 665-686.

Rights

Research Institute