Towards a behavioural theory for random parallel computing

K. Schewe, F. Ferrarotti, L. Tec, Q. Wang. Towards a behavioural theory for random parallel computing. pages 365-376, 1, 2016.

  • Klaus-Dieter Schewe
  • Flavio Ferrarotti
  • Loredana Tec
  • Qing Wang
  • C. Beierle
  • G. Brewka
  • M. Thimm
BuchComputational Models of Rationality. Essays Dedicated to Gabriele Kern-Isberner on the occasion of her 60th birthday
TypIn Buch
VerlagCollege Publications

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