Towards a Behavioural Theory for Random Parallel Computing

A behavioural theory comprises a set of postulates that characterise a particular class of algorithms, an abstract machine model that provably satisfies the postulates, and a proof that all algorithms stipulated by the postulates are captured by the abstract machine model. This article is dedicated to the development of a behavioural theory for random, parallel algorithms. For this first a theory for nondeterministic, parallel algorithms is developed, which captures the case of uniform distribution for the random choices made by the algorithms. This is followed by a discussion how the uniformity could be replaced by arbitrary distributionsThe research reported in this paper results from the project Behavioural Theory and Logics for Distributed Adaptive Systems supported by the Austrian Science Fund (FWF): [P26452-N15]. It was further supported by the Austrian Research Promotion Agency (FFG) through the COMET funding for the Software Competence Center Hagenber