An Extension to Pi-Calculus for Performance Evaluation

ABSTRACT

Pi-Calculus is a formal method for describing and analyzing the behavior of large distributed and concurrent systems. Pi-calculus offers a conceptual framework for describing and analyzing the concurrent systems whose configuration may change during the computation. With all the advantages that pi-calculus offers, it does not provide any methods for performance evaluation of the systems described by it; nevertheless performance is a crucial factor that needs to be considered in designing of a multi-process system. Currently, the available tools for pi-calculus are high level language tools that provide facilities for describing and analyzing systems but there is no practical tool on hand for pi-calculus based performance evaluation. In this paper, the performance evaluation is incorporated with pi-calculus by adding performance primitives and associating performance parameters with each action that takes place internally in a system. By using such parameters, the designers can benchmark multi-process systems and compare the performance of different architectures against one another.

Pi-Calculus is a formal method for describing and analyzing the behavior of large distributed and concurrent systems. Pi-calculus offers a conceptual framework for describing and analyzing the concurrent systems whose configuration may change during the computation. With all the advantages that pi-calculus offers, it does not provide any methods for performance evaluation of the systems described by it; nevertheless performance is a crucial factor that needs to be considered in designing of a multi-process system. Currently, the available tools for pi-calculus are high level language tools that provide facilities for describing and analyzing systems but there is no practical tool on hand for pi-calculus based performance evaluation. In this paper, the performance evaluation is incorporated with pi-calculus by adding performance primitives and associating performance parameters with each action that takes place internally in a system. By using such parameters, the designers can benchmark multi-process systems and compare the performance of different architectures against one another.

Cite this paper

nullS. Rahimi, E. Khorasani, Y. Lee and B. Gupta, "An Extension to Pi-Calculus for Performance Evaluation,"*Journal of Software Engineering and Applications*, Vol. 4 No. 1, 2011, pp. 9-17. doi: 10.4236/jsea.2011.41002.

nullS. Rahimi, E. Khorasani, Y. Lee and B. Gupta, "An Extension to Pi-Calculus for Performance Evaluation,"

References

[1] R. Milner, J. Parrow and D. Walker, “A Calculus of Mobile Processes—Part I and II,” LFCS Report 89-85, University of Edinburgh, Edinburgh, 1989.

[2] R. Milner, “Communicating and Mobile Systems: The π-Calculus,” Cambridge University Press, Cambridge, 1999.

[3] R. Milner, “The Polyadic Pi-Calculus: A Tutorial,” Technical Report ECSLFCS -91-180, Computer Science Department, University of Edinburgh, Edinburgh, 1991.

[4] D. Sangiorgi, “Theπ-Calculus: A Theory of Mobile Processes,” Cambridge University Press, Cambridge, 2001.

[5] D. Sangiorgi: “Expressing Mobility in Process Algebras: First-Order and Higher-Order Paradigms,” Ph.D. Thesis, University of Edinburgh, Edinburgh, 1993.

[6] C. Priami, “Stochasticπ-Calculus,” Computer Journal, Vol. 38, 1995, pp. 578-589. doi:10.1093/comjnl/38.7.578

[7] N. G tz, U. Herzog and M. Rettelbach, “TIPP-A Language for Timed Processes and Performance Evaluation,” Technical Report 4/92. IMMD VII, University of Erlangen-Nurnberg, Erlangen, 1992.

[8] J. Hillston, “A Compositional Approach to Performance Modelling,” Ph.D. Thesis, University of Edinburgh, Edinburgh, 1994.

[9] M. Bernardo, L. Donatiello and R. Gorrieri, “MPA: A Stochastic Process Algebra,” Technial Report UBLCS- 94-10, University of Bologna, Bologna, 1994.

[10] P. Buchholz, “On a Markovian Process Algebra,” Techinal Report Informatik IV, University of Dortmund, Dort- mund 1994.

[11] L. de Alfaro, “Stochastic Transition Systems,” Proceedings of Ninth International Conference on Concurrency Theory (CONCUR’98), Vol. 1477, 1998, pp. 423-438. doi:10.1007/BFb0055639

[12] J. Markovski and E. P. de Vink, “Performance Evaluation of Distributed Systems Based on a Discrete Real- and Stochastic-Time Process Algebra,” Fundamenta Informaticae, Vol. 95, No. 1, October 2009, pp. 157-186.

[13] A. Clark, S. Gilmore, J. Hillston and M. Tribastone, “Stochastic Process Algebras,” SFM’07 Proceedings of the 7th International Conference on Formal Methods for Performance Evaluation, 2007, pp 132-179.

[14] P. R. D’Argenio and J. Katoen, “A Theory of Stochastic Systems. Part II: Process Algebra,” Information and Computation, Vol. 203, No. 1, November 2005, pp. 39-74. doi:10.1016/j.ic.2005.07.002

[15] S. M. Ross, “Stochastic Processes,” 2nd Edition, Wiley, New York, 1996.

[16] G. Bolch, S. Greiner, H. De Meer and K. S. Trivedi, “Queuing Networks and Markov Chains: Modelling and Performance Evaluation with Computer Science Applications,” Wiley, New York, 1998

[17] C. Nottegar, C. Priami and P. Degano, “Performance Evaluation of Mobile Processes Via Abstract Machines,” IEEE Transactions on Software Engineering, Vol. 27, No. 10, 2001, pp. 867-889. doi:10.1109/32.962559

[18] F. Logozzo, “Pi-Calculus as a Rapid Prototype Language For Performance Evaluation,” Proceedings of the ICLP 2001 Workshop on Specification, Analysis and Validation for Emerging Technologies in Computational Logic (SAVE 2001), 2001.

[19] S. Rahimi, M. Cobb, D. Ali, M. Paprzycki and F. Petry, “A Knowledge-Based Multi-Agent System for Geospatial Data Conflation,” Journal of Geographic Information and Decision Analysis, Vol. 6, No. 2, 2002, pp. 67-81.

[20] A. Grama, G. Karypis, V. Kumar and A Gupta, “An Introduction to Parallel Computing: Design and Analysis of Algorithms,” 2nd Edition, Addison Wesley, Reading, 2003

[21] W. R. Cockayne and M. Zyda, “Mobile Agents”, Manning Publications Company, Greenwich, 1998.

[22] H. Samet, “The Design and Analysis of Spatial Data Structures,” Addison-Wesley, Reading, 1989.

[23] S. Rahimi, “Using Api-Calculus for Formal Modeling of SDIAgent: A Multi-Agent Distributed Geospatial Data Integration,” Journal of Geographic Information and Decision Analysis, Vol. 7, No. 2, 2003, pp. 132-149.

[24] S. Rahimi, J. Bjursell, M. Paprzycki, M. Cobb and D. Ali, “Performance Evaluation of SDIAGENT, a Multi-Agent System for Distributed Fuzzy Geospatial Data Conflation,” Information Sciences, Vol. 176, No. 9, 2006. doi:10.1016/ j.ins.2005.07.009

[25] S. Derisavi, P. Kemper and W. H. Sanders, “Symbolic State-Space Exploration and Numerical Analysis of State-Sharing Composed Models,” Linear Algebra and Its Applications, Vol. 386, July 2004, pp. 137-166. doi:10. 1016/j.laa.2004.01.006

[26] S. Derisavi, H. Hermanns and W. H. Sanders, “Optimal State-Space Lumping in Markov Chains,” Information Processing Letters, Vol. 87, No. 6, 2003, pp. 309-315. doi:10.1016/S0020-0190(03)00343-0

[27] P. Buchholz, “Efficient Computation of Equivalent and Reduced Representations for Stochastic Automata,” International Journal of Computer Systems Science & Engineering, Vol. 15, No. 2, March 2000, pp. 93-103.

[1] R. Milner, J. Parrow and D. Walker, “A Calculus of Mobile Processes—Part I and II,” LFCS Report 89-85, University of Edinburgh, Edinburgh, 1989.

[2] R. Milner, “Communicating and Mobile Systems: The π-Calculus,” Cambridge University Press, Cambridge, 1999.

[3] R. Milner, “The Polyadic Pi-Calculus: A Tutorial,” Technical Report ECSLFCS -91-180, Computer Science Department, University of Edinburgh, Edinburgh, 1991.

[4] D. Sangiorgi, “Theπ-Calculus: A Theory of Mobile Processes,” Cambridge University Press, Cambridge, 2001.

[5] D. Sangiorgi: “Expressing Mobility in Process Algebras: First-Order and Higher-Order Paradigms,” Ph.D. Thesis, University of Edinburgh, Edinburgh, 1993.

[6] C. Priami, “Stochasticπ-Calculus,” Computer Journal, Vol. 38, 1995, pp. 578-589. doi:10.1093/comjnl/38.7.578

[7] N. G tz, U. Herzog and M. Rettelbach, “TIPP-A Language for Timed Processes and Performance Evaluation,” Technical Report 4/92. IMMD VII, University of Erlangen-Nurnberg, Erlangen, 1992.

[8] J. Hillston, “A Compositional Approach to Performance Modelling,” Ph.D. Thesis, University of Edinburgh, Edinburgh, 1994.

[9] M. Bernardo, L. Donatiello and R. Gorrieri, “MPA: A Stochastic Process Algebra,” Technial Report UBLCS- 94-10, University of Bologna, Bologna, 1994.

[10] P. Buchholz, “On a Markovian Process Algebra,” Techinal Report Informatik IV, University of Dortmund, Dort- mund 1994.

[11] L. de Alfaro, “Stochastic Transition Systems,” Proceedings of Ninth International Conference on Concurrency Theory (CONCUR’98), Vol. 1477, 1998, pp. 423-438. doi:10.1007/BFb0055639

[12] J. Markovski and E. P. de Vink, “Performance Evaluation of Distributed Systems Based on a Discrete Real- and Stochastic-Time Process Algebra,” Fundamenta Informaticae, Vol. 95, No. 1, October 2009, pp. 157-186.

[13] A. Clark, S. Gilmore, J. Hillston and M. Tribastone, “Stochastic Process Algebras,” SFM’07 Proceedings of the 7th International Conference on Formal Methods for Performance Evaluation, 2007, pp 132-179.

[14] P. R. D’Argenio and J. Katoen, “A Theory of Stochastic Systems. Part II: Process Algebra,” Information and Computation, Vol. 203, No. 1, November 2005, pp. 39-74. doi:10.1016/j.ic.2005.07.002

[15] S. M. Ross, “Stochastic Processes,” 2nd Edition, Wiley, New York, 1996.

[16] G. Bolch, S. Greiner, H. De Meer and K. S. Trivedi, “Queuing Networks and Markov Chains: Modelling and Performance Evaluation with Computer Science Applications,” Wiley, New York, 1998

[17] C. Nottegar, C. Priami and P. Degano, “Performance Evaluation of Mobile Processes Via Abstract Machines,” IEEE Transactions on Software Engineering, Vol. 27, No. 10, 2001, pp. 867-889. doi:10.1109/32.962559

[18] F. Logozzo, “Pi-Calculus as a Rapid Prototype Language For Performance Evaluation,” Proceedings of the ICLP 2001 Workshop on Specification, Analysis and Validation for Emerging Technologies in Computational Logic (SAVE 2001), 2001.

[19] S. Rahimi, M. Cobb, D. Ali, M. Paprzycki and F. Petry, “A Knowledge-Based Multi-Agent System for Geospatial Data Conflation,” Journal of Geographic Information and Decision Analysis, Vol. 6, No. 2, 2002, pp. 67-81.

[20] A. Grama, G. Karypis, V. Kumar and A Gupta, “An Introduction to Parallel Computing: Design and Analysis of Algorithms,” 2nd Edition, Addison Wesley, Reading, 2003

[21] W. R. Cockayne and M. Zyda, “Mobile Agents”, Manning Publications Company, Greenwich, 1998.

[22] H. Samet, “The Design and Analysis of Spatial Data Structures,” Addison-Wesley, Reading, 1989.

[23] S. Rahimi, “Using Api-Calculus for Formal Modeling of SDIAgent: A Multi-Agent Distributed Geospatial Data Integration,” Journal of Geographic Information and Decision Analysis, Vol. 7, No. 2, 2003, pp. 132-149.

[24] S. Rahimi, J. Bjursell, M. Paprzycki, M. Cobb and D. Ali, “Performance Evaluation of SDIAGENT, a Multi-Agent System for Distributed Fuzzy Geospatial Data Conflation,” Information Sciences, Vol. 176, No. 9, 2006. doi:10.1016/ j.ins.2005.07.009

[25] S. Derisavi, P. Kemper and W. H. Sanders, “Symbolic State-Space Exploration and Numerical Analysis of State-Sharing Composed Models,” Linear Algebra and Its Applications, Vol. 386, July 2004, pp. 137-166. doi:10. 1016/j.laa.2004.01.006

[26] S. Derisavi, H. Hermanns and W. H. Sanders, “Optimal State-Space Lumping in Markov Chains,” Information Processing Letters, Vol. 87, No. 6, 2003, pp. 309-315. doi:10.1016/S0020-0190(03)00343-0

[27] P. Buchholz, “Efficient Computation of Equivalent and Reduced Representations for Stochastic Automata,” International Journal of Computer Systems Science & Engineering, Vol. 15, No. 2, March 2000, pp. 93-103.