微信服务号

微信订阅号

2025年6月13日 23:02 星期五
首页 > 过刊浏览>2002年第13卷第2期 >203-213
PDF HTML阅读 XML下载 导出引用 引用提醒
随机进程代数与随机Petri网
作者:
基金项目:

国家自然科学基金资助项目(69873012);国家重点基础研究发展规划973资助项目(G1999032707)


Stochastic Process Algebras and Stochastic Petri Nets
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [53]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    针对随机进程代数(stochastic process algebra,简称SPA)的基本模型方法、模型特点和该领域的主要研究成果进行了综述.比较了SPA和随机Petri网(stochastic Petri nets,简称SPN)之间的异同点,并讨论了SPA转化为相应SPN的语义和将SPA的研究成果应用于SPN的方法.最后对SPA进一步研究工作的方向作了展望.

    Abstract:

    This is a review paper about the basic model approaches and model characteristics as well as the recent works on SPA. In this paper, the difference and similarities about SPA and SPN are compared and the approach of translating SPA into the SPN semantics and exploiting SPA achievements for SPN are discussed. At the end of this paper, some research directions and open problems are presented in this area.

    参考文献
    [1] Bolognesi, T., Lucidi, F., Trigila, S. Converging towards a timed LOTOS standard. Computer Standards and Interfaces, 1994,16(2): 87～118.
    [2] Leonard, L., Leduc, G. An introduction to ET-LOTOS for the description of time sensitive systems. Computer Networks and ISDN Systems, 1997,29(3):271～292.
    [3] Schneider, S. An operational semantics for timed CSP. Information & Computation, 1995,116(2):193～213.
    [4] Moller, F., Tofts, C. A temporal calculus of communicating systems. In: Baeten, J.C.M., Klop, J-W., eds. Proceedings of Concur'90: Theories of Concurrency-Unification and Extension. LNCS 458, Amsterdam: Springer-Verlag, 1990. 401～415.
    [5] Wang, Y. Real-Time behaviour of asynchronous agents. In: Baeten, J.C.M., Klop, J-W., eds. Concur'90: Theories of Concurrency- Unification and Extension. LNCS 458, Amsterdam: Springer-Verlag, 1990. 502～520.
    [6] Herzog, U. Formal description, time and performance analysis: a framework. Technical Report 15/90. IMMD VII, Friedrich- Alexander-universitat, Erlangen-Nurnberg, Germany, 1990.
    [7] Gilmore, S., Hillston,J. The PEPAWorkbench: a tool to support a process algebra-based approach to performance modeling. In: Haring, G., Kotsis, G., eds. Proceedings of Modeling Techniques and Tools for Computer Performance Evaluation. LNCS794, 1994.
    [8] Hermanns, H., Herzog, U., Mertsiotakis, V. Stochastic process algebras-between LOTOS and Markov chains. Computer Networks and ISDN Systems, 1998,30(9～10):901～924.
    [9] Hermanns, H., Ribaudo, M. Exploiting symmetries in stochastic process algebras. In: Proceedings of the European Simulation Multiconference ESM'98, SCS Europe. 1998.763～770. http://citeseer.nj.nec.com/context/552192/114690.
    [10] Hillston, J., Mertsiotakis, V. A simple time scale decomposition technique for SPAs. Computer Journal,1995,38(7):566～577.
    [11] Hermanns, H., Herzog, U., Hillston, J. Stochastic process algebras--a formal approach to performance modeling. In: Bagchi, K., Zobrist, G., eds. Proceedings of Performance Tools'95/MMB'95. Heidelberg, 1995. http://www.home.cs.utwente.nl/～hermanns/ mypapers.html.
    [12] Hermanns, H., Herzog, U., Mertsiotakis, V. Stochastic process algebras as a tool for performance and dependability modeling. In: Proceedings of International Computer Performance and Dependability Symposium (IPDS'95). IEEE CS Press, 1995. 102～113. http://www7.informatik.uni-erlangen.de/tree/IMMD-VII/Persons/vsmertsi/papers/
    [13] Hillston., J. A compositional approach to performance modeling [Ph.D. Thesis]. University of Edinburgh, 1994. CST-107-94. http://www.dcs.ed.ac.uk/home/stg/PEPA/papers.html.
    [14] Bernardo, M., Gorrieri, R. A tutorial on EMPA: a theory of concurrent processes with nondeterminism, priorities, probabilities and time. The Computer Science, Palma de Mallorca, Spain: Springer-Verlag, 1998,202(1～2):1～54.
    [15] Hermanns, H., Klehmet, U., Mertsiotakis, V., et al. Compositional performance modeling with the TIPPTOOL. In: Puigjaner, R., Savio, N.N., Serra, B., eds. Computer Performance Evaluation. LNCS 1469, 1998. 51～63.
    [16] Hermanns, H., Mertsiotakis, V., Rettelbach, M. A construction and analysis tool based on the stochastic process algebra TIPP. In: Proceedings of the 2nd International Workshop on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'96). Lecture Notes in Computer Science Vol 1055, Berlin: Springer-Verlag, 1996. 427～430.
    [17] Clark, G., Gilmore, S., Hillston, J., et al. Experiences with the PEPA performance modeling tools. IEEE Software, 1999,146(1):11～19.
    [18] Bernardo, M., Cleaveland, R., Sims, S., et al. TWOTOWERS: a tool integrating functional and performance analysis of concurrent systems. In: Budkowski, S., Cavali, A., Najm, E., eds. Proceedings of the FORTE/PSTV'98. Paris: Kluwer, 1998. 457～467.
    [19] Hermanns, H., Lohrey, M., Priority and maximal progress are completely aximatisable. In: Sangiorgi, D., de Simone, R., eds. Proceedings of the CONCUR'98 Concurrency Theory. Lecture Notes in Computer Science, Berlin: Springer-Verlag, 1998,1446: 237～252.
    [20] Hillston, J., Hermanns, H., Herzog. U. Stochastic process algebras: integrating qualitative and quantitative modeling. http://www7. informatik.uni-erlangen.de/tipp/papers.html.
    [21] Hermanns, H., Herzog, U., Mertsiotikis, V., et al. Stochastic process algebra--foundations and relations with SPN. In: PERFORMANCE TOOLS'97/PNPM'97 ; Saint Malo, 1997. http://wwwhome.cs.utwente.nl/～hermanns/mypapers.html.
    [22] Hillston, J., Ribaudo, M. Stochastic process algebras: a new approach to performance modeling. In:Bagchi, K., Zobrist, G., eds. Modeling and Simulation of Advanced Computer Systems. Gordon Breach, 1998. http://www.dcs.ed.ac.uk/home/stg/PEPA/ papers.html.
    [23] Larsen, K.G., Skou, A. Bisimulation through probabilistic testing. Information and Computation, 1991,94(1):1～28.
    [24] Hillston., J. Compositional markovian modeling using a process algebra. In: Stewart, W., ed. Proceedings of the 2nd International Workshop on Numerical Solution of Markov Chains: Computations with Markov Chains. Raleigh: Kluwer Academic Press, 1995. 177～196.
    [25] Rettelbach, M., Siegle, M. Compositional minimal semantics for the stochastic process algebra: TIPP. In: Herzog, U., Rettelbach, M., eds. Regensberg/Erlangen, July Arbeits-berichte des IMMD. Universitat Erlangen-Nurnberg. 1994. 89～106. http://citeseer.nj. nec.com/rettelbach94compositional.html.
    [26] Mitrani, I., Ost, A., Rettelbach, M. Tipp and the spectral expansion method. In: Bacceli, F., Mitrani, I., eds. Quantitative Modeling in Parrallel Systems. Berlin: Springer-Verlag, 1995. 99～113.
    [27] Courtois, P.J. Decomposability, Queueing and Computer System Applications. ACM Monograph Series, 1977.
    [28] Mitrani, I., Ost, A., Rettelbach, M. Quantitative modeling in parallel systems, chapter TIPP and the spectral expansion method. Berlin: Springer, 1995. http://www7.informatik.uni-erlangen.de/tree/IMMD-VII/Persons/vsmertsi/papers/.
    [29] Harrison, P., Hillston, J. Exploiting quasi-reversible structures in Markovian process algebra models models. The Computer Journal, 1995,38(7):510～520.
    [30] Sereno, M. Towards a product form solution for stochastic process algebra. The Computer Journal, 1995,38(7):622～632.
    [31] Hillston, J., Thomas, N. Product form solution for a class of PEPA models. Performance Evaluation, 1999,35(3～4):171～192.
    [32] Mitrani, I., Mitra, D.. A spectral expansion method for random walks on semi-Infinite strips. In: Beauwens, R., de Groen, P. , eds. Iterative Methods in Linear Algebra. North-Holland: Elsevier, 1992. 141～149.
    [33] Sereno, M. Towards a product form solution for stochastic process algebras. Computer Journal, 1995,38(7):622～632.
    [34] Hillston, J. Exploiting structure in solution: decomposing composed models. http://www.dcs.ed.ac.uk/home/stg/PEPA/.
    [35] Iienderson, W., Taylor, P.G. Embedded processes in stochastic petri nets. IEEE Transactions on Software Engineering, 1991,17(2): 108～116.
    [36] Mertsiotakis, V. Approximate analysis methods for stochastic process algebras [Ph.D. Thesis]. Erlangen: Universitat Erlangen- Nurnberg, 1994. http://citeseer.nj.nec.com/context/300986/0.
    [37] Mertsiotakis, V., Silva, M. Throughput approximation of decision free processes using decomposition. In: Proceedings of the 7th International Workshop on Petri Nets and Performance Models. Los Alamitos, CA: IEEE CS-Press. 1997. 174～182. http://www. informatik.uni-hamburg.de/TGI/pnbib/m/mertsiotakis_v1.html.
    [38] Clark, G., Gimore, S., Hillston, J., et al. Experience with the PEPA performance modeling tools. In: Pooley, R., Thomas, N., eds, IEEE Software, 1999,146(1):11～19.
    [39] Donatelli, S., Ribaudo, M., Hillston, J. A comparison of performance evaluation process algebra and generalized stochastic Petri nets. In: Proceedings of the 6th International Workshop on Petri Nets and Performance Models. Los Alamitos, CA: IEEE Press, 1995. 158～168. http://citeseer.nj.nec.com/ context/179345/120786.
    [40] RettelBach, M. Towards a theory of GSPA. In: Gilmore, S., Hillston, J., eds. Proceedings of the 3rd Process Algebra and Performance Modeling Workshop. Edinburgh, 1995.
    [41] Donatell, S., Hermanns, H., Hillston, J., et al. GSPN and SPA compared in practice. In: Baccelli, Mitrani, eds. Quantitative Modeling in Parallel Systems. Berlin: Springer-Verlag, 1995. 38～51.
    [42] Ribaudo, M. Stachostic Petri net semantics for process algebras. In: Proceedings of the 6th International Workshop on Petri Nets and Performance Models. Los Alamitos CA: IEEE Press, 1995. 148～157. http://www.computer.org/proceedings/pnpm/7210/ 72100148abs.htm.
    [43] Bernardo, M., Donatiello, L., Gorrieri, R. Giving a net semantics to markovian process. In: Proceedings of the 6th International Workshop on Petri Nets and Performance Models. Los Alamitos CA: IEEE Press. 1995. 169～178. http://citeseer.nj.nec.com/ contest/59121/129308
    [44] Buchlolz, P. A notion of equivalence for stochastic petri nets. In: de Michelis, G., Diaz, M., eds. Application and Theory of Petri Nets. LNCS 935, Springer, 1995. 161～180.
    [45] Buchholz, P. Markovian process algebra: composition and equivalence. In: Herzog, U., Rettelbach, M., eds. Proceedings of the 2nd Process Algebra and Performance Modeling Workshop. Erlangen, 1994. 11～30.
    [46] Hermanns, H., Rettelbach, M. Syntax, semantics, equivalence, and axioms for MTIPP. In: Proceedings of the 2nd Process Algebra and Performance Modeling Workshop. Erlangen, 1994. 71～87. http://citeseer.nj.nec.com/hermanns94syntax.html.
    [47] Rettelbach, M.. Stochastiche prozebalgebren mit zeitlosen akivitaten und probabilistischen verzweigungen[Ph.D. Thesis]. Universitat Erlangen-Nurnberg, 1996.
    [48] Hermanns, H., Herzog, U., Mertsiotakis, V., et al. Exploiting stochastic process algebra achievements for generalized stochastic petri nets. Proceedings of the 7th International Workshop on Petri Nets and Performance Models, Saint Malo: IEEE CS Press, 1997. 183～192. http://citeseer.nj.nec.com/context/377009/186791.
    [49] Lin, C., Marinescu, D.C. Stochastic high-level Petri nets and applications. IEEE Transactions on Computers, 1988,37(7):815～825.
    [50] Ribaudo, M. On the aggregation techniques in stochastic petri nets and stochastic process algebras. The Computer Journal, 1995,38 (7):600～611.
    [51] Buchholz, P. Lumpability and nearly-lumpability in hierarchical queueing networks. In: Computer Performance and Dependability Symposium. 1995. 82～91. http://www.ieee.org.
    [52] Brinksma, Ed. Stochastic process algebras: Linking process descriptions with performance. 1999 IFIP TC6/WG6.1 Joint International Conference (FORTE/PSTV'99) on Formal Description Techniques (FORTE XLL) for Distributed Systems and Communication Protocols, and Protocol Specification, Testing, and Verification (PSTV XIX). 1999.
    [53] Hachtel, G., Macii, E., Padro, A., et al. Markovian analysis of large finite-state machines. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1996,15(12):1479～1493.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

林闯,魏丫丫.随机进程代数与随机Petri网.软件学报,2002,13(2):203-213

复制
分享
文章指标
  • 点击次数:6744
  • 下载次数: 8317
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2001-05-25
  • 最后修改日期:2001-09-26
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第20042774位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号