BSP abstract state machines capture bulk synchronous parallel computations

作     者：Ferrarotti, Flavio Gonzalez, Senen Schewe, Klaus-Dieter 

作者机构：Software Competence Ctr Hagenberg Hagenberg Austria P&T Connected Hagenberg Austria Zhejiang Univ UIUC Inst Haining Peoples R China 

出 版 物：《SCIENCE OF COMPUTER PROGRAMMING》 (计算机程序设计科学)

年 卷 期：2019年第184卷

页      面：102319-000页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Bulk synchronous parallel bridging model Abstract state machine Concurrent algorithm Behavioural theory 

摘      要：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. (C) 2019 Elsevier B.V. All rights reserved.