The trend towards cloud and utility computing infrastructures raises challenges not only for application development, but also for management: diverse resources, changing resource availability, and differing application requirements create a complex optimization problem. Most existing cloud applications are managed externally, and this separation can lead to increased response time to failures, and slower or less appropriate adaptation to resource availability and pricing changes. In this paper, we explore a different approach more akin to P2P systems: we closely couple a decentralized management runtime ("Rhizoma") with the application itself. The application expresses its resource requirements to the runtime as a constrained optimization problem. Rhizoma then fuses multiple real-time sources of resource availability data, from which it decides to acquire or release resources (such as virtual machines), redeploying the system to continually maximize its utility. Using PlanetLab as a challenging "proving ground" for cloud-based services, we present results showing Rhizoma's performance, overhead, and efficiency versus existing approaches, as well the system's ability to react to unexpected large-scale changes in resource availability.