Service-oriented computing has emerged as a new software development paradigm that enables implementation of web accessible software systems composed of distributed services interacting with each other via exchanging messages. Modeling and analysis of interactions among services is a crucial problem in this paradigm. Many formal methods including process algebras have been used to address functional modeling and verification of web service composition; however they often ignore the modeling and analysis of the cost of the service composition. In this paper, we propose priced probabilistic process algebra (PPPA) by extending existing probabilistic process algebra with cost modeling and analysis capability. We show how to use PPPA to model service composition and how to control the cost of service composition using Markov decision process with target function of optimal cost.
