On the parallel computation thesis

Nachum Dershowitz, Eugenia Falkovich-Derzhavetz, "On the parallel computation thesis", in Logic Journal of IGPL, Oxford University Press, 2016.

Abstract

We develop a generic programming language for parallel algorithms, one that works for all data structures and control structures. We show that any parallel algorithm satisfying intuitively-appealing postulates can be modelled by a collection of cells, each of which is an abstract state machine, augmented with the ability to spawn new cells. The cells all run the same algorithm and communicate via a shared global memory. Using a formal definition of what makes such an algorithm effective, we prove the validity of the Parallel Computation Thesis, according to which all reasonable parallel models of computation have roughly equivalent running times.

Full text (PDF on Oxfordjournals.org)