A Behavioural Thesis of Synchronous Parallel Algorithms -- Correction of the Simplified Parallel ASM Thesis
arXiv:1504.06203 · doi:10.1016/j.tcs.2016.08.013
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, though mathematically correct, fails to be convincing, as it is not intuitively clear that the postulates really capture the essence of (synchronous) parallel algorithms. We present a much simpler (and presumably more convincing) set of four postulates for (synchronous) parallel algorithms, which are close to those of Gurevich's sequential ASM thesis. The key difference is 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 representing states of a parallel algorithm by meta-finite first-order structures. The article first provides evidence that the axiomatization characterizes the whole class of deterministic, synchronous, parallel algorithms, then formally proves that parallel algorithms are captured by Abstract State Machines (ASMs). The proof uses the requirement of the bounded exploration postulate that update sets be uniformly definable, by equality-free first-order formulae, in the finite critical structures determined by the witness terms; these formulae are translated into the guards of a parallel ASM rule. This version corrects the characterization proof of the first version, whose key lemma was false; the bounded exploration postulate has been amended accordingly.
arXiv comment52 pages. v2 corrects v1: Lemma 7.11 of v1 is false and the characterization theorem fails under the original postulates. The bounded exploration postulate now requires uniformly definable updates, and the theorem is proved anew. Title changed. A revised form of v1 appeared in Theor. Comput. Sci. 649 (2016) 25-53; a corrigendum has been submitted to the same journal