More Web Proxy on the site http://driver.im/

research-article

Choreography conformance via synchronizability

Authors:

Tevfik BultanAuthors Info & Claims

WWW '11: Proceedings of the 20th international conference on World wide web

Pages 795 - 804

https://doi.org/10.1145/1963405.1963516

Published: 28 March 2011 Publication History

Abstract

Choreography analysis has been a crucial problem in service oriented computing. Interactions among services involve message exchanges across organizational boundaries in a distributed computing environment, and in order to build such systems in a reliable manner, it is necessary to develop techniques for analyzing such interactions. Choreography conformance involves verifying that a set of services behave according to a given choreography specification that characterizes their interactions. Unfortunately this is an undecidable problem when services interact with asynchronous communication. In this paper we present techniques that identify if the interaction behavior for a set of services remain the same when asynchronous communication is replaced with synchronous communication. This is called the synchronizability problem and determining the synchronizability of a set of services has been an open problem for several years. We solve this problem in this paper. Our results can be used to identify synchronizable services for which choreography conformance can be checked efficiently. Our results on synchronizability are applicable to any software infrastructure that supports message-based interactions.

References

[1]

J. Armstrong. Getting erlang to talk to the outside world. In Proceedings of the 2002 ACM SIGPLAN workshop on Erlang, pages 64--72, 2002.

Digital Library

[2]

G. Banavar, T. D. Chandra, R. E. Strom, and D. C. Sturman. A case for message oriented middleware. In 13th International Symposium on Distributed Computing (DISC), pages 1--18, 1999.

Digital Library

[3]

D. Brand and P. Zafiropulo. On communicating finite-state machines. J. ACM, 30(2):323--342, 1983.

Digital Library

[4]

T. Bultan, X. Fu, R. Hull, and J. Su. Conversation specification: A new approach to design and analysis of e-service composition. In Proc. 12th Int. World Wide Web Conf., pages 403--410, May 2003.

Digital Library

[5]

M. Carbone, K. Honda, N. Yoshida, R. Milner, G. Brown, and S. Ross-Talbot. A theoretical basis of communication-centred concurrent programming.

[6]

E. Clarke, O. Grumberg, and D. A. Peled. Model Checking. The MIT Press, Cambridge, Massachusetts, 1999.

Digital Library

[7]

G. Decker, A. P. Barros, F. M. Kraft, and N. Lohmann. Non-desynchronizable service choreographies. In International Conference on Service Oriented Computing (ICSOC), pages 331--346, 2008.

Digital Library

[8]

M. Fähndrich, M. Aiken, C. Hawblitzel, O. Hodson, G. C. Hunt, J. R. Larus, and S. Levi. Language support for fast and reliable message-based communication in singularity os. In Proc. 2006 EuroSys Conf., pages 177--190, 2006.

Digital Library

[9]

X. Fu, T. Bultan, and J. Su. Analysis of interacting web services. In Proc. 13th Int. World Wide Web Conf., pages 621 -- 630, New York, May 2004.

Digital Library

[10]

X. Fu, T. Bultan, and J. Su. Conversation protocols: A formalism for specification and analysis of reactive electronic services. Theoretical Computer Science, 328(1-2):19--37, November 2004.

Digital Library

[11]

X. Fu, T. Bultan, and J. Su. Synchronizability of conversations among web services. IEEE Trans. Software Eng., 31(12):1042--1055, 2005.

Digital Library

[12]

K. Honda, V. T. Vasconcelos, and M. Kubo. Language primitives and type discipline for structured communication-based programming. In 7th European Symposium on Programming on Programming Languages and Systems (ESOP'98), pages 122--138, 1998.

Digital Library

[13]

K. Honda, N. Yoshida, and M. Carbone. Multiparty asynchronous session types. In Proc. 35th Symp. on Principles of Programming Languages, pages 273--284, 2008.

Digital Library

[14]

G. C. Hunt and J. R. Larus. Singularity: rethinking the software stack. Operating Systems Review, 41(2):37--49, 2007.

Digital Library

[15]

Conversation support for agents, e-business, and component integration. http://www.research.ibm.com/convsupport.

[16]

Java API for XML messaging (JAXM). http://java.sun.com/developer/earlyAccess/xml/jaxm/.

[17]

Java Message Service. http://java.sun.com/products/jms/.

[18]

R. Kazhamiakin, M. Pistore, and L. Santuari. Analysis of communication models in web service compositions. In Proceedings of the 15th international conference on World Wide Web (WWW 2006), pages 267--276, 2006.

Digital Library

[19]

D. A. Menascé. Mom vs. rpc: Communication models for distributed applications. IEEE Internet Computing, 9(2):90--93, 2005.

Digital Library

[20]

R. Milner. Communication and Concurrency. Prentice-Hall, New York, New York, 1989.

Digital Library

[21]

Microsoft Message Queuing Service. http://www.microsoft.com/windowsserver2003/technologies/msmq/default.mspx.

[22]

Z. Stengel and T. Bultan. Analyzing singularity channel contracts. In Proceedings of the 18th International Symposium on Software Testing and Analysis (ISSTA 2009), pages 13--24, 2009.

Digital Library

[23]

M. Y. Vardi. Automata-theoretic model checking revisited. In Proceedings of the International Conference on Verification, Model Checking and Abstract Interpretation, pages 137--150, 2007.

Digital Library

[24]

S. Weerawarana, F. Curbera, F. Leymann, T. Storey, and D. F. Ferguson. Web Services Platform Architecture: SOAP, WSDL, WS-Policy, WS-Addressing, WS-BPEL, WS-Reliable Messaging, and More. Prentice Hall, March 2005.

Digital Library

Cited By

Pan XJin YXi MLi Y(2024)Deployment perspective of service pattern: Solve dynamic services with heterogeneous carrier description2024 IEEE International Conference on Web Services (ICWS)10.1109/ICWS62655.2024.00045(234-243)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ICWS62655.2024.00045
Yang LHuang BChai XLiu GWu XDai F(2024)Deadlock Analysis of Microservice Systems with Bounded Buffers2024 IEEE Cyber Science and Technology Congress (CyberSciTech)10.1109/CyberSciTech64112.2024.00027(107-114)Online publication date: 5-Nov-2024
https://doi.org/10.1109/CyberSciTech64112.2024.00027
Wang SDing ZYang RJiang C(2023)A Complex Behavioral Interaction Analysis Method for Microservice Systems With Bounded BuffersIEEE Transactions on Cloud Computing10.1109/TCC.2023.331903811:4(3713-3724)Online publication date: Oct-2023
https://doi.org/10.1109/TCC.2023.3319038
Show More Cited By

Index Terms

Choreography conformance via synchronizability

Recommendations

Deciding choreography realizability
POPL '12: Proceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

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 ...
Synchronizability of Conversations among Web Services

We present a framework for analyzing interactions among Web services that communicate with asynchronous messages. We model the interactions among the peers participating in a composite Web service as conversations, the global sequences of messages ...
Deciding choreography realizability
POPL '12

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

WWW '11: Proceedings of the 20th international conference on World wide web

March 2011

840 pages

ISBN:9781450306324

DOI:10.1145/1963405

General Chairs:
S. Sadagopan
IIIT-Bangalore, India
,
Krithi Ramamritham
IIT-Bombay, India
,
Arun Kumar
IBM Research, India
,
M. P. Ravindra
Infosys E & R, India
,
Program Chairs:
Elisa Bertino
Purdue University, USA
,
Ravi Kumar
Yahoo! Research, USA

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web
The International Institute of Information Technology Bangalore: The International Institute of Information Technology Bangalore

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 March 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

WWW '11

WWW '11: 20th International World Wide Web Conference

March 28 - April 1, 2011

Hyderabad, India

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

67
Total Citations
View Citations
252
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Pan XJin YXi MLi Y(2024)Deployment perspective of service pattern: Solve dynamic services with heterogeneous carrier description2024 IEEE International Conference on Web Services (ICWS)10.1109/ICWS62655.2024.00045(234-243)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ICWS62655.2024.00045
Yang LHuang BChai XLiu GWu XDai F(2024)Deadlock Analysis of Microservice Systems with Bounded Buffers2024 IEEE Cyber Science and Technology Congress (CyberSciTech)10.1109/CyberSciTech64112.2024.00027(107-114)Online publication date: 5-Nov-2024
https://doi.org/10.1109/CyberSciTech64112.2024.00027
Wang SDing ZYang RJiang C(2023)A Complex Behavioral Interaction Analysis Method for Microservice Systems With Bounded BuffersIEEE Transactions on Cloud Computing10.1109/TCC.2023.331903811:4(3713-3724)Online publication date: Oct-2023
https://doi.org/10.1109/TCC.2023.3319038
Di Giusto CFerre’ DLozes ENisse N(2023)Weakly Synchronous Systems with Three Machines Are Turing PowerfulReachability Problems10.1007/978-3-031-45286-4_3(28-41)Online publication date: 5-Oct-2023
https://doi.org/10.1007/978-3-031-45286-4_3
Chen BXu HYang QLu GLi H(2022)Modeling Interactions among Cyber-Physical Services2022 IEEE Intl Conf on Dependable, Autonomic and Secure Computing, Intl Conf on Pervasive Intelligence and Computing, Intl Conf on Cloud and Big Data Computing, Intl Conf on Cyber Science and Technology Congress (DASC/PiCom/CBDCom/CyberSciTech)10.1109/DASC/PiCom/CBDCom/Cy55231.2022.9927918(1-6)Online publication date: 12-Sep-2022
https://doi.org/10.1109/DASC/PiCom/CBDCom/Cy55231.2022.9927918
Filippone GPompilio CAutili MTivoli M(2022)An architectural style for scalable choreography-based microservice-oriented distributed systemsComputing10.1007/s00607-022-01139-5105:9(1933-1956)Online publication date: 10-Dec-2022
https://doi.org/10.1007/s00607-022-01139-5
Barbanera FLanese ITuosto E(2022)Formal Choreographic LanguagesCoordination Models and Languages10.1007/978-3-031-08143-9_8(121-139)Online publication date: 14-Jun-2022
https://doi.org/10.1007/978-3-031-08143-9_8
Ouederni M(2021)Compatibility checking for asynchronously communicating softwareScience of Computer Programming10.1016/j.scico.2020.102569205(102569)Online publication date: May-2021
https://doi.org/10.1016/j.scico.2020.102569
Xi MYin JWei YZhang MDeng SLi Y(2020)A Scenario-based Modeling Method for Crossover Services2020 IEEE International Conference on Services Computing (SCC)10.1109/SCC49832.2020.00010(20-29)Online publication date: Nov-2020
https://doi.org/10.1109/SCC49832.2020.00010
Autili MDi Salle AGallo FPompilio CTivoli M(2020)CHOReVOLUTION: Service choreography in practiceScience of Computer Programming10.1016/j.scico.2020.102498(102498)Online publication date: Jun-2020
https://doi.org/10.1016/j.scico.2020.102498
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents