Axiomatization and characterization of BSP algorithms

DOI10.1016/j.jlamp.2019.100479zbMath1435.68187OpenAlexW2964482874MaRDI QIDQ2011205

Yoann Marquer, Frédéric Gava

Publication date: 28 November 2019

Published in: Journal of Logical and Algebraic Methods in Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jlamp.2019.100479

zbMATH Keywords

semanticsaxiomatizationASMBSPalgorithmic completeness

Mathematics Subject Classification ID

Semantics in the theory of computing (68Q55) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) General topics in the theory of algorithms (68W01)

Related Items

Preface to the special issue on formal approaches to parallel and distributed systems 2018

Uses Software

• BSPlib
• Pregel
• BSPedupack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Concurrent abstract state machines
• A new thesis concerning synchronised parallel computing -- simplified parallel ASM thesis
• A data-flow approach to test multi-agent ASMs
• A bridging model for multi-core computing
• Sequential algorithms on concrete data structures
• Palindrome recognition using a multidimensional tape.
• Generating the greatest common divisor, and limitations of primitive recursive algorithms
• NestStep: Nested parallelism and virtual shared memory for the BSP model
• Towards a Definition of an Algorithm
• An ASM-Characterization of a Class of Distributed Algorithms
• The formal language of recursion
• Normalization of Some Extended Abstract State Machines
• ASMs and Operational Algorithmic Completeness of Lambda Calculus
• Abstract State Machines
• Algorithmic Completeness of Imperative Programming Languages
• Abstract state machines capture parallel algorithms
• Sequential abstract-state machines capture sequential algorithms