1 Introduction
The identification and tracking of dependencies between the components of distributed systems is becoming increasingly important for integrated fault management. Applications and services rely on a variety of supporting services that might be outsourced to a service provider; moreover, emerging web-based business architectures allow the composition of web-based e-business applications at runtime: The concept of Web Services [10] consists in the dynamic advertisement, discovery and access of business functionality among multiple cooperating partners. Consequently, failures occurring in one service affect other services being offered to a customer, i.e., services have dependencies on other services. For our discussion, we call services that depend on other services dependents, while services on which other services depend are termed antecedents. It is important to note that a service often plays both roles (e.g., a name service is required by many applications and services but is dependent on the proper functioning of other ser-vices, such as operating system and network infrastructure), thus leading to a dependency hierarchy that can be modeled as a directed graph. Figure 1 depicts a simplified application dependency graph for various components of an e-business system that we have used in a testbed for designing, implementing and testing our approach. It represents a fictitious Internet storefront application that involves a Web Server for serving the static content of the site, a Web Application Server for hosting the business logic (implemented as storefront servlets), and a back-end database system that stores the dynamic content of the application (such as product descriptions, user and manufacturer data, carts, payment information etc.).