Abstract
Since their introduction in the early 1990s, compositionality has been reported as one of the major attractions of stochastic process algebras. The benefits that compositionality provides for model construction are readily apparent and have been demonstrated in numerous case studies. Early research on the compositionality of the languages focused on how the inherent structure could be used, in conjunction with equivalence relations, for model simplification and aggregation. In this chapter we consider how far we have been able to take advantage of compositionality when it comes to solving the Markov process underlying a Markovian process algebra model.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. Aldini, M. Bernardo, and R. Gorrieri. An algebraic model for evaluating the performance of an ATM switch with explicit rate marking. In J. Hillston and M. Silva, editors, Proc. of 7th Int. Workshop on Process Algebra and Performance Modelling (PAPM’99), pages 119–138. Prensas Universitarias de Zaragoza, September 1999.
H.H. Ammar and S.M. Rezaul Islam. Time Scale Decomposition of a Class of Generalized Stochastic Petri Net Models. IEEE Transactions on Software Engineering, 15(6):809–820, June 1989.
F. Baskett, K.M. Chandy, R.R. Muntz, and F.G. Palacios. Open, Closed and Mixed Networks of Queues with Different Classes of Customers. Journal of the ACM, 22(2):248–260, April 1975.
M. Bernardo and R. Gorrieri. A Tutorial on EMPA: A Theory of Concurrent Processes with Nondeterminism, Priorities, Probabilities and Time. Theoretical Computer Science, 202(1-2):1–54, July 1998.
M. Bhabuta, P.G. Harrison, and K. Kanani. Detecting reversibility in Markovian Process Algebra. In Performance Engineering of Computer and Telecommunications Systems, Liverpool John Moores University, September 1995. Springer-Verlag.
A. Blakemore and S. Tripathi. Automated Time Scale Decomposition of SPNs. In Proc. of 5th International Workshop on Petri Nets and Performance Models (PNPM’ 93), Toulouse, 1993.
H. Bohnenkamp and B. Haverkort. Decomposition Methods for the Solution of Stochastic Process Algebra Models: a Proposal. In E. Brinksma and A. Nymeyer, editors, Proc. of 5th Process Algebra and Performance Modelling Workshop, 1997.
H. Bohnenkamp and B. Haverkort. Semi-Numerical Solution of Stochastic Process Algebra Models. In C. Priami, editor, Proc. of 6th Process Algebra and Performance Modelling Workshop, 1998.
H. Bohnenkamp and B. Haverkort. Stochastic event structures for the decomposition of stochastic process algebra models. In J. Hillston and M. Silva, editors, Proc. of 7th Int. Workshop on Process Algebra and Performance Modelling (PAPM’99), pages 119–138. Prensas Universitarias de Zaragoza, September 1999.
R.J. Boucherie. A Characterisation of Independence for Competing Markov Chains with Applications to Stochastic Petri Nets. IEEE Transactions on Software Engineering, 20(7):536–544, July 1994.
R.J. Boucherie and M. Sereno. On the Traffic Equations of Batch Routing Queueing Networks and Stochastic Petri Nets. Technical report, European Research Consortium for Informatics and Mathematics, 1994.
P. Buchholz. Compositional Analysis of a Markovian Process Algebra. In U. Herzog and M. Rettelbach, editors, Proc. of 2nd Process Algebra and Performance Modelling Workshop, 1994.
G. Ciardo and K.S. Trivedi. A Decomposition Approach for Stochastic Petri Net Models. Performance Evaluation, 1992.
G. Clark. An Extended Weak Isomorphism for Model Simplification. In E. Brinksma and A. Nymeyer, editors, Proc. of 5th Process Algebra and Performance Modelling Workshop, 1997.
G. Clark. Stochastic Process Algebra Structure for Insensitivity. In J. Hillston and M. Silva, editors, Proc. of 7th Int. Workshop on Process Algebra and Performance Modelling (PAPM’99), pages 63–82. Prensas Universitarias de Zaragoza, September 1999.
G. Clark. Techniques for the Construction and Analysis of Algebraic Performance Models. PhD thesis, LFCS, University of Edinburgh, 2000.
G. Clark and J. Hillston. Product form solution for an insensitive stochastic process algebra structure. Performance Evaluation, 2001. To appear.
P.J. Courtois. Decomposability: Queueing and Computer System Applications. ACM Series. Academic Press, New York, 1977.
P. D’Argenio, J-P. Katoen, and E. Brinksma. General Purpose Discrete Event Simulation Using Spades. In C. Priami, editor, Proc. of 6th Process Algebra and Performance Modelling Workshop, 1998.
S. Donatelli and M. Sereno. On the Product Form Solution for Stochastic Petri Nets. In Application and Theory of Petri Nets, pages 154–172. Springer Verlag, 1992.
J-M. Fourneau, L. Kloul, and F. Valois. Performance Modelling of Hierarchical Cellular Networks using PEPA. In J. Hillston and M. Silva, editors, Proc. of 7th Int. Workshop on Process Algebra and Performance Modelling (PAPM’99), pages 139–154. Prensas Universitarias de Zaragoza, September 1999.
S. Gilmore and J. Hillston. The PEPA Workbench: A Tool to Support a Process Algebra-based Approach to Performance Modelling. In G. Haring and G. Kotsis, editors, Proceedings of the Seventh International Conference on Modelling Techniques and Tools for Computer Performance Evaluation, volume 794 of LNCS, pages 353–368. Springer-Verlag, 1994.
S. Gilmore, J. Hillston, R. Holton, and M. Rettelbach. Specifications in Stochastic Process Algebra for a Robot Control Problem. International Journal of Production Research, December 1995.
S. Gilmore, J. Hillston, and L. Recalde. Elementary structural analysis for PEPA. Technical Report ECS-LFCS-97-377, Laboratory for Foundations of Computer Science, Department of Computer Science, The University of Edinburgh, 1997.
P. Harrison and J. Hillston. Exploiting Quasi-reversible Structures in Markovian Process Algebra Models. The Computer Journal, 38(6), 1995.Special Issue: Proc. of 3rd Process Algebra and Performance Modelling Workshop.
W. Henderson, D. Lucic, and P.G. Taylor. A Net level Performance Analysis of Stochastic Petri Nets. Journal of the Australian Mathematical Society, Series B, 31:176–187, 1989.
W. Henderson and P.G. Taylor. Embedded Processes in Stochastic Petri Nets. IEEE Transactions on Software Engineering, 17(2):108–116, February 1991.
H. Hermanns and M. Rettelbach. Towards a Superset of Basic LOTOS for Performance Prediction. In M. Ribaudo, editor, Proc. of 6th Process Algebra and Performance Modelling Workshop, 1996.
H. Hermanns and M.L. Rettelbach. Syntax, Semantics, Equivalences and Axioms for MTIPP. In U. Herzog and M. Rettelbach, editors, Proc. of 2nd Process Algebra and Performance Modelling Workshop, 1994.
U. Herzog. Formal description, time and performance analysis: A framework. Technical Report 15/90, IMMD VII, Friedrich-Alexander-Universität, Erlangen-Nürnberg, Germany, September 1990.
J. Hillston. The Nature of Synchronisation. In U. Herzog and M. Rettelbach, editors, Proc. of 2nd Process Algebra and Performance Modelling Workshop, 1994.
J. Hillston. Compositional Markovian Modelling Using a Process Algebra. In W.J. Stewart, editor, Numerical Solution of Markov Chains. Kluwer, 1995.
J. Hillston. A Compositional Approach to Performance Modelling. Distinguished Dissertations in Computer Science. Cambridge University Press, 1996.
J. Hillston. A Class of PEPA Models Exhibiting Product Form Solution. Technical Report ECS-LFCS-98-382, LFCS, Dept. of Computer Science, University of Edinburgh, February 1998.
J. Hillston, H. Hermanns, U. Herzog, V. Mertsiotakis, and M. Rettelbach. Integrating Qualitative and Quantitative Modelling with Stochastic Process Algebras. Technical report, IMMD VII, Universität Erlangen-Nürnberg, May 1994.
J. Hillston and L. Kloul. An Efficient Kronecker Representation for PEPA Models. Submitted for publication, 2000.
J. Hillston and V. Mertsiotakis. A Simple Time Scale Decomposition Technique for Stochastic Process Algebras. The Computer Journal, 38(6), 1995. Special Issue: Proc. of 3rd Process Algebra and Performance Modelling Workshop.
J. Hillston and N. Thomas. A Syntactical Analysis of Reversible PEPA Models. In Proc. of 6th Process Algebra and Performance Modelling Workshop, Nice, France, September 1998. University of Verona.
J. Hillston and N. Thomas. Product Form Solution for a class of PEPA Models. Performance Evaluation, 35:171–192, 1999.
J. Hillston and J. Tomasik. Amalgamation of transition sequences in the PEPA formalism. In Proc. of ICALP Workshops 2000 (PAPM). Carleton Scientific Press, 2000.
D.R.W. Holton. A PEPA Specification of an Industrial Production Cell. The Computer Journal, 38(6), 1995. Special Issue: Proc. of 3rd Process Algebra and Performance Modelling Workshop.
J.R. Jackson. Jobshop-like Queueing Systems. Management Science, 10: 131–142, 1963.
H. Jungnitz. Approximation Methods for Stochastic Petri Nets. PhD thesis, Rensselaer Polytechnic Institute, May 1992.
F. Kelly. Reversibility and Stochastic Processes. Wiley, 1979.
A.A. Lazar and T.G. Robertazzi. Markovian Petri Net Protocols with Product Form Solution. Performance Evaluation, 12(1):67–77, January 1991.
V. Mertsiotakis. Time Scale Decomposition of Stochastic Process Algebra Models. In E. Brinksma and A. Nymeyer, editors, Proc. of 5th Process Algebra and Performance Modelling Workshop, 1997.
V. Mertsiotakis. Approximate Analysis Methods for Stochastic Process Algebras. PhD thesis, Universität Erlangen-Nürnberg, Martensstraße 3, 91058 Erlangen, September 1998.
V. Mertsiotakis and M. Silva. A Throughput Approximation Algorithm for Decision Free Processes. In M. Ribaudo, editor, Proc. of 6th Process Algebra and Performance Modelling Workshop, 1996.
V. Mertsiotakis and M. Silva. A Throughput Approximation Algorithm for Decision Free Processes. In M. Ribaudo, editor, Proc. of 7th International Workshop on Petri Nets and Performance Models, 1996.
I. Mitrani and N. Thomas. Routing Among Different Nodes Where Servers Break Down Without Losing Jobs. In F. Baccelli, A. Jean-Marie, and I. Mitrani, editors, Quantitative Methods in Parallel Systems, pages 248–261. Springer, 1995.
I. Mitrani and P.E. Wright. Routing in the Presence of Breakdowns. Performance Evaluation, 20:151–164, 1994.
M.K. Molloy. Performance Analysis using Stochastic Petri Nets. IEEE Transactions on Computers, 31(9):913–917, September 1982.
B. Plateau. On the Stochastic Structure of Parallelism and Synchronisation Models for Distributed Algorithms. In Proc. ACM Sigmetrics Conference on Measurement and Modelling of Computer Systems, 1985.
B. Plateau, J.M. Fourneau, and K.H. Lee. PEPS: A Package for Solving Complex Markov Models of Parallel Systems. In Proc. of the 4th International Conference on Modelling Techniques and Tools for Computer Performance Evaluation, 1988.
M.L. Rettelbach and M. Siegle. Compositional Minimal Semantics for the Stochastic Process Algebra TIPP. In U. Herzog and M. Rettelbach, editors, Proc. of 2nd Process Algebra and Performance Modelling Workshop, 1994.
M. Sereno. Towards a Product Form Solution of Stochastic Process Algebras. The Computer Journal, 38(6), 1995. Special Issue: Proc. of 3rd Process Algebra and Performance Modelling Workshop.
M. Sereno. Performance Models for Discrete Event Systems with Synchronisations, volume II, chapter Product form and Petri nets, pages 637–660. Kronos, 1998.
W.J. Stewart, K. Arif, and B. Plateau. The numerical solution of Stochastic Automata Networks. European Journal of Operation Research, 86(3):503–525, 1995.
N. Thomas and J. Bradley. Approximating variance in non-product form decomposed models. In Proc. of ICALP Workshops 2000 (PAPM), pages 607–619. Carleton Scientific Press, 2000.
N. Thomas and S. Gilmore. Applying Quasi-Separability to Markovian Process Algebra. In Proc. of 6th Process Algebra and Performance Modelling Workshop, Nice, France, September 1998. University of Verona.
J. Tomasik and J. Hillston. Transforming PEPA Models to Obtain Product Form Bounds. Technical report, Division of Informatics, University of Edinburgh, 2000.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Hillston, J. (2001). Exploiting Structure in Solution: Decomposing Compositional Models. In: Brinksma, E., Hermanns, H., Katoen, JP. (eds) Lectures on Formal Methods and PerformanceAnalysis. EEF School 2000. Lecture Notes in Computer Science, vol 2090. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44667-2_8
Download citation
DOI: https://doi.org/10.1007/3-540-44667-2_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42479-6
Online ISBN: 978-3-540-44667-5
eBook Packages: Springer Book Archive