BSP abstract state machines capture bulk synchronous prallel computations

Autoren Flavio Ferrarotti
Senén André González Cornejo
Klaus-Dieter Schewe
Editoren
Titel BSP abstract state machines capture bulk synchronous prallel computations
Typ Artikel
Journal Science of Computer Programming
Band 184
DOI 10.1016/j.scico.2019.102319
Monat October
Jahr 2019
Seiten online first
SCCH ID# 19007
Abstract

The bulk synchronous parallel (BSP) bridging model is a model for concurrent computations with alternating computation and communication phases between programs running on different processors. In a computation phase the programs proceed independently and asynchronously until a barrier is reached. In a communication phase initiated by all programs having reached the barrier only messages between the programs are exchanged until normal processing can be continued. In this article we present a behavioural theory for BSP computations comprising an axiomatisation of the BSP model, the definition of a restricted class of concurrent abstract state machines, which we call BSP abstract state machines, and the proof that BSP abstract state machines capture BSP computations as defined by the axiomatisation. We illustrate the use of BSP abstract state machines on map-reduce.