Abstract
Reversible computations have been widely studied from the functional point of view and energy consumption. In the literature, several authors have proposed various formalisms (mainly based on process algebras) for assessing the correctness or the equivalence among reversible computations. In this paper we propose the adoption of Markovian stochastic models to assess the quantitative properties of reversible computations. Under some conditions, we show that the notion of time-reversibility for Markov chains can be used to efficiently derive some performance measures of reversible computations. The importance of time-reversibly relies on the fact that, in general, the process’s stationary distribution can be derived efficiently by using numerically stable algorithms. This paper reviews the main results about time-reversible Markov processes and discusses how to apply them to tackle the problem of the quantitative evaluation of reversible computations.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
By purely reversible computations we mean those computations in which each step can be undone and there are no segments in which the execution direction is forward only.
- 2.
We exclude the \(\tau \) self-loops from the definition of stochastic automaton in order to simplify the semantics of synchronisation. Indeed, the \(\tau \) self-loops are irrelevant for the equilibrium distribution of the CTMC underlying the automaton.
References
Artalejo, J.R., Economou, A., Lopez-Herrero, M.J.: The maximum number of infected individuals in SIS epidemic models: computational techniques and quasi-stationary distributions. J. Comput. Appl. Math. 233, 2563–2574 (2010)
Barbierato, E., Dei Rossi, G.-L., Gribaudo, M., Iacono, M., Marin, A.: Exploiting product forms solution techniques in multiformalism modeling. Electr. Notes Theor. Comput. Sci. 296, 61–77 (2013)
Barbour, A.D.: Quasi-stationary distributions in markov population processes. Adv. Appl. Prob. 8, 296–314 (1976)
Baskett, F., Chandy, K.M., Muntz, R.R., Palacios, F.G.: Open, closed, and mixed networks of queues with different classes of customers. J. ACM 22(2), 248–260 (1975)
Bugliesi, M., Gallina, L., Hamadou, S., Marin, A., Rossi, S.: Behavioural equivalences and interference metrics for mobile ad-hoc networks. Perform. Eval. 73, 41–72 (2014)
Casale, G., Smirni, E.: KPC-toolbox: fitting markovian arrival processes and phase-type distributions with MATLAB. SIGMETRICS Perform. Eval. Rev. 39(4), 47 (2012)
Danos, V., Krivine, J.: Reversible communicating systems. In: Gardner, P., Yoshida, N. (eds.) CONCUR 2004. LNCS, vol. 3170, pp. 292–307. Springer, Heidelberg (2004)
Gallina, L., Hamadou, S., Marin, A., Rossi, S.: A probabilistic energy-aware model for mobile ad-hoc networks. In: Al-Begain, K., Balsamo, S., Fiems, D., Marin, A. (eds.) ASMTA 2011. LNCS, vol. 6751, pp. 316–330. Springer, Heidelberg (2011)
Gordon, W.J., Newell, G.F.: Cyclic queueing networks with exponential servers. Oper. Res. 15(2), 254–265 (1967)
Harrison, P.G.: Turning back time in Markovian process algebra. Theoret. Comput. Sci. 290(3), 1947–1986 (2003)
Harrison, P.G.: Reversed processes, product forms and a non-product form. Elsevier Linear Algebra Appl. 386, 359–381 (2004)
Hillston, J.: A Compositional Approach to Performance Modelling. Cambridge Press, Cambridge (1996)
Hillston, J., Marin, A., Piazza, C., Rossi, S.: Contextual iumpability. In: Proceedings of Valuetools 2013 Conference. ACM Press (2013)
Jackson, J.R.: Jobshop-like queueing systems. Manag. Sci. 10, 131–142 (1963)
Kant, K.: Introduction to Computer System Performance Evaluation. McGraw-Hill, New York (1992)
Kelly, F.: Reversibility and Stochastic Networks. Wiley, New York (1979)
Lanese, I., Mezzina, C.A., Tiezzi, F.: Causal-consistent reversibility. Bull. EATCS 114, 17 (2014)
Marin, A., Rossi, S.: On discrete time reversibility modulo state renaming and its applications. In: Proceedings of Valuetools 2014 Conference (2014)
Marin, A., Rossi, S.: On the relations between lumpability and reversibility. In: Proceedings of MASCOTS 2014, pp. 427–432 (2014)
Marin, A., Rossi, S.: Quantitative analysis of concurrent reversible computations. In: Sankaranarayanan, S., Vicario, E. (eds.) FORMATS 2015. LNCS, vol. 9268, pp. 206–221. Springer, Heidelberg (2015)
Mészáros, A., Papp, J., Telek, M.: Fitting traffic traces with discrete canonical phase type distributions and Markov arrival processes. Appl. Math. Comput. Sci. 24(3), 453–470 (2014)
Perumalla, K.S.: Introduction to Reversible Computing. CRC Press, Boca Raton (2013)
Plateau, B.: On the stochastic structure of parallelism and synchronization models for distributed algorithms. SIGMETRICS Perf. Eval. Rev. 13(2), 147–154 (1985)
Ross, S.M.: Stochastic Processes, 2nd edn. Wiley, Hoboken (1996)
Stewart, W.J.: Introduction to the Numerical Solution of Markov Chains. Princeton University Press, Princeton (1994)
Whittle, P.: Systems in Stochastic Equilibrium. Wiley, Hoboken (1986)
Yokoyama, T., Glück, R.: A reversible programming language and its invertible self-interpreter. In: Proceedings of the 2007 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-based Program Manipulation, pp. 144–153, New York, NY, USA. ACM (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Balsamo, S., Cavallin, F., Marin, A., Rossi, S. (2016). Applying Reversibility Theory for the Performance Evaluation of Reversible Computations. In: Wittevrongel, S., Phung-Duc, T. (eds) Analytical and Stochastic Modelling Techniques and Applications. ASMTA 2016. Lecture Notes in Computer Science(), vol 9845. Springer, Cham. https://doi.org/10.1007/978-3-319-43904-4_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-43904-4_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-43903-7
Online ISBN: 978-3-319-43904-4
eBook Packages: Computer ScienceComputer Science (R0)