Axiomatization and characterization of BSP algorithms

DOI10.1016/J.JLAMP.2019.100479MaRDI QIDQ2011205zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• AXIOMATIC FRAMEWORKS FOR DEVELOPING BSP-STYLE PROGRAMS∗
• Direct bulk-synchronous parallel algorithms
• The bulk-synchronous parallel random access machine
• A calculus of functional BSP programs
• scientific article; zbMATH DE number 2102052

Cites work

• scientific article; zbMATH DE number 1687041 (Why is no real title available?)
• scientific article; zbMATH DE number 5999715 (Why is no real title available?)
• scientific article; zbMATH DE number 1223727 (Why is no real title available?)
• scientific article; zbMATH DE number 1343482 (Why is no real title available?)
• scientific article; zbMATH DE number 2116061 (Why is no real title available?)
• A bridging model for multi-core computing
• A data-flow approach to test multi-agent ASMs
• A new thesis concerning synchronised parallel computing -- simplified parallel ASM thesis
• ASMs and operational algorithmic completeness of lambda calculus
• Abstract State Machines
• Abstract state machines capture parallel algorithms
• Algorithmic completeness of imperative programming languages
• An ASM-characterization of a class of distributed algorithms
• An imperative language characterizing PTIME algorithms
• Classes of algorithms: formalization and comparison
• Concurrent abstract state machines
• Generating the greatest common divisor, and limitations of primitive recursive algorithms
• NestStep: Nested parallelism and virtual shared memory for the BSP model
• Normalization of Some Extended Abstract State Machines
• Palindrome recognition using a multidimensional tape.
• Sequential abstract-state machines capture sequential algorithms
• Sequential algorithms on concrete data structures
• The formal language of recursion
• Towards a definition of an algorithm

Cited in

(10)

• Preface to the special issue on formal approaches to parallel and distributed systems 2018
• A theory of partitioned global address spaces
• A bulk-synchronous parallel process algebra
• scientific article; zbMATH DE number 2102052 (Why is no real title available?)
• A programming model for BSP with partitioned synchronisation
• scientific article; zbMATH DE number 1760046 (Why is no real title available?)
• H-BSP: Hierarchical BSP computation model
• A generic cost model for concurrent and data-parallel meta-computing
• Barrier synchronisation: Axiomatisation and relaxation
• Verified scalable parallel computing with Why3

Describes a project that uses

Uses Software

• BSPedupack
• Pregel
• BSPlib

This page was built for publication: Axiomatization and characterization of BSP algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2011205)