Abstract. Web services orchestrations and choreographies require es-tablishing Quality of Service (QoS) contracts with the user. This is achieved by performing QoS composition, based on contracts established between the orchestrator and the Web services called in the orchestration. Typical QoS parameters include maximum query throughput, response time, security, and validity of the response. Usually, QoS contracts are stated in the form of hard guarantees (e.g., response time always less than 5 msec). However, experiments and measurements from existing Web services show evidence that soft guarantees, not hard, should be stated instead (e.g., response time less than 5 msec in 95 % of the cases). In a previous work [1] we have proposed using ...