Abstract
This paper presents the construction of an automaton termed the Concurrent Probabilistic Reversible Automata (CPRA). It models the distributed systems which exhibit probabilistic behaviour and also relies on backtracking as the basis to make a system fault tolerant. Here, the basic concepts of non-probabilistic automata have been extended by introducing the discrete probabilities on the set of transitions for modelling the probabilistic nature of computing environment. In addition, concurrency has been implemented by defining parallel joint(\(\mbox{\textasciicircum}\)) operator dealing with the odds of shared transitions. A memory structure has also been defined to keep track of past transitions in order to facilitate the backtracking without losing the initial computations, which may result in inconsistent states as well. The major contribution of this work can be seen in three aspects: first, defining an automaton to model full non-determinism along with probabilistic characterisation without making any distinctions between states and actions by which some of the previous formalism suffers; second, association of memory with the automata that preserves concurrency during backtracking; third, the implementation of the parallel joint operator to facilitate the concurrency. Although, the full probabilistic analysis of CPRA can be performed by applying the principles of measure theory on the traces of CPRA but it is reported as future work.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Tanenbaum, A.: Computer Networks, 4th edn. Prentice Hall Professional Technical Reference (2002)
Shigong, L., Lijun, W.: Analysis of cryptographic protocols using ltl of knowledge. In: 2010 2nd International Conference on Networking and Digital Society (ICNDS), vol. 1, pp. 463–466 (2010)
Daws, C., Kwiatkowska, M., Norman, G.: Automatic verification of the ieee 1394 root contention protocol with kronos and prism. International Journal on Software Tools for Technology Transfer 5(2-3), 221–236 (2004)
Ma, J., Zhang, D., Xu, G., Yang, Y.: Model checking based security policy verification and validation. In: 2010 2nd International Workshop on Intelligent Systems and Applications (ISA), pp. 1–4 (2010)
Glabbeek, R.J.V., Smolka, S.A., Steffen, B.: Reactive, generative and stratified models of probabilistic processes. Information and Computation 121, 130–141 (1990)
Sokolova, A., de Vink, E.P.: Probabilistic automata: System types, parallel composition and comparison. In: Baier, C., Haverkort, B.R., Hermanns, H., Katoen, J.-P., Siegle, M. (eds.) Validation of Stochastic Systems. LNCS, vol. 2925, pp. 1–43. Springer, Heidelberg (2004)
Barendregt, H.P.: The Lambda Calculus, Its Syntax and Semantics, Revised Edition. Studies in Logic and the Foundations of Mathematics, vol. 103. North Holland (November 1985)
Milner, R.: Communication and Concurrency. Prentice-Hall, Inc., Upper Saddle River (1989)
De Alfaro, L.: Formal verification of probabilistic systems. PhD thesis, Stanford, CA, USA, AAI9837082 (1998)
Segala, R.: Modeling and verification of randomized distributed real-time systems. PhD thesis, Cambridge, MA, USA, Not available from Univ. Microfilms Int. (1995)
Delahaye, B., Katoen, J.-P., Larsen, K.G., Legay, A., Pedersen, M.L., Sher, F., Wąsowski, A.: Abstract probabilistic automata. In: Jhala, R., Schmidt, D. (eds.) VMCAI 2011. LNCS, vol. 6538, pp. 324–339. Springer, Heidelberg (2011)
Golovkins, M., Kravtsev, M.: Probabilistic reversible automata and quantum automata. In: Ibarra, O.H., Zhang, L. (eds.) COCOON 2002. LNCS, vol. 2387, pp. 574–583. Springer, Heidelberg (2002)
Golovkins, M., Kravtsev, M., Kravcevs, V.: On a class of languages recognizable by probabilistic reversible decide-and-halt automata. Theor. Comput. Sci. 410(20), 1942–1951 (2009)
Phillips, I., Ulidowski, I.: Reversibility and models for concurrency. Electron. Notes Theor. Comput. Sci. 192(1), 93–108 (2007)
Pnueli, A.: The temporal logic of programs. In: Proceedings of the 18th Annual Symposium on Foundations of Computer Science, SFCS 1977, pp. 46–57. IEEE Computer Society, Washington, DC (1977)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Arpit, Shafie, A., Wan Ahmad, W.F. (2014). Automata for Modeling the Distributed Probabilistic Reversible Processes. In: Gupta, P., Zaroliagis, C. (eds) Applied Algorithms. ICAA 2014. Lecture Notes in Computer Science, vol 8321. Springer, Cham. https://doi.org/10.1007/978-3-319-04126-1_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-04126-1_11
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-04125-4
Online ISBN: 978-3-319-04126-1
eBook Packages: Computer ScienceComputer Science (R0)