Pervasive Computing envisions seamless support for user tasks through cooperating devices that are present in an environment. Fluctuating availability of devices, induced by mobility and failures, requires mechanisms and algorithms that allow applications to adapt to their ever-changing execution environments without user intervention. To ease the development of adaptive applications, Becker et al. [3] have proposed the peer-based component system PCOM. This system provides fundamental mechanisms to support the automated composition of applications at runtime. In this article, we discuss the requirements on algorithms that enable automatic configuration of pervasive applications. Furthermore, we show how finding a configuration can be interpreted as Distributed Constraint Satisfaction Problem. Based on this, we present an algorithm that is capable of finding an application configuration in the presence of strictly limited resources. To show the feasibility of this algorithm, we present an evaluation based on simulations and real-world measurements and we compare the results with a simple greedy approximation.