The automatic invocation of a web service by an agent is a complex task which is currently being addressed by semantic markup techniques. However, it is dif cult to de ne the computational aspects of a web service in this approach. In this paper we propose a protocol-based formalism which appears better suited to a representation of these issues. We de ne the syntax and semantics of a protocol language which express precisely how the interaction with a service should be performed, and how the service should be invoked. We also sketch an architecture for the execution of our protocols.