Minimal Translations from Synchronous Communication to Synchronizing Locks

Manfred Schmidt-Schauß
(Goethe-Universität Frankfurt am Main)
David Sabel
(LMU München)

In order to understand the relative expressive power of larger concurrent programming languages, we analyze translations of small process calculi which model the communication and synchronization of concurrent processes. The source language SYNCSIMPLE is a minimalistic model for message passing concurrency while the target language LOCKSIMPLE is a minimalistic model for shared memory concurrency. The former is a calculus with synchronous communication of processes, while the latter has synchronizing mutable locations – called locks – that behave similarly to binary semaphores. The criteria for correctness of translations is that they preserve and reflect may-termination and must-termination of the processes. We show that there is no correct compositional translation from SYNCSIMPLE to LOCKSIMPLE that uses one or two locks, independent from the initialisation of the locks. We also show that there is a correct translation that uses three locks. Also variants of the locks are taken into account with different blocking behavior.

In Ornela Dardha and Valentina Castiglioni: Proceedings Combined 28th International Workshop on Expressiveness in Concurrency and 18th Workshop on Structural Operational Semantics (EXPRESS/SOS 2021), Paris, France (online event), 23rd August 2021, Electronic Proceedings in Theoretical Computer Science 339, pp. 59–75.
Published: 23rd August 2021.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: