Decentralised agent-based resource allocation in open and dynamic environments

The on-demand provisioning of distributed applications and services in open, large-scale and distributed systems such as the Internet is a complex undertaking. It requires an adaptive resource allocation scheme that can effectively and efficiently allocate resources on a large scale and across different administrative domains. Two of the main challenges for resource allocation in such environments are the lack of full control over the resources and the uncertainty and the limitation in the type and the amount of information about resource providers and resource consumers. These challenges restrict the use of resource allocation schemes that require central control or assume the availability of full information and direct coordination between providers and consumers. In this thesis, we study distributed resource allocation problems in open and dynamic environments consisting of independent resource providers and resource consumers. In such environments, consumers have to select a provider with suffcient resources for the task execution. Shared resources that serve the computational needs of the consumers are offered by the providers. The interest of each provider is an optimal utilisation of their resources, or equivalently to minimise the amount of idle resources. On the other hand, the consumers pursue the execution of their tasks at a provider where the demand of resources does not exceed the capacity in order to get a high quality of service. The problem in this setting is that providers and consumers operate independently and no central entity exists that can effectively mediate the allocation of resources. Resource consumers are not directly aware of each other, thus they have no means to communicate and directly coordinate their resource allocation decisions with each other. They must learn to coordinate their own resource allocation decisions with others. This problem of the on-demand allocation of resources in open environments where the control over resources is decentralised among the participants is not well investigated in the current research literature. Existing resource allocation schemes with decentralised control are typically studied in a static context, where a fixed number of consumers with static resource demands try to access a fixed amount of resources provided by a single provider. This thesis addresses the above problems and proposes a multi-agent framework for decentralised and dynamic resource allocation. Resource allocation decisions are made by autonomous adaptive agents in the presence of changing demand for resources as well as the availability and capacity of shared resources. This innovative resource allocation mechanism is based on inductive reasoning techniques. It allows agents to reason about the expected amount of available resources based on past observations. This knowledge enables the agents to individually request for the allocation of resources without direct coordination between them to pursue the overall aim of collectively optimising the utilisation of the shared resources. The resource allocation is created by the effective competition of agents for the available resources and is a purely emergent effect. The second contribution of this thesis is a study of the impact of different information models with regard to the level of coordination between the agents. More speciffcally, we consider the Publish-Subscribe and the Data-Pull information models. The results show that agents can adapt their resource allocation decisions in the face of gradual changes in a dynamic environment. The resource utilisation of a provider is closer to the optimal utilisation when consumers have only limited and heterogeneous information that they individually collect using the Data-Pull model as opposed to the level of coordination that can be achieved when the providers publish their resource utilisation information globally. At the same time, the resource allocation success rate for the agents is significantly higher with limited information because agents are less reactive to fluctuations in the environment. The applicability of the developed algorithm in open and dynamic environments is demonstrated in a range of different scenarios. More specifically, we first examine environments where consumers use the resources of a single provider in different settings with static and dynamic capacities. Then, this thesis investigates different resource allocation strategies in environments with multiple providers and tasks that require multiple types of resources simultaneously. The empirical evaluation shows that the utilisation of resources is closer to optimal when the consumers have less information available and they only explore alternative resource allocations when the recent allocations were not satisfying.