BSP -Style Computation: A Semantic Investigation

Henry Stewart, Maurice Clint

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


A BSP (Bulk Synchronous Parallelism) computation is characterized by the generation of asynchronous messages in packages during independent execution of a number of processes and their subsequent delivery at synchronization points. Bundling messages together represents a significant departure from the traditional ‘one communication at a time’ approach. In this paper the semantic consequences of communication packaging are explored. In particular, the BSP communication structure is identified with a general form of substitution—predicate substitution. Predicate substitution provides a means of reasoning about the synchronized delivery of asynchronous communications when the immediate programming context does not explicitly refer to the variables that are to be updated (unlike traditional operations, such as the assignment $x := e$, where the names of the updated variables can be extracted from the context). Proofs of implementations of Newton's root finding method and prefix sum are used to illustrate the practical application of the proposed approach.
Original languageEnglish
Pages (from-to)174-185
Number of pages12
JournalThe Computer Journal
Volume44 (3)
Issue number3
Publication statusPublished - Jan 2001

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Hardware and Architecture
  • Information Systems
  • Software


Dive into the research topics of 'BSP -Style Computation: A Semantic Investigation'. Together they form a unique fingerprint.

Cite this