A new thesis concerning synchronised parallel computing -- simplified parallel ASM thesis
From MaRDI portal
Abstract: A behavioural theory consists of machine-independent postulates characterizing a particular class of algorithms or systems, an abstract machine model that provably satisfies these postulates, and a rigorous proof that any algorithm or system stipulated by the postulates is captured by the abstract machine model. The class of interest in this article is that of synchronous parallel algorithms. For this class a behavioural theory has already been developed by Blass and Gurevich, which unfortunately, though mathematically correct, fails to be convincing, as it is not intuitively clear that the postulates really capture the essence of (synchronous) parallel algorithms. In this article we present a much simpler (and presumably more convincing) set of four postulates for (synchronous) parallel algorithms, which are rather close to those used in Gurevich's celebrated sequential ASM thesis, i.e. the behavioural theory of sequential algorithms. The key difference is made by an extension of the bounded exploration postulate using multiset comprehension terms instead of ground terms formulated over the signature of the states. In addition, all implicit assumptions are made explicit, which amounts to considering states of a parallel algorithm to be represented by meta-finite first-order structures. The article first provides the necessary evidence that the axiomatization presented in this article characterizes indeed the whole class of deterministic, synchronous, parallel algorithms, then formally proves that parallel algorithms are captured by Abstract State Machines (ASMs). The proof requires some recourse to methods from finite model theory, by means of which it can be shown that if a critical tuple defines an update in some update set, then also every other tuple that is logically indistinguishable defines an update in that update set.
Recommendations
Cites work
- scientific article; zbMATH DE number 1670467 (Why is no real title available?)
- scientific article; zbMATH DE number 5855088 (Why is no real title available?)
- scientific article; zbMATH DE number 1142306 (Why is no real title available?)
- A new thesis concerning synchronised parallel computing -- simplified parallel ASM thesis
- Abstract State Machines
- Abstract state machines capture parallel algorithms
- Abstract state machines capture parallel algorithms: correction and extension
- Concurrent abstract state machines
- Evolving Algebras 1993: Lipari Guide
- Foundational analyses of computation
- Foundations of information and knowledge systems. 7th international symposium, FoIKS 2012, Kiel, Germany, March 5--9, 2012. Proceedings
- Interactive Small-Step Algorithms I: Axiomatization
- Metafinite model theory
- On elementary equivalence for equality-free logic
- Sequential abstract-state machines capture sequential algorithms
- XML database transformations
Cited in
(12)- Capturing Membrane Computing by ASMs
- Distributed Adaptive Systems
- Systematic Refinement of Abstract State Machines with Higher-Order Logic
- A Logic for Reflective ASMs
- ASM specification and refinement of a quantum algorithm
- Computation on structures. Behavioural theory, logic, complexity
- Abstract state machines capture parallel algorithms: correction and extension
- Concurrent abstract state machines
- A new thesis concerning synchronised parallel computing -- simplified parallel ASM thesis
- Abstract state machines capture parallel algorithms
- A behavioural theory of recursive algorithms
- Axiomatization and characterization of BSP algorithms
This page was built for publication: A new thesis concerning synchronised parallel computing -- simplified parallel ASM thesis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q313981)
