A Probabilistic Strategy Language for Probabilistic Rewrite Theories and its Application to Cloud Computing

Abstract. Several formal models combine probabilistic and nondeterministic features. To allow their probabilistic simulation and statistical model checking by means of pseudo-random number sampling, all sources of nondeterminism must first be quanti-fied. However, current tools offer limited flexibility for the user to define how the non-determinism should be quantified. In this report we propose an expressive probabilistic strategy language that allows the user to define complex strategies for quantifying the nondeterminism in probabilistic rewrite theories. These strategies may depend on the current system state, and their associated weight expressions can be given by any com-putable function defined equationally in Maude. We have implemented PSMaude, a tool that extends Maude with a probabilistic simulator and a statistical model checker for our language. We illustrate the convenience of being able to define different prob-abilistic strategies by a cloud computing example, where a (non-probabilistic) rewrite theory defines the capabilities of the cloud computing infrastructure, and where dif-ferent load balancing policies are specified by different probabilistic strategies. Our language also enables a Maude-based safety/QoS modeling and analysis methodology in which key safety properties can be verified for a basic “uncluttered ” non-probabilistic model, and where QoS properties for different probabilistic strategies can be analyzed by probabilistic simulation and statistical model checking.