The Decentralized Data Dependency (D3) Analysis Project

Year 3 Findings Summary

3/16/2010

 

Title: SRS: A Decentralized and Rule-Based Approach to Data Dependency Analysis and Failure Recovery in a Service-Oriented Environment

P.I.: Susan D. Urban

NSF Grant No: CCF-0820152

Period Covered: Project year beginning 6/01/2010

Our findings for year three build on our results from the first two years [1-3], with additional publications in [4-8] and publications in progress in [9-14].

 

Findings for the Assurance Point Approach to Service Composition and Recovery [4-7, 11]

 

The introduction of service-oriented computing has created a more dynamic environment for the composition of software applications, where processes are affected by events and data changes and also pose data consistency issues that must be considered in application design and development. This research has addressed the need to develop a more effective means to model the dynamic aspects of processes in contemporary, distributed applications, especially in the context of concurrently executing processes that access shared data and cannot enforce traditional transaction properties.

In particular, this research has extended an abstract execution model for establishing user-defined correctness and recovery in a service composition environment. The service composition model defines a hierarchical service composition structure, where a service is composed of atomic and/or composite groups. The model provides multi-level protection against service execution failure by using compensation and contingency at different composition granularity levels. The model is enhanced with the concept of assurance points (APS) and integration rules, where APs serve as logical and physical checkpoints for user-defined consistency checking, invoking integration rules that check pre and post conditions at different points in the execution process. The unique aspect of APs is that they provide intermediate rollback points when failures occur, thus allowing a process to be compensated to a specific AP for the purpose of rechecking pre-conditions before retry attempts. APs also support a dynamic backward recovery process, known as cascaded contingency, for hierarchically nested processes in an attempt to recover to a previous AP that can be used to invoke contingent procedures or alternate execution paths for failure of a nested process. As a result, the assurance point approach provides flexibility with respect to the combined use of backward and forward recovery options.

Petri Nets have been used to define the semantics of the assurance point approach to service composition and recovery with integration rules. Over the next year, the Petri Net formalization will be extended to include the semantics of additional rule forms that are a part of the AP recovery model and to also define the semantics of APs in the context of flow groups that support parallel execution within a process.

As part of our research, we have also compared recovery procedures of the AP model to those of BPEL. The work in [15] highlights the two main problems with the fault and compensation mechanism in the current BPEL standard: 1) compensation order can violate control link dependencies if control links cross the scope boundaries, and 2) high complexity of default compensation order due to default handler behavior. The AP model also honors control links between peer-scopes. Unlike BPEL, however, the order of compensation is clear since the AP approach does not support control links between non-peer scopes, making the semantics of compensation in the AP approach unambiguous. In addition, the AP model supports a hierarchical structure during compensation as promoted in [15].

In general, the notion of compensation should also be capable of handling constraint violations [16]. Since BPEL’s compensation handling mechanism through the activity can only be called inside a fault handler, this limits the ability to call compensation outside a fault handling. Thus, a fault has to occur to invoke a compensation procedure. In the case of the AP model, compensation can be invoked during normal execution (no error has yet occurred) when integration rules are not satisfied. This allows a flexible way to recover the process through compensation in response to constraint violations.

BPEL does not explicitly support a contingency feature other than fault, exception, and termination handlers. The designer is also responsible for complex fault handling logic, which, as pointed out in [15-16], has the potential to increase complexity and create unexpected errors. The AP model provides explicit contingency activities so that forward recovery is possible. Compared to BPEL, the AP logic allows designers to have a clearer notion of how recovery actions take place and at the same time provides flexibility through different recovery actions depending upon the status of execution and user-defined integration rule conditions. In addition to integration rules, the AP model also supports the use of two additional rules forms known as invariants and application exception rules.  

 

Findings for Invariants [6, 8-9]

 

This research has developed the concept of invariants for monitoring data in an environment that allows concurrent data accessibility with relaxed isolation. The invariant approach is an extension of the assurance point concept, where an assurance point is a logical and physical checkpoint that is used to store critical data values, to express a post-condition for completed service, and to express a pre-condition for the next service to execute. Invariants provide a stronger way of monitoring constraints and guaranteeing that a condition holds for a specific duration of execution as defined by starting and ending assurance points, using the change notification capabilities of Delta-Enabled Grid Services (DEGS). Research results include the specification of invariants as well as the invariant monitoring system for activating invariants, evaluating and re-evaluating invariant conditions, and deactivating invariants. Algorithms are also presented for the delta analysis agent of the system, which is responsible for filtering data changes from DEGS against the monitored objects of the active invariants. The system is supported by an invariant evaluation web service that uses materialized views for more efficient re-evaluation of invariant conditions. This research includes a performance analysis of the invariant evaluation Web Service, illustrating the benefits of using materialized views. The strength of the invariant technique is that it provides a way to monitor data consistency in an environment where the coordinated locking of data items across multiple service executions is not possible, thus providing better support for reliability and maintenance of user-defined correctness conditions among concurrent processes.

 

Findings for Application Exception Rules [6,10]

 

This research introduces the concept of Application Exception Rules (AERs), integrated with the use of data dependency analysis, to provide an efficient and flexible way of handling exceptions and maintaining data consistency in concurrent process execution. An AER is a rule that specifies recovery actions to be carried out based on the execution status of the corresponding process. AERs build on past work with Assurance Points (APs) and integration rules, where an AP is a logical checkpoint within a process that provides a way to check constraints and respond to failures. Integration rules that are associated with APs allow a process to respond to internal events, where an internal event is an error that occurs during process execution. AERs extend integration rules with a case-based structure that is used to respond to external events, where external events are interrupts received from the environment external to a process. An AER allows a process to respond variably to exceptions instead of giving a fixed response, using the current AP status of a process to determine the recovery actions to take. The development of AERs includes the integration of the AP recovery techniques with a data dependency analysis algorithm that enables the partial recovery of a process to identify and inform other concurrently-running processes that may be data dependent on the recovered process, where dependent processes are notified by also using AERs. The AER system provides support for flexible constraint checking and failure recovery, more complete exception handling by handling both internal and external events, and addressing data consistency issues in the environment by communicating failure recovery to dependent processes.

 

Findings from Undergraduate Researchers Supported through the NSF REU Supplement and the NSF REU Site Program:

 

Jonathan Rodriguez, Texas Tech University
Title: Formalization and Verification of Assurance Points by Means of Colored Petri Nets

Abstract: As the use of web services continues to grow, the need for better recovery methods for software processes increases as well. A method that has been introduced to address recovery in service composition is the use of Assurance Points (APs). Using the idea of checkpoints and user-defined constraints, APs use integration rules as a way to check correctness conditions and to invoke backward and forward recovery actions, using APs as intermediate rollback points within a process. Although the concept of APs has been introduced, APs have not yet been formalized. This research focuses on using Colored Petri Nets (CPNs) to model the semantics of Assurance Points and its recovery functionality for rollback, retry, and cascaded contingency [13]. The graphical notation and exact mathematical definition of CPNs make it a suitable tool to model information systems, verify whether the design operates correctly, and eliminate dead paths in a process flow. As part of this research, CPN models were first designed and tested for a service composition and recovery model. The models were then extended to define and verify Assurance Point semantics and to demonstrate AP recovery functionality by simulating errors and observing recovery response to errors. The CPN specification provides a formal definition of Assurance Points that clarifies the semantics of the recovery actions in the context of the service composition model.

Mary Shuman, University of North Carolina, Charlotte
Title: A Database Service for Checking Invariants

Abstract: When web services run collaboratively, concurrently executing processes may be accessing the same shared data. Assurance Points (APs) insure the consistency of data in service-oriented environments because they check user defined conditions, tracking pre and post conditions in-between the service calls of a process. An extension to APs is investigating the use of invariants, which are user-defined data correctness conditions that can be monitored between the APs of a process. To support the development of the invariant system, this research focused on the development of a web service for testing invariant conditions [6, 8-9]. The web service accepts as input the invariant identification number, an SQL query, and a list of tables associated with the query. The web service then executes the query to test the invariant condition. Since the invariant may need to be checked multiple times between the starting and ending APs of an invariant, a materialized view is constructed to improve the performance of re-checking the invariant, where the view is immediately refreshed when relevant data changes occur. Rechecking the invariant condition then uses a query that counts the tuples of the refreshed view rather than performing a complete re-execution of the query. The invariant-checking web service has been incorporated into the invariant monitoring extension to APs as a way to monitor the status of data correctness conditions during process execution.

Jamere Veldez Joshua, Indiana University
Title: Analysis and Comparison of Assurance Points with Aspect-Oriented Programming to Assess Iteration and Recovery

Abstract: Web Service Composition is used to define the logical flow of a business process as well as data transfer points during different pivotal points of the process. Due to the current organization of current web service composition languages, such as the Business Process Execution Language (BPEL), issues regarding access control, auditing, authentication, business rules, exception handling, and classes of service cannot be easily accommodated and often disrupt the current business model. These concerns raise the issue of providing support for crosscutting functionality. Assurance Points (APs) are one current form of crosscutting functionality, providing logical and physical checkpoints within a process that are capable of checking user-defined constraints, invoking forward and backward recovery actions, and using assurance points as intermediate rollback points. Aspect-Oriented Programming (AOP) is another form of crosscutting functionality that is used to add, edit, and delete current business processes without actually changing the base functionality code. This research has focused on a comparison of APs and AOP, examining the basic functionality of each paradigm and evaluating each approach with respect to the use of iteration and recovery [14]. An ultimate goal of this research is to assess the potential combination of the two paradigms through the integration of APs into Aspect-Oriented BPEL.

Zev Friedman, Texas Tech University
Title: Extension of the Assurance Point (AP) Concept to Concurrently Executing Web Services within a Single Business Process

Abstract: With the emergence of the Internet as a powerful communication tool, many businesses have begun turning to distributed computing for performing processes which can be broken into smaller pieces. This has led to the use of online web services that perform specific tasks and subsequently the creation of the service-oriented computing paradigm. With processes separated by organization and location, ensuring data consistency in a service-oriented environment is a challenge. The concept of Assurance Points (APs) provides a new approach to addressing data consistency in processes composed of service invocations. APs allow for checking of user-defined correctness conditions at different points during the execution of a business process, along with options for recovery actions to take if those conditions are not met. APs also serve as intermediate rollback points from which forward recovery can take place without having to reset an entire process when an error occurs. The initial definition of the AP concept focused on defining the semantics of recovery conditions known as rollback, retry, and cascaded contingency, assuming a sequential execution of services. This research has extended the AP concept to define the semantics of recovery conditions for concurrently executing threads, known as flow groups, within a process [12]. In particular, this research has defined the placement of APs for use with flow groups and the flow group recovery semantics for rollback, retry, and cascaded contingency in the presence of parallelism. As a simplifying assumption, the semantics assume that there are no data dependencies among threads. The recovery semantics have also been designed to minimize rollback and recovery activities for concurrent threads within a flow group. This research has also included a detailed assessment of the current AP prototype, with new directions for a revised software architecture that can support the flow group recovery semantics as well as other future AP extensions.

 

References

1. Urban, S. D., Liu, Z., and Gao, L., “Decentralized Data Dependency Analysis for Concurrent Process Execution,” Workshop on Middleware for Web Services, held in conjunction with the 13th International EDOC Conference, Auckland, New Zealand, September, 2009, pp. 74-83.

2. Liu, Ziao, Decentralized Data Dependency Analysis for Concurrent Process Execution, M.S. Thesis, Texas Tech University, Department of Computer Science, Fall 2009.

3. Urban, S. D., Liu, Z., and Gao, L., “Decentralized Communication for Data Dependency Analysis Among Process Execution Agents,” submitted for publication to the International Journal of Web Services Research, 2010.

4. Shrestha, R., Using Assurance Points and Integration Rules for Recovery in Service Composition, M.S. Thesis, Texas Tech University, Department of Computer Science, Spring 2010.

5. Urban, S. D., Gao, L., Shrestha, R., and Courter, A., “Achieving Recovery in Service Composition with Assurance Points and Integration Rules,” Proceedings of the Cooperative Information Systems Conference (Crete, Greece) as part of On the Move (OTM) 2010, Part 1, Lecture Notes in Computer Science 6426, Springer, Heidelberg, pp. 428-437.

6. Urban, S. D. and Gao, L., “The Dynamics of Process Modeling: New Directions for the Use of Events and Rules in Service-Oriented Computing,” The Evolution of Conceptual Modeling: From a Historical Perspective towards the Future of Conceptual Modeling, R. Kaschek and L. Delcambre (editors), Lecture Notes in Computer Science 6520, pp. 205-224, Springer, Heidelberg, 2011.

7. Susan D. Urban, Le Gao, Rajiv Shrestha, Yang Xiao, Zev Friedman, Jonathan Rodriguez, “The Assurance Point Model for Consistency and Recovery in Service Composition,” to appear in Innovations, Standards, and Practices of Web Services: Emerging Research Topics, Liang Jie-Zhang (Editor), IGI Global, 2011.

8. Andrew Courter, Supporting Data Consistency in Concurrent Process Execution with Assurance Points and Invariants, M.S. Thesis, Department of Computer Science, Texas Tech University, Fall, 2010.

9. Susan D. Urban, Andrew Courter, Le Gao, and Mary Shuman, “Supporting Data Consistency in Concurrent Process Execution with Assurance Points and Invariants,” under revision for submission to the Cooperative Information Systems Conference, June, 2011.

10. Janani Ramachandran, Integrating Exception Handling and Data Dependency Analysis Through Application Exception Rules, M.S. Thesis, Department of Computer Science, Texas Tech University, to be defended June, 2011.

11. Le Gao, A Context-Aware Web Service Composition Model with Decentralized Data Dependency Analysis and Rule-Based Failure Recovery Capability, Ph.D. Dissertation Proposal, Department of Computer Science, Texas Tech University, to be defended June, 2011.

12. Zev Friedman, Susan D. Urban, Le Gao, Rajiv Shrestha, “Extending the Assurance Point Approach to Process Recovery for Use with Flow Groups,” under revision for submission to the Cooperative Information Systems Conference, June 2011.

13. Jonathan Rodriguez, Le Gao, and Susan D. Urban, “Verification and Formalization of Assurance Points by Means of Colored Petri Nets,” in preparation for conference or journal submission, Summer, 2011.

14. Jamere Veldez Joshua, Analysis and Comparison of Assurance Points with Aspect-Oriented Programming to Assess Iteration and Recovery, REU Site Program Report, Texas Tech University, July, 2010.

15. Khalaf, R., Roller, D., Leymann, F., “Revisiting the Behavior of Fault and Compensation Handlers in WS-BPEL,” On the Move to Meaningful Internet Systems: OTM 2009, 286-303 (2009).

16. Coleman, J., “Examining BPEL's Compensation Construct,” Workshop on Rigorous Eng. of Fault-Tolerant Systems (2005).

---