Efficient management of service level agreements which govern provision of service compositions remains a big challenge in the Web services environment. This paper reports innovative research aiming at supporting autonomous establishment of a set of interrelated service level agreements for service compositions. In this paper, an agent-based framework is proposed to exploit agent interaction and negotiation capabilities for achieving agreements on service provision. Based on mis framework, this paper also discusses mechanisms for agents representing service consumers and providers to negotiate quality of service constraints for constituent services in a coordinated way, with a focus on achieving end-to-end quality of service requirements. © Springer-Verlag Berlin Heidelberg 2007.