Modern applications, e.g., for pervasive computing scenarios, are increasingly reliant on systems built from multiple distributed components, which must be suitably composed to meet some specified functional and non-functional requirements. A key challenge is how to efficiently and effectively manage such complex systems. The use of self-management capabilities has been suggested as a possible way to address this challenge. To cope with the scalability and robustness issues of large distributed systems, self-management should ideally be architected in a decentralized way, where the overall system behavior emerges from local decisions and interactions. Within this context, we propose GOPRIME, a fully decentralized middleware solution for the adaptive self-assembly of distributed services. The GOPRIME goal is to build and maintain an assembly of services that, besides functional requirements, fulfils also global quality-of-service and structural requirements. The key aspect of GOPRIME is the use of a gossip protocol to achieve decentralized information dissemination and decision making. To show the validity of our approach, we present results from the experimentation of a prototype implementation of GOPRIME in a mobile health application, and an extensive set of simulation experiments that assess the effectiveness of GOPRIME in terms of scalability, robustness and convergence speed.