Ensuring consistency in long running transactions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Ensuring consistency in long running transactions

Full text

Pdf (275 KB)

Source

Automated Software Engineering archive
Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering table of contents

Atlanta, Georgia, USA

SESSION: Fault tolerance table of contents

Pages 54-63

Year of Publication: 2007

ISBN:978-1-59593-882-4

Authors

Jeffrey Fischer	University of California, Los Angeles, Los Angeles, CA
Rupak Majumdar	University of California, Los Angeles, Los Angeles, CA

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 79, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1321631.1321642 What is a DOI?

ABSTRACT

Flow composition languages permit the construction of long-running transactions from collections of independent atomic services. Due to environmental limitations, such transactions usually cannot be made to conform to standard ACID semantics. We propose set consistency, a powerful, yet intuitive, notion of consistency for long-running transactions. Set consistency considers the collection of permanent (non-intermittent) changes made by a process, when viewed at the end of its execution. Consistency requirements for such collections of changes are specified as predicates over the atomic actions of a process. Set consistency generalizes self-cancellation, a standard consistency requirement for long-running transactions, where failed processes are responsible for undoing any partially completed work. Set consistency can also express strictly stronger requirements, such as mutual exclusion or dependency.

We show that the set consistency verification problem for processes is co-NP complete and present an algorithm for verifying set consistency by reduction to propositional validity. We have implemented this algorithm and demonstrate the value and tractability of our approach on three real-world case studies. In each case, the consistency requirements can be verified within a second, demonstrating the practicality of our approach.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Business process modeling language (BPML). http://www.bpmi.org.
	2	Web services conversation language (WSCL) 1.0. http://www.w3.org/TR/wscl10.
	3	Dirk Beyer , Arindam Chakrabarti , Thomas A. Henzinger, Web service interfaces, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060770]
	4	Roberto Bruni , Michael Butler , Carla Ferreira , Tony Hoare , Hernán Melgratti , Ugo Montanari, Comparing two approaches to compensable flow composition, CONCUR 2005 - Concurrency Theory, Springer-Verlag, London, 2005 [doi>10.1007/11539452_30]
	5	Roberto Bruni , Hernán Melgratti , Ugo Montanari, Theoretical foundations for compensations in flow composition languages, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.209-220, January 12-14, 2005, Long Beach, California, USA
	6	Tevfik Bultan , Xiang Fu , Richard Hull , Jianwen Su, Conversation specification: a new approach to design and analysis of e-service composition, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775210]
	7	Michael J. Butler , Carla Ferreira, A Process Compensation Language, Proceedings of the Second International Conference on Integrated Formal Methods, p.61-76, November 01-03, 2000
	8	M. Butler and C. Ferreira. An operational semantics for StAC, a language for modelling long-running business transactions. In Coordination '04, volume 2949 of LNCS, pages 87--104. Springer, 2004.
	9	M. Butler, C. A. R. Hoare, and C. Ferreira. A trace semantics for long-running transactions. In Communicating Sequential Processes: The First 25 Years, volume 3525/2005 of LNCS, pages 133--150. Springer, 2004.
	10	NEen and NSörensson. An extensible SAT-solver. In SAT '03, pages 502--518, 2003.
	11	Ahmed K. Elmagarmid , Yungho Leu , Witold Litwin , Marek Rusinkiewicz, A Multidatabase Transaction Model for InterBase, Proceedings of the 16th International Conference on Very Large Data Bases, p.507-518, August 13-16, 1990
	12	M. Emmi and R. Majumdar. Verifying compensating transactions. In VMCAI '07. Springer, 2007.
	13	T. Andrews et al. Business process execution language for web services, May 2003. http://dev2dev.bea.com/webservices/BPEL4WS.html.
	14	H. Foster, S. Uchitel, J. Magee, and J. Kramer. Model-based verification of web service compositions. In ASE '03. IEEE, 2003.
	15	Xiang Fu , Tevfik Bultan , Jianwen Su, Analysis of interacting BPEL web services, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988756]
	16	Hector Garcia-Molina , Kenneth Salem, Sagas, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.249-259, May 27-29, 1987, San Francisco, California, United States
	17	Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
	18	Claus Hagen , Gustavo Alonso, Exception Handling in Workflow Management Systems, IEEE Transactions on Software Engineering, v.26 n.10, p.943-958, October 2000 [doi>10.1109/32.879818]
	19	J. Augusto, M. Leuschel, M. Butler, and C. Ferreira. Using the extensible model checker XTL to verify StAC business specifications. In AVoCS '03, 2003.
	20	Heiko Schuldt , Gustavo Alonso , Catriel Beeri , Hans-Jörg Schek, Atomicity and isolation for transactional processes, ACM Transactions on Database Systems (TODS), v.27 n.1, p.63-116, March 2002 [doi>10.1145/507234.507236]
	21	Inderjeet Singh , Sean Brydon , Greg Murray , Vijay Ramachandran , Thierry Violleau , Beth Stearns, Designing Web Services with the J2EE 1.4 Platform: JAX-RPC, XML Services, and Clients, Pearson Education, 2004
	22	A. P. Sistla , E. M. Clarke, The complexity of propositional linear temporal logics, Journal of the ACM (JACM), v.32 n.3, p.733-749, July 1985 [doi>10.1145/3828.3837]
	23	Chunyang Ye , S. C. Cheung , W. K. Chan, Publishing and composition of atomicity-equivalent services for B2B collaboration, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134335]