Call for Paper - March 2020 Edition
IJCA solicits original research papers for the March 2020 Edition. Last date of manuscript submission is February 20, 2020. Read More

A Stochastic Extension of the Routing Calculi

IJCA Proceedings on International Conference on Distributed Computing and Internet Technology
© 2015 by IJCA Journal
ICDCIT 2015 - Number 1
Year of Publication: 2015
Rama Kant
Manish Gaur

Rama Kant and Manish Gaur. Article: A Stochastic Extension of the Routing Calculi. IJCA Proceedings on International Conference on Distributed Computing and Internet Technology ICDCIT 2015(1):13-17, January 2015. Full text available. BibTeX

	author = {Rama Kant and Manish Gaur},
	title = {Article: A Stochastic Extension of the Routing Calculi},
	journal = {IJCA Proceedings on International Conference on Distributed Computing and Internet Technology},
	year = {2015},
	volume = {ICDCIT 2015},
	number = {1},
	pages = {13-17},
	month = {January},
	note = {Full text available}


The modern distributed systems have not only functional requirements (i. e. absence of deadlock, livelock etc. ) but also have non-functional requirements (i. e. security, reliability, performance, Quality of Service(QoS) etc. ). The methods for checking their correctness and analyze their performance is at very primitive stage. In the last few decades, formal verification techniques such as process algebras offer a powerful and rigorous approach for establishing the correctness of computer systems. Routing calculi (a such process algebra which is an elaboration of asynchronous distributed Pi calculus ) which models a distributed networks with router as an active component in determining the path between communicating processes. This algebra also take into account various types of routing tables updates upon creation of new nodes. The semantics of routing calculi has been defined to incorporate the cost of communicating processes after taking into consideration the number of routers crossings. In this paper, we survey to extend the routing calculi. This is done with an intention to aggregate the number of states in the state space of calculus. We propose this extension along the lines of PEPA nets. A brief sketch of the proposed extension is also given in this paper as future direction of our research.


  • Ajmone Marsan, M. and Bobbio, A. and Donatelli, S. Petri nets in performance analysis: An introduction. In Reisig, Wolfgang and Rozenberg, Grzegorz, editors, Lectures on Petri Nets I: Basic Models in Lecture Notes in Computer Science, pages 211-256. Springer Berlin Heidelberg, 1998.
  • Marco Bernardo and Roberto Gorrieri and Mura Anteo Zamboni. A Tutorial on EMPA: A Theory of Concurrent Processes with Nondeterminism, Priorities, Probabilities and Time. Theoretical Computer Science, 202:1–54, 1997.
  • Peter Buchholz. Markovian Process Algebra: Composition and Equivalence. pages 11–30, 1994.
  • Chiola, G. and Dutheillet, C. and Franceschinis, G. and Haddad, S. Stochastic well-formed colored nets and symmetric modeling applications. Computers, IEEE Transactions on, 42(11):1343-1360, 1993.
  • Clarke et. al. Model Checking and the State Explosion Problem. In Meyer, Bertrand and Nordio, Martin, editors, Tools for Practical Software Verification in Lecture Notes in Computer Science, pages 1-30. Springer Berlin Heidelberg, 2012.
  • S. Donatelli and M. Ribaudo and J. Hillston. A Comparison of Performance Evaluation Process Algebra and Generalized Stochastic Petri Nets. In Proc. 6th International Workshop on Petri Nets and Performance Models, pages 158–168, 1995. IEEE Computer Society Press.
  • Fuggetta, A. and Picco, G. P. and Vigna, Giovanni. Understanding code mobility. Software Engineering, IEEE Transactions on, 24(5):342-361, 1998.
  • Manish Gaur and Rama Kant. A Survey on Process Algebraic Stochastic Modelling of Large Distributed Systems for its Performance Analysis (Accepted). ICECCS in to be appear in conference proceedings, 2014. IEEE Xplore Digital Library.
  • Gilmore, Stephen and Hillston, Jane and Kloul, Lela and Ribaudo, Marina. Software Performance Modelling Using PEPA Nets. Proceedings of the 4th International Workshop on Software and Performance in WOSP '04, pages 13–23, New York, NY, USA, 2004. ACM.
  • Gilmore, Stephen and Hillston, Jane and Kloul, Leïla. PEPA Nets. In Calzarossa, MariaCarla and Gelenbe, Erol, editors, Performance Tools and Applications to Networked Systems in Lecture Notes in Computer Science, pages 311-335. Springer Berlin Heidelberg, 2004.
  • Hillston, J and Ribaudo, M. Modelling Mobility with PEPA Nets. In Aykanat, Cevdet and Dayar, Tugrul and Korpeoglu, Ibrahim, editors, ISCIS in Lecture Notes in Computer Science, pages 513-522, 2004. Springer.
  • Manish Gaur, Ian Mackie and Simon Gay. A Routing Calculus with Flooding Updates. ICDCIT in Lecture Notes in Computer Science, 2015. Springer.
  • http://www. inf. ed. ac. uk/ teaching / courses /pm/ Note15. pdf.
  • Allan Clark, Stephen Gilmore, Jane Hillston, and Mirco Tribastone. Stochastic Process Algebras. LFCS, School of Informatics, University of Edinburgh.
  • J. A. Bergstra and J. W. Klop. Algebra of communicating processes with abstraction. Theoretical Computer Science, 37(0):77 - 121, 1985.
  • Brodo, Linda and Degano, Pierpaolo and Gilmore, Stephen and Hillston, Jane and Priami, Corrado. Performance Evaluation for Global Computation. In Priami, Corrado, editors, Global Computing. Programming Environments, Languages, Security, and Analysis of Systems in Lecture Notes in Computer Science, pages 229-253. Springer Berlin Heidelberg, 2003.
  • Peter Buchholz. Hierarchical Markovian Models -Symmetries and Reduction-. Performance Evaluation, pages 234–246, 1992.
  • Andrew T. Campbell and S. Keshav. Quality of service in distributed systems. Computer Communications, :21(4):291-293, 1998.
  • Chiola, G. and Dutheillet, C. and Franceschinis, G. and Haddad, S. Stochastic Well-Formed Coloured Nets and Multiprocessor Modelling Applications. In Jensen, Kurt and Rozenberg, Grzegorz, editors, High-level Petri Nets, pages 504-530. Springer Berlin Heidelberg, 1991.
  • Clark, Allan and Gilmore, Stephen and Hillston, Jane and Tribastone, Mirco. Stochastic Process Algebras. In Bernardo, Marco and Hillston, Jane, editors, Formal Methods for Performance Evaluation in Lecture Notes in Computer Science, pages 132-179. Springer Berlin Heidelberg, 2007.
  • A. Francalanza and M. Hennessy. A theory of system behaviour in the presence of node and link failures. In CONCUR, :368-382, 2005.
  • Adrian Francalanza and Matthew Hennessy. A theory of system behaviour in the presence of node and link failure. Inf. Comput. , :206(6):711-759, 2008.
  • Manish Gaur. A Routing Calculus: Towards formalising the cost of computation in a distributed computer network. PhD, Informatics, University of Sussex, U. K. , 2008.
  • Manish Gaur and Matthew Hennessy. . Counting the cost in the picalculus (extended abstract). Electronic Notes in Theoretical Computer Science (ENTCS), :229:117-129, 2009.
  • Manish Gaur and Rama Kant. Article: DR F : A Fault Tolerant Distributed Routing Calculi. International Journal of Computer Applications, 40(7):1-7, 2012. Published by Foundation of Computer Science, New York, USA.
  • Manish Gaur. A routing calculus for distributed computing. In Elena Troubitsyna, editor, Proceedings of Doctoral Symposium held in conjunction with Formal Methods 2008,Turku Centre for Computer Science General Publication, 48:23-32. , 2008.
  • Matthew Hennessy and Julian Rathke. Typed behavioural equivalences for processes in thepresence of subtyping. Mathematical Structures in Computer Science, :14(5):651-684, 2004.
  • Matthew Hennessy. A distributed Pi-Calculus. . Cambridge University Press, 2007.
  • Holger Hermanns and Joost-Pieter Katoen. Automated Compositional Markov Chain Generation for a Plain-Old Telephone System. SCIENCE OF COMPUTER PROGRAMMING, pages 97–127, 1999.
  • J . Hillston. Fluid flow approximation of PEPA models. Quantitative Evaluation of Systems, 2005. Second International Conference on the, pages 33-35, 2005.
  • Hillston, Jane and Ciocchetta, Federica and Duguid, Adam and Gilmore, Stephen. Integrated Analysis from Abstract Stochastic Process Algebra Models. In Heiner, Monika and Uhrmacher, AdelindeM. , editors, Computational Methods in Systems Biology in Lecture Notes in Computer Science, pages 2-4. Springer Berlin Heidelberg, 2008.
  • Jane Hillston and Mirco Tribastone and Stephen Gilmore. Stochastic Process Algebras: From Individuals to Populations. The Computer Journal, 2011.
  • Jane Hilston. A compositional Approach to Performance Modeling. Distinguished Dissertations in Computer Science. Cambridge University Press. , 1996.
  • Hoare, C. A. R. Communicating Sequential Processes. Commun. ACM, 21(8):666–677, 1978.
  • Kim G. Larsen and Arne Skou. Bisimulation through probabilistic testing. in "Conference Record of the 16th ACM Symposium on Principles of Programming Languages (POPL, pages 344–352, 1989.
  • M. Hennessy, J. Riely. Resource access control in systems of mobile agents. Information and Computation . , :173 :82-120, 2002.
  • R. Milner. Communicating and mobile systems: The -Calculus. Cambridge University Press, 1999.
  • Robin Milner. A Calculus of Communicating Systems. volume 92 of Lecture Notes in Computer Science. Springer, 1980.
  • Pedro R. D'Argenio, Joost-Pieter Katoen, and Ed Brinksma. An algebraic approach to the specification of stochastic systems(exteneded abstract). In D. Gries and W. P. de Roever,editors, Proceedings of the IFIP working conference on Programming Concepts and Methods, :126-147, 1998.
  • Pourranjbar, Alireza and Hillston, Jane. An Aggregation Technique for Large-scale PEPA Models with Non-uniform Populations. Proceedings of the 7th International Conference on Performance Evaluation Methodologies and Tools in ValueTools '13, pages 20–29, ICST, Brussels, Belgium, Belgium, 2013. ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering).
  • R. W. Butler. "What is Formal Methods". Available online from http://shemesh. larc. nasa. gov/fm/fm-what. html.
  • Richard A. Hayden , Jeremy T. Bradley. A fluid analysis framework for a Markovian process algebra. Theoretical Computer Science, 411(22 24):2260 2297, 2010.
  • Rocco De Nicola, Daniele Gorla, and Rosario Pugliese. Basic observables for a calculus for global computing. Inf. Comput. , :205(10):1491-1525, 2007.
  • Davide Sangiorgi and DavidWalker. The -Calculus: A theory of Mobile Processes. . Cambridge University Press, 2001.
  • W. Richard Stevens. TCP/IP Illustrated : The Protocols,, volume 1. Addison-Wesley, 1994.
  • Tribastone, Mirco. The PEPA Plug-in Project. Proceedings of the Fourth International Conference on Quantitative Evaluation of Systems in QEST '07, pages 53–54, Washington, DC, USA, 2007. IEEE Computer Society.
  • Trivedi, Kishor S. Probability and Statistics with Reliability, Queuing and Computer Science Applications. John Wiley and Sons Ltd. , Chichester, UK, 2nd edition edition, 2002.
  • Kenneth J. Turner and Marten van Sinderen and K. J. Turner and M. Van Sinderen. LOTOS Specification Style for OSI. The LOTOSPHERE Project, pages 137–159, 1992. Kluwer.
  • Valmari, Antti. The state explosion problem. In Reisig, Wolfgang and Rozenberg, Grzegorz, editors, Lectures on Petri Nets I: Basic Models in Lecture Notes in Computer Science, pages 429-528. Springer Berlin Heidelberg, 1998.
  • W. Reisig. Petri Nets: An Introduction. Springer-Verlag, 1982.