Hennicker, Rolf and Bidoit, Michel - Compatibility Properties of Synchronously and Asynchronously Communicating Components

lmcs:4191 - Logical Methods in Computer Science, January 9, 2018, Volume 14, Issue 1
Compatibility Properties of Synchronously and Asynchronously Communicating Components

Authors: Hennicker, Rolf and Bidoit, Michel

We study interacting components and their compatibility with respect to synchronous and asynchronous composition. The behavior of components is formalized by I/O-transition systems. Synchronous composition is based on simultaneous execution of shared output and input actions of two components while asynchronous composition uses unbounded FIFO-buffers for message transfer. In both contexts we study compatibility notions based on the idea that any output issued by one component should be accepted as an input by the other. We distinguish between strong and weak versions of compatibility, the latter allowing the execution of internal actions before a message is accepted. We consider open systems and study conditions under which (strong/weak) synchronous compatibility is sufficient and necessary to get (strong/weak) asynchronous compatibility. We show that these conditions characterize half-duplex systems. Then we focus on the verification of weak asynchronous compatibility for possibly non half-duplex systems and provide a decidable criterion that ensures weak asynchronous compatibility. We investigate conditions under which this criterion is complete, i.e. if it is not satisfied then the asynchronous system is not weakly asynchronously compatible. Finally, we discuss deadlock-freeness and investigate relationships between deadlock-freeness in the synchronous and in the asynchronous case.

Source : oai:arXiv.org:1611.03656
DOI : 10.23638/LMCS-14(1:1)2018
Volume: Volume 14, Issue 1
Published on: January 9, 2018
Submitted on: November 14, 2016
Keywords: Computer Science - Logic in Computer Science


Consultation statistics

This page has been seen 108 times.
This article's PDF has been downloaded 40 times.