Many SOA applications are now migrating to cloud servers, due to cloud's low cost provision, elasticity for growth, and better availability. Although cloud service providers have implemented reliable management system for their infrastructure, hybrid cloud users often lack easy monitoring and diagnosis facilities to discover the root cause of end-to-end QoS violations. However, the cause must be identified before the auto scaling of provisioned resources within cloud servers can be conducted. In this paper, we investigate the locality property of distributed services, and propose the Markov network based monitoring and diagnosis support in the Llama Cloud middleware. We present the diagnosis problem definition, diagnosis model, and the algorithm for runtime diagnosis. Our experiment results show that the proposed Markov network based method outperforms the Bayesian network based diagnosis method under different workloads and service locality patterns.