Sebastian Stein

ss2@ecs.soton.ac.uk

• Home
• Research Overview
• Publications
• Curriculum Vitae
• Links

In April 2008, I completed my PhD thesis on Flexible Service Provisioning in Multi-Agent Systems [PhD 2008]. In collaboration with my supervisors Nick Jennings and Terry Payne, I combined techniques from the fields of artificial intelligence, multi-agent systems and decision theory to design efficient and effective algorithms for provisioning (or selecting) uncertain and heterogeneous services that are required for complex workflows. In particular, our approach deals with service uncertainty by flexibly provisioning multiple services redundantly for critical tasks, by re-provisioning failed services at run-time and by reserving services in advance where this is beneficial.

The following is an extended abstract of my thesis work. It is divided into five sections:

1. "Background" introduces the challenges that we have addressed.
2. "Contributions" lists the main contributions of my PhD thesis.
3. "Illustrative Example" provides a simple example of our techniques.
4. "Applications" describes how our work has been applied.
5. "References" lists the references cited in this summary.

Background

Service-oriented computing is an increasingly popular approach for providing applications, computational resources and business services over highly distributed and open systems (such as the Web, computational Grids and peer-to-peer systems). In this approach, service providers advertise their offerings by means of standardised computer-readable descriptions, which can then be used by software applications to discover and consume appropriate services in a fully automatic manner. This allows consumer applications to outsource key pieces of functionality and flexibly choose the best service providers at any given time. For example, the application of a computational scientist can seamlessly access remote data-processing and simulation services on the Grid without the need for an expensive local mainframe. Similarly, a supply-chain application can automatically discover and order from the cheapest supplier of stocks when inventory levels run low.

However, despite active research in service infrastructures, and in service discovery and composition mechanisms, little existing work has dealt effectively with some of the key features of large-scale service-oriented systems:

• Uncertainty: Services typically take uncertain amounts of time to complete and may even fail completely (possibly without providing a failure message). In part, this uncertainty may be due to network delays, competition for resources and unforeseen hardware failures. Furthermore, services are generally offered by autonomous and self-interested entities, or agents. These agents may choose to delay certain service requests or even defect when this increases their private utility.
• Heterogeneity: Often, there are many agents that offer functionally equivalent services at varying levels of quality. Hence, the consumer must make a decision between, e.g., selecting a cheap, but unreliable service and a more expensive, highly reliable one.
• Dynamism: The service landscape in an open system can change quickly as new providers enter or leave the system. This means that a consumer application must monitor availability and needs to respond promptly when critical services disappear. Similarly, such dynamism can present an opportunity as better providers may become available over time.

These issues are particularly critical when the consumer requires services to complete in a timely manner, when providers demand financial remuneration and when services are executed as part of larger workflows, where multiple services are composed to achieve some high-level goal. Such circumstances are common in many application scenarios of service-oriented technologies, from computational Grids to commercial business processes.

Contributions

To address the issues described above, we have developed a number of algorithms that a service consumer can use to effectively and efficiently execute large service workflows in dynamic and uncertain environments.

More specifically, we have concentrated on the process of service provisioning (see Figure 1). Provisioning, i.e., the selection of particular service instances for specific tasks of a workflow, has received comparatively little attention in the research literature so far, but we believe that it is vital for controlling and mitigating nondeterministic service performance. Provisioning providers in an appropriate manner allows a service consumer to differentiate between providers that offer a service at differing levels of quality or reliability and to invest extra resources in tasks that are particularly critical. Furthermore, re-provisioning providers on-the-fly enables the service consumer to respond quickly to failures and recover partially complete workflows without starting from scratch.

Figure 1: Workflow Lifecycle

To this end, we have developed a novel model for a distributed system and for simple workflows, which can be used in a wide range of application areas — from Grid to Web services and peer-to-peer systems. In the context of this model, we described a number of provisioning strategies, and, in doing so, advanced the state of the art in service provisioning as follows:

• Automatic Service Redundancy: We devised the first algorithm that provisions multiple services redundantly for particularly critical workflow tasks in an automatic and principled manner, based on service performance information and the predicted benefit of doing so. Using such redundancy allows the consumer agent to decrease the probability of task failures and improve task execution times [ECAI 2006, TOIT 2009].

• Flexible Re-Provisioning: We explicitly considered the problem of crash failures in service workflows, where services appear to work on an assigned task, but in fact never return a result. While existing work assumes either timely error messages or manually fixed time-out values, we developed, for the first time, a method for flexibly determining service time-outs, i.e., how long to wait for a service before re-assigning the task to a different provider [ECAI 2006, TOIT 2009].
• Limited and Full Information Settings: In developing the above two contributions, we also showed how our techniques can be applied in environments where different amounts of performance information is available about service providers. When this is extremely limited, the agent can use task-specific information to make fast decisions within a restricted decision space. In this case, we were the first to describe how the consumer can address uncertainty proactively without specific information to distinguish between providers [ECAI 2006, TOIT 2009]. On the other hand, when the consumer has detailed knowledge about each provider, it can harness this to not only select the most appropriate one, but also to rely on multiple heterogeneous providers for a single task where this is beneficial [AAMAS 2007, AAAI 2007].
• Gradual Advance Provisioning: When services are provisioned using advance agreements, we showed that the service consumer can benefit significantly by gradually provisioning its workflow during execution, rather than provisioning all tasks at once (as is done by existing work). To enable such behaviour, we developed a novel strategy that predicts the benefit of advance provisioning and balances this with the risk of losing agreed services due to task conflicts [AAMAS 2008].
• Highly Adaptive Provisioning: We proposed a highly adaptive provisioning strategy that continuously incorporates new information about service performance into its decision-making procedure at run-time, and changes its behaviour accordingly. In this context, it is the first strategy that uses such information not only to react to outright failures, but also to make additional provisions when the workflow begins to fall behind schedule, to reduce its investments when services perform better than expected, to exploit better offers as soon as they become available, and to realise when to completely abandon an infeasible workflow [AAMAS 2008].
• Significant Improvements over the State of the Art: To quantify the benefits of our work, we showed empirically that our algorithms consistently outperform existing provisioning approaches. More specifically, our approach achieves an average improvement in utility of 50-700% over the state of the art (depending on the types of systems we consider), which can rise up to 3500% for specific settings. Moreover, we demonstrate that in particularly uncertain environments, our algorithms successfully complete 80% of workflows within the given deadline, while existing approaches complete none [ECAI 2006, AAAI 2007, AAMAS 2008, PhD 2008, TOIT 2009, PTRSA 2009].
• Robustness to Inaccurate Service Information: As accurate service performance information may not always be available, we have carried out a sensitivity analysis of our work in the presence of noisy data. This has shown that our approach is highly robust to errors of around 10%, and usually experiences only a marginal degradation in performance when the provided information is within 20-30% of the true value [SOCASE 2007].
• Efficiency for Real-World Applications: We investigated the theoretical properties of the underlying optimisation problem and proved that the service provisioning problem is NP-hard (this holds even when service execution times are deterministic) [AAAI 2007]. Hence, to deal with real-world workflow applications, our algorithms use approximations which run in polynomial time and can successfully deal with thousands of interdependent tasks and tens of thousands of service providers [PhD 2008]. Furthermore, we show empirically that the performance of our algorithms is within 88-98% of the optimal [PhD 2008, TOIT 2009].

Illustrative Example

In the following, we briefly discuss a simple example of how we use redundancy, flexible re-provisioning and knowledge of heterogeneous service providers to address uncertainty.

Consider a single workflow task, which can be completed by a number of service providers. As shown in Figure 2, let us assume there are 17 such providers and each of them belongs to one of two classes: either cheap, unreliable and slow, or expensive, reliable and fast (this is for illustration only — in reality, there may be many more types of providers).

Figure 2: Available Service Providers

Now, a naïve approach may select only a single provider for the task. For example, if the task is of a high value and the consumer wants to maximise its probability of success, it may select a provider from the expensive population, as show below:

Figure 3: Single Reliable Provider

However, we could do better by introducing redundancy and re-provisioning. Figure 4 shows the result of invoking four of the cheaper providers in parallel, then waiting for an hour until re-assigning the task to four more providers if the task has not been successful (and repeating this another hour later). Surprisingly, using the far less reliable providers now results in a higher success probability, at a significantly lower cost. However, the duration and variance both rise in this case, due to the additional waiting time that is introduced.

Figure 4: Multiple Cheap Providers

Finally, it is possible for the consumer to invoke different types of services providers over time. Figure 5 shows a schedule where the consumer first invokes a number of cheap providers in parallel, followed some time later by more expensive ones. Here, the consumer may be lucky and have the task completed by one of the initial cheap providers. However, if this is not the case, it falls back onto the more reliable providers to ensure the task is completed within a reasonable time. In summary, this decision now results in almost guaranteed success and an expected cost and duration that are both lower than those of a single reliable provider.

Figure 5: Redundant Heterogeneous Providers

The example highlights how redundancy and re-provisioning can be used to proactively deal with uncertainty. A key benefit of our approach is that the schedules outlined above are found automatically, based on the performance of service providers, the structure of the workflow, time constraints and the overall workflow value. For example, this means that our algorithm might pick the cheaper allocation in Figure 4 when the user has a lower value and less urgent deadline for the workflow. However, when time is more critical and the workflow is more important, then the more expensive, reliable and faster allocation in Figure 5 might be chosen.

Applications

In addition to the above contributions, we have liaised with computational scientists to show that our algorithm can be used to ensure a long-running Grid workflow from the bioinformatics domain is completed within a certain deadline, even when services are highly unreliable (see Figure 6) [AHM 2008, TOIT 2009, PTRSA 2009].

Figure 6: Bioinformatics Workflow

Furthermore, we have developed a GUI to visualise both the provisioning decisions and workflow progress during execution (see Figure 7) [PTRSA 2009].

Figure 7: Service Provisioning GUI

References

Copyright © 2008 Sebastian Stein. All right reserved.