Distributed Resource Allocation: Formalization, Complexity Results and Mappings to Distributed CSPs £

In distributed resource allocation a set of agents must assign their resources to a set of dynamic tasks. This problem arises in many real-world domains like the one described in this paper: distributed sensor networks. Despite the variety of approaches proposed for distributed resource allocation, a systematic formalization of the problem and a general solution strategy are missing. Such formalizations are necessary to understand the complexity of different types of problems and to develop solution strategies that translate across domains. This paper takes a step towards this goal by proposing a formalization of resource allocation that represents both dynamic and distributed aspects of the problem and allows tractable subclasses to be identified. In addition, this paper defines the notion of Dynamic Distributed Constraint Satisfaction Problem (DyDisCSP) and proposes two generalized mappings to translate distributed resource allocation problems to DyDisCSP. Each mapping is proven to correctly perform resource allocation problems of specific difficulty. Our theoretical results are verified in practice by an implementation on a real-world distributed sensor network. £ This paper is an extension of a earlier conference paper [12]. Detailed exposition, experimental results and detailed proofs are included here. 1