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

lmcs:2208 - Logical Methods in Computer Science, January 9, 2018, Volume 14, Issue 1 - https://doi.org/10.23638/LMCS-14(1:1)2018
Compatibility Properties of Synchronously and Asynchronously Communicating ComponentsArticle

Authors: Rolf Hennicker ; Michel Bidoit

    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.


    Volume: Volume 14, Issue 1
    Published on: January 9, 2018
    Accepted on: October 27, 2017
    Submitted on: November 14, 2016
    Keywords: Computer Science - Logic in Computer Science

    2 Documents citing this article

    Consultation statistics

    This page has been seen 1421 times.
    This article's PDF has been downloaded 296 times.