This paper presents a specification for a domain-independent, symmetrical, two-party negotiation protocol to reach binding agreements between services based on the principles of contract law. The protocol is necessary as existing specifications, such as WS-agreement, lack the capability to form negotiated agreements and lack sufficient rigor in their design. This leads to ambiguities in their interpretations and, therefore, possible interoperability problems between different implementations. The negotiation protocol fits into the modular, high-level framework also presented here, that can be completed using a variety of existing contract monitoring and management procedures