With the continuous growth in the number of mobile networked devices, and their rapidly improving compute capabilities, it has become possible to harness them as an extended cloud. This presents a clear opportunity to place latency-sensitive applications and services at the edge. As applications are increasingly based on the microservices and Network Function Virtualization (NFV) architectures, their overall performance will depend on the location of their constituent microservices relative to one-another. An extended cloud comprising mobile devices therefore results in a dynamic network, making it difficult for traditional orchestration systems in distant clouds to perform timely management and replacement of microservices to ensure the overall application or service is performant. We propose to address this challenge by decentralizing the service discovery and allocation logic, placing it in client microservices. This paper presents a P2P-based design and prototype system that empowers clients to discover desired services based on pre-defined QoS requirements. If none are found, clients identify compute nodes meeting the requirements to request a new service allocation.