Abstract State Machines Capture Parallel Algorithms: Correction and Extension

We consider parallel algorithms working in sequential global time, like circuits or parallel random access machines. Parallel abstract state machines (parallel ASMs) are such parallel algorithms, and the parallel ASM thesis asserts that every parallel algorithm is behaviorally equivalent to a parallel ASM. In an earlier paper 157-1, we axiomatized parallel algorithms, proved the ASM thesis and proved that every parallel ASM satisfies the axioms. It turned out, however, that the latter proof was flawed. We are forced to liberalize our axioms and allow on-the-fly creation of new parallel components. We prove the parallel thesis for the new, larger class of parallel algorithms, and we check that parallel ASMs satisfy the new axioms.