×

Extending timed process algebra with discrete stochastic time. (English) Zbl 1170.68542

Meseguer, José (ed.) et al., Algebraic methodology and software technology. 12th international conference, AMAST 2008, Urbana, IL, USA, July 28–31, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79979-5/pbk). Lecture Notes in Computer Science 5140, 268-283 (2008).
Summary: When extending timed process algebra with discrete stochastic time, typical standard notions like time additivity are hard to preserve in the presence of the race condition. We propose context-sensitive interpolation as a restricted form of time additivity to accommodate the extension with stochastic time. We also present a stochastic process algebra featuring an explicit account of two types of race conditions in terms of conditional random variables. The approach enables compositional modeling, a non-trivial expansion law, and explicit manipulation of maximal progress.
For the entire collection see [Zbl 1154.68019].

MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

Software:

MoDeST
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Nicollin, X.; Sifakis, J.; Huizing, C.; de Bakker, J. W.; Rozenberg, G.; de Roever, W.-P., An overview and synthesis of timed process algebras, Real-Time: Theory in Practice, 526-548 (1992), Heidelberg: Springer, Heidelberg
[2] Hermanns, H., Mertsiotakis, V., Rettelbach, M.: Performance analysis of distributed systems using TIPP. In: Proc. UKPEW 1994, pp. 131-144 (1994)
[3] Bravetti, M., Bernardo, M., Gorrieri, R.: From EMPA to GSMPA: Allowing for general distributions. In: Proc. PAPM 1997, pp. 17-33 (1997)
[4] D’Argenio, P.; Katoen, J. P., A theory of stochastic systems, part II: Process algebra, Information and Computation, 203, 1, 39-74 (2005) · Zbl 1106.68073
[5] Bravetti, M.: Specification and Analysis of Stochastic Real-time Systems. PhD thesis, Universitá di Bologna (2002) · Zbl 1065.68581
[6] López, N.; Núñez, M., NMSPA: A non-Markovian model for stochastic processes, Proc. ICDS 2000, 33-40 (2000), Los Alamitos: IEEE, Los Alamitos
[7] Bohnenkamp, H.; D’Argenio, P.; Hermanns, H.; Katoen, J.-P., MODEST: A compositional modeling formalism for hard and softly timed systems, IEEE Transactions on Software Engineering, 32, 812-830 (2006)
[8] Katoen, J. P.; D’Argenio, P. R.; Brinksma, E.; Hermanns, H.; Katoen, J.-P., General distributions in process algebra, Lectures on Formal Methods and Performance Analysis, 375-429 (2001), Heidelberg: Springer, Heidelberg · Zbl 0990.68091
[9] D’Argenio, P.: From stochastic automata to timed automata: Abstracting probability in a compositional manner. In: Proc. WAIT 2003(2003)
[10] Markovski, J.; de Vink, E. P.; Horváth, A.; Telek, M., Embedding real-time in stochastic process algebras, Formal Methods and Stochastic Models for Performance Evaluation, 47-62 (2006), Heidelberg: Springer, Heidelberg · Zbl 1185.68449
[11] Markovski, J.; de Vink, E.-P., Real-time process algebra with stochastic delays, Proc. ACSD 2007, 177-186 (2007), Los Alamitos: IEEE Computer Society Press, Los Alamitos
[12] Markovski, J., de Vink, E.: Discrete real-time and stochastic-time process algebra for performance analysis of distributed systems. In: Proc. ACSD 2008 (to be published, 2008) · Zbl 1170.68542
[13] Cattani, S.; Segala, R.; Kwiatkowska, M.; Norman, G.; Sassone, V., Stochastic transition systems for continuous state spaces and non-determinism, Foundations of Software Science and Computational Structures, 125-139 (2005), Heidelberg: Springer, Heidelberg · Zbl 1118.68568
[14] Markovski, J., de Vink, E.P.: Discrete real-time and stochastic-time process algebra for performance analysis of distributed systems. Technical Report CS 08/10, Eindhoven University of Technology (2008) · Zbl 1170.68542
[15] D’Argenio, P.; Katoen, J. P., A theory of stochastic systems, part I: Stochastic automata, Information and Computation, 203, 1, 1-38 (2005) · Zbl 1105.68061
[16] Howard, R., Dynamic Probabilistic Systems (1971), Chichester: Wiley, Chichester · Zbl 0227.90031
[17] Baeten, J.; Middelburg, C., Process Algebra with Timing (2002), Heidelberg: Springer, Heidelberg · Zbl 1021.68063
[18] López, N.; Núñez, M.; Van Hung, D.; Wirsing, M., Weak stochastic bisimulation for non-Markovian processes, Theoretical Aspects of Computing - ICTAC 2005, 454-468 (2005), Heidelberg: Springer, Heidelberg · Zbl 1169.68548
[19] van Niftrik, W.: Context sensitive interpolation. Master thesis, Eindhoven University of Technology (in progress, 2008)
[20] Baeten, J. C.M.; Bergstra, J. A.; Klop, J. W., On the consistency of Koomen’s fair abstraction rule, Theoretical Computer Science, 51, 1, 129-176 (1987) · Zbl 0621.68010
[21] Bravetti, M.; D’Argenio, P.; Baier, C.; Haverkort, B. R.; Hermanns, H.; Katoen, J.-P.; Siegle, M., Tutte le algebre insieme – concepts, discussions and relations of stochastic process algebras with general distributions, Validation of Stochastic Systems, 44-88 (2004), Heidelberg: Springer, Heidelberg · Zbl 1203.68113
[22] Bryans, J.; Bowman, H.; Derrick, J., Model checking stochastic automata, ACM Transactions on Computational Logic, 4, 4, 452-492 (2003) · Zbl 1365.68316
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.