We present SHReQ, a formal framework for specifying systems that handle abstract high-level QoS requirements which are becoming more and more important for service oriented computing. SHReQ combines Synchronised Hyperedge Replacement (SHR) with constraint-semirings. SHR is a (hyper)graph rewriting mechanism for modelling evolution of systems. The novelty of the approach relies on the synchronisation mechanism which is based on constraint-semirings, algebraic structures that provide both the mathematics for multi-criteria QoS and the synchronisation policies underlying the SHR mechanism.