Algorithmic Completeness for BSP Languages
Yoann Marquer, Frédéric Gava · 2018
What is bulk-synchronous parallel (BSP) computing and is not? Behind this naive question, we can find complex formalisms. We first define a model that contain all BSP algorithms; This model comes with what is called abstract state machines (ASMs). Then, we prove, by using an operational semantics and a fair simulation, the algorithmic equivalence between an imperative language (with BSP routines) and the previous model. We finally give the intuition of an example that is not BSP complete.