To overcome the practical limitations of partial-order runs of ‘distributed ASMs’ (Abstract State Machines) proposed by Gurevich, we have defined a concept of concurrent runs of multi-agent ASMs and could show that concurrent ASMs capture a natural language-independent axiomatic definition of concurrent algorithms, thus generalising Gurevich’s seminal ‘Sequential ASM Thesis’ from sequential to concurrent algorithms. However, we remained intrigued by the fact that Blass and Gurevich used partial-order runs of distributed ASMs to explain runs of sequential recursive algorithms. We discovered that also the inverse simulation holds: for every distributed ASM with partial order runs, these runs can be described by runs of a sequential recursive algorithm. This surprising result clarifies the difference in expressivity between partial-order and concurrent runs.
If you cannot see the document below, the PDF document is most likely not freely accessible. In this case, please try to access the document via this link.
% BibTex
@inproceedings{BorgerS20,
author = {Egon B{\"{o}}rger and
Klaus{-}Dieter Schewe},
editor = {Alexander Raschke and
Dominique M{\'{e}}ry and
Frank Houdek},
title = {A Characterization of Distributed ASMs with Partial-Order Runs},
booktitle = {Rigorous State-Based Methods - 7th International Conference, {ABZ}
2020, Ulm, Germany, May 27-29, 2020, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {12071},
pages = {78--92},
publisher = {Springer},
year = {2020},
url = {https://doi.org/10.1007/978-3-030-48077-6\_6},
doi = {10.1007/978-3-030-48077-6\_6},
timestamp = {Mon, 25 May 2020 12:33:39 +0200},
biburl = {https://dblp.org/rec/conf/asm/BorgerS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}