The Network Function Virtualization paradigm is attracting the interest of service providers, that may greatly benefit from its flexibility and scalability properties. However, the diversity of possible orchestrated services, rises the necessity of adopting specific orchestration strategies for each service request that are unknown a priori. This paper presents Senate, a distributed architecture that enables precise orchestration of heterogeneous services over a common edge infrastructure. To assign shared resources to service orchestrators, Senate uses the Distributed Orchestration Resource Assignment (DORA), an approximation algorithm that we designed to guarantee both a bound on convergence time and an optimal (1-1/e)-approximation with respect to the Pareto optimal resource assignment. We evaluate advantages of service orchestration with Senate and performance of DORA through a prototype implementation.