ACM SIGPLAN Notices · 2012 · 119 citations · 19 references
ComputingComputer EngineeringComputer ScienceDistributed SystemsSystems ArchitectureSystems ModelingDistributed Systems DesignInterprocess CommunicationMessage OrderingService-oriented ArchitectureSpecification LanguagesCommunication Protocol ModelingCommunication ProtocolsRealizability TheoryService ChoreographyService-oriented CommunicationState Machine ModelsUml ModelingWeb Service Architecture
In concurrent and distributed software, message‑based choreography specifications describe permissible message orderings, but whether such specifications can be realized by a distributed system has remained an open decidability question. We provide necessary and sufficient conditions for choreography realizability and describe a corresponding decision procedure. Our implementation demonstrates that the check efficiently determines realizability for web service choreographies, Singularity OS channel contracts, and UML collaboration diagrams.
Since software systems are becoming increasingly more concurrent and distributed, modeling and analysis of interactions among their components is a crucial problem. In several application domains, message-based communication is used as the interaction mechanism, and the communication contract among the components of the system is specified semantically as a state machine. In the service-oriented computing domain such communication contracts are called "choreography" specifications. A choreography specification identifies allowable ordering of message exchanges in a distributed system. A fundamental question about a choreography specification is determining its realizability, i.e., given a choreography specification, is it possible to build a distributed system that communicates exactly as the choreography specifies? Checking realizability of choreography specifications has been an open problem for several years and it was not known if this was a decidable problem. In this paper we give necessary and sufficient conditions for realizability of choreographies. We implemented the proposed realizability check and our experiments show that it can efficiently determine the realizability of 1) web service choreographies, 2) Singularity OS channel contracts, and 3) UML collaboration (communication) diagrams.
19
E. M. Clarke, Orna Grümberg, D. Long · 1996 · 6.9K citations
On Communicating Finite-State Machines
Daniël Brand, P. Zafiropulo · Journal of the ACM · 1983 · 1.1K citations · Full text
Multiparty asynchronous session types
Kohei Honda, Nobuko Yoshida, Marco Carbone · 2008 · 659 citations · Full text
J. Roy, A. K. Ramanujan · IT Professional · 2001 · 345 citations
Galen Hunt, James R. Larus · ACM SIGOPS Operating Systems Review · 2007 · 307 citations · Full text