Flexible Service Provisioning in Multi-Agent Systems

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 without human intervention. However, despite active research in service infrastructures, and in service discovery and composition mechanisms, little work has recognised that services are offered by inherently autonomous and self-interested entities. This autonomy implies that providers may choose not to honour every service request, demand remuneration for their efforts, and, in general, exhibit uncertain behaviour. This uncertainty is especially problematic for the service consumers when services are part of complex workflows, as is common in many application domains, such as bioinformatics, large-scale data analysis and processing, and commercial supply-chain management. In order to address this uncertainty, we propose a novel algorithm for provisioning services for complex workflows (i.e., for selecting suitable services for the constituent tasks of a workflow). This algorithm uses probabilistic performance information about providers to reason about service uncertainty and its impact on the overall workflow. Furthermore, our approach actively mitigates this uncertainty by employing two key techniques. First, it proactively provisions redundant services for particularly critical or failure-prone tasks (thus increasing the probability of success). Second, it recovers dynamically from service failures by re-provisioning services at run-time (without necessarily receiving explicit failure messages). Unlike existing work in this area, our algorithm employs principled decision-theoretic techniques to determine which services to provision, whether to introduce redundant services and when to re-provision failed services. In doing so, it explicitly balances the cost of provisioning with the expected value of the workflow. To show how our algorithm applies to a range of common service-oriented systems, we consider a variety of different scenarios in this thesis. More specifically, we first examine environments where the consumer lacks specific knowledge to differentiate between distinct service providers, as is common in highly dynamic and open systems. Despite this lack of detailed knowledge, we demonstrate how the consumer can use redundancy and dynamic re-provisioning to influence the outcome of a workflow and to deal with uncertainty. Then, we look into systems where the consumer has more specific knowledge about highly heterogeneous providers. While existing work has concentrated on selecting the single best provider for each workflow task, we show that a consumer can often improve its performance by provisioning multiple providers with different qualities for a single task. Finally, we discuss how our algorithm can be adapted for systems where consumers and providers reach explicit service contracts in advance. In this context, we are the first to propose a gradual provisioning approach, whereby the consumer negotiates contracts for some tasks in advance, but leaves the negotiation of others to a later time. This approach allows the consumer to better react to uncertain service outcomes and to avoid paying reservation fees that are later lost when services fail. Throughout this thesis, we compare our approach empirically to current provisioning algorithms. In doing so, we demonstrate that our approach typically achieves a significantly higher utility for the service consumer than approaches that do not reason about uncertainty, that rely on fixed levels of redundancy or service time-outs, and approaches that select single services to achieve the optimal balance of various performance characteristics. Furthermore, we show that these results hold over a large range of environments and workflow types and that our algorithm copes well even in highly uncertain environments where most services fail. As our approach relies on fast heuristics to solve a problem that is known to be intractable, it scales well to larger workflows with hundreds of tasks and thousands of providers. Finally, where it is tractable to compute an optimal solution, we show empirically that our algorithm achieves a high utility that is within 87% or more of the optimal