This paper addresses the issue of coordination mechanism selection in agent based service oriented computing systems. We aim to strengthen the current research on service selection and composition with a dynamic choice of the underlying coordination mechanisms. Indeed, since the environment in such systems might dynamically change, and the agents can have several protocols at their disposal, they need to select the most adequate one for service provision/ request upon the prevailing circumstances. In this paper, we present a joint protocol selection mechanism, which enables agents to decide together the protocols they will use to coordinate each other during a service provision.