Mangala Gowri Nanda
Satish Chandra
Vivek Sarkar
ABSTRACT
Distributed enterprise applications today are increasingly being built from services available over the web. A unit of functionality in this framework is a web service, a software application that exposes a set of "typed'' connections that can be accessed over the web using standard protocols. These units can then be composed into a <i>composite</i> web service. BPEL (Business Process Execution Language) is a high-level distributed programming language for creating composite web services.
Although a BPEL program invokes services distributed over several servers, the <i>orchestration</i> of these services is typically under centralized control. Because performance and throughput are major concerns in enterprise applications, it is important to remove the inefficiencies introduced by the centralized control. In a distributed, or decentralized orchestration, the BPEL program is partitioned into independent sub-programs that interact with each other without any centralized control. Decentralization can increase parallelism and reduce the amount of network traffic required for an application.
This paper presents a technique to partition a composite web service written as a single BPEL program into an equivalent set of decentralized processes. It gives a new code partitioning algorithm to partition a BPEL program represented as a program dependence graph, with the goal of minimizing communication costs and maximizing the <i>throughput</i> of multiple concurrent instances of the input program. In contrast, much of the past work on dependence-based partitioning and scheduling seeks to minimize the <i>completion time</i> of a single instance of a program running in isolation. The paper also gives a cost model to estimate the throughput of a given code partition.
- WebSphere Application Server. http://www-3.ibm.com/software/info1/websphere/index.jsp?tab=products/appserv.Google Scholar
- WBaxter and IHR. Bauer. The program dependence graph and vectorization. In Proceedings of the ACM Symposium on Principles of Programming Languages, 1989. Google ScholarDigital Library
- S. H. Bokhari. Partitioning Problems in Parallel, Pipelined, and Distributed Computing. IEEE Transactions on Computers, C-37:48--57, January 1988. Google ScholarDigital Library
- Business Process Execution Language for Web Services Version 1.1. http://www.ibm.com/developerworks/library/ws-bpel/.Google Scholar
- BPWS4J: Java Run Time for BPEL4WS. http://www.alphaworks.ibm.com/tech/bpws4j.Google Scholar
- J. Ferrante, K. Ottenstein, and J. Warren. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems, 9:319--349, July 1987. Google ScholarDigital Library
- A. Gerasoulis, S. Venugopal, and T. Yang. Clustering Task Graphs for Message Passing Architectures. Proceedings of the ACM 1990 International Conference on Supercomputing, pages 447--456, June 1990. Amsterdam, the Netherlands. Google ScholarDigital Library
- R. L. Graham. Bounds on Multiprocessing Timing Anomalies. SIAM Journal on Applied Mathematics, 17(2):416--429, March 1969.Google ScholarDigital Library
- S. Graham, S. Simeonov, T. Boubez, G. Daniels, D. Davis, Y. Nakamura, and R. Neyama. Building Web Services with Java: Making sense of XML, SOAP, WSDL and UDDI. Sams; ISBN:0672321815, 2001. Google ScholarDigital Library
- S. Horwitz, J. Prins, and T. Reps. Integrating Non-Interfering Versions of Programs. Conf. Rec. Fifteenth ACM Symposium on Principles of Programming Languages, pages 133--145, January 1988. Google ScholarDigital Library
- R. Khalaf, N. Mukhi, and S. Weerawarana. Service-Oriented Composition in BPEL4WS. In Proceedings of the Twelfth International World Wide Web Conference, 2003.Google Scholar
- J. Krinke. Static slicing of threaded programs. In Program analysis for software tools and engineering (PASTE 98), pages 35--42. ACMSOFT, 1998. Google ScholarDigital Library
- P. Muth, D. Wodtke, J. Weissenfels, D. A. Kotz, and G. Weikum. From centralized workflow specification to distributed workflow execution. Journal of Intelligent Information Systems (JIIS), 10(2), 1998. Google ScholarDigital Library
- R. Reiter. Scheduling Parallel Computations. Journal of the ACM, 4(15):590--599, 1968. Google ScholarDigital Library
- V. Sarkar. Partitioning and Scheduling Parallel Programs on Multiprocessors. Research Monographs in Parallel and Distributed Computing. MIT Press, Cambridge, MA, 1989. Google ScholarDigital Library
- V. Sarkar. Automatic Partitioning of a Program Dependence Graph into Parallel Tasks. IBM Journal of Research and Development, 35(5/6), 1991. Google ScholarDigital Library
- V. Sarkar. A Concurrent Execution Semantics for Parallel Program Graphs and Program Dependence Graphs. Springer-Verlag Lecture Notes in Computer Science, 757:16--30, 1992. Proceedings of the Fifth Workshop on Languages and Compilers for Parallel Computing, Yale University, August 1992. Google ScholarDigital Library
- A. Singh and S. Pande. Compiler optimizations for Java aglets in distributed data intensive applications. In Proceedings of the ACM Symposium on Applied Computing, pages 87--92, 2002. Google ScholarDigital Library
- S. Singhai and K. McKinley. Loop fusion for data locality and parallelism. In Proceedings of the Mid-Atlantic Student Workshop on Programming Languages and Systems, 1996.Google Scholar
- J. Subhlok, D. O'Hallaron, T. Gross, P. Dinda, and J. Webb. Communication and memory requirements as the basis for mapping task and data parallel programs. In Proceedings of Supercomputing, pages 330--339, Washington, DC, November 1994. Google ScholarDigital Library
- J. Subhlok and G. Vondran. Optimal latency-throughput tradeoffs for data parallel pipelines. In Proceedings of the Eighth Annual ACM Symposium on Parallel Algorithms and Architecture (SPAA), Padua, Italy, June 1996. Google ScholarDigital Library
- E. Tilevich and Y. Smaragdakis. J-Orchestra: Automatic Java application partitioning. In Proceedings of European Conference on Object Oriented Programming (ECOOP'02), 2002. Google ScholarDigital Library
- T. Yang and A. Gerasoulis. DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors. IEEE Transactions on Parallel and Distributed Systems, 5(9):951--967, 1994. Google ScholarDigital Library
- D. Zhou, S. Pande, and K. Schwan. Method partitioning - runtime customization of pervasive programs without design-time application knowledge. In Proceedings of the 23rd International Conference on Distributed Computing Systems (ICDCS'03), 2003. Google ScholarDigital Library
Index Terms
- Decentralizing execution of composite web services
Recommendations
Decentralized orchestration of composite web services
WWW Alt. '04: Proceedings of the 13th international World Wide Web conference on Alternate track papers & postersWeb services make information and software available programmatically via the Internet and may be used as building blocks for applications. A composite web service is one that is built using multiple component web services and is typically specified ...
Decentralizing execution of composite web services
OOPSLA '04Distributed enterprise applications today are increasingly being built from services available over the web. A unit of functionality in this framework is a web service, a software application that exposes a set of "typed'' connections that can be ...
Synchronization analysis for decentralizing composite Web services
SAC '03: Proceedings of the 2003 ACM symposium on Applied computingWeb Services are emerging as the standard mechanism for making information and software available programmatically via the Internet, and as building blocks for applications. A composite web service may be built using multiple component web services. ...
Comments