Towards a behavioural theory for random parallel computing
Autoren |
Klaus-Dieter Schewe Flavio Ferrarotti Loredana Tec Qing Wang |
Editoren |
C. Beierle G. Brewka M. Thimm |
Titel | Towards a behavioural theory for random parallel computing |
Buchtitel | Computational Models of Rationality. Essays Dedicated to Gabriele Kern-Isberner on the occasion of her 60th birthday |
Typ | in Buch |
Verlag | College Publications |
ISBN | 978-1848901988 |
Monat | January |
Jahr | 2016 |
Seiten | 365-376 |
Abstract | 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. |