Service Level Agreements (SLA) may be used to establish agreements on the quality of a service between a service provider and a service consumer. This report gives an overview on current work done on negotiation and re-negotiation of SLAs within the CoreGRID Institute on Resource Management and Scheduling and in the Grid Resource Allocation Agreement Protocol Working Group (GRAAP-WG) of the Open Grid Forum (OGF). An introduction is given on the proposed OGF recommendation WS-Agreement and its state, followed by a presentation of use-cases for negotiation stemming from from implementations of WS-Agreement. We then describe the approaches currently under discussion in the GRAAP-WG to be consolidated to a negotiation protocol for Service Level Agreements using WS-Agreement. Since the working group of the OGF has not yet consolidated the approaches presented there is not yet a single proposal for a negotiation protocol. However, during the last meeting of the working group the members identified the three approaches that will now be used as a base to specify the protocol for negotiation and re-negotiation of SLAs. Furthermore, the report discusses built-in functionality ofWS-Agreement and additional requirements for the monitoring of SLAs.