{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T09:01:28Z","timestamp":1772528488477,"version":"3.50.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T00:00:00Z","timestamp":1698278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Italian National Recovery and Resilience Plan (NRRP) of NextGenerationEU"},{"name":"Telecommunications of the Future","award":["PE00000001"],"award-info":[{"award-number":["PE00000001"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Comput. Simul."],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"<jats:p>We evaluate a stochastic upper bound on the response time Probability Density Function (PDF) of complex workflows through an efficient and accurate compositional approach. Workflows consist of activities having generally distributed stochastic durations with bounded supports, composed through sequence, choice\/merge, and balanced\/unbalanced split\/join operators, possibly breaking the structure of well-formed nesting. Workflows are specified using a formalism defined in terms of Stochastic Time Petri Nets that permits decomposition into a hierarchy of subworkflows with positively correlated response times, guaranteeing that a stochastically larger end-to-end response time PDF is obtained when intermediate results are approximated by stochastically larger PDFs and when dependencies are simplified by replicating activities appearing in multiple subworkflows. In particular, an accurate stochastically larger PDF is obtained by combining shifted truncated Exponential terms with positive or negative rates. Experiments are performed on sets of manually and randomly generated models with increasing complexity, illustrating under which conditions different decomposition heuristics work well in terms of accuracy and complexity and showing that the proposed approach outperforms simulation having the same execution time.<\/jats:p>","DOI":"10.1145\/3591205","type":"journal-article","created":{"date-parts":[[2023,4,5]],"date-time":"2023-04-05T11:59:59Z","timestamp":1680695999000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Compositional Safe Approximation of Response Time Probability Density Function of Complex Workflows"],"prefix":"10.1145","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5896-4860","authenticated-orcid":false,"given":"Laura","family":"Carnevali","sequence":"first","affiliation":[{"name":"Department of Information Engineering, University of Florence, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5110-203X","authenticated-orcid":false,"given":"Marco","family":"Paolieri","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Southern California, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6047-3796","authenticated-orcid":false,"given":"Riccardo","family":"Reali","sequence":"additional","affiliation":[{"name":"Department of Information Engineering, University of Florence, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4983-4386","authenticated-orcid":false,"given":"Enrico","family":"Vicario","sequence":"additional","affiliation":[{"name":"Department of Information Engineering, University of Florence, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,10,26]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/978-3-642-54792-8_16","volume-title":"Proceedings of the International Conference on Principles of Security and Trust","author":"Arnold Florian","year":"2014","unstructured":"Florian Arnold, Holger Hermanns, Reza Pulungan, and Mari\u00eblle Stoelinga. 2014. Time-dependent analysis of attacks. In Proceedings of the International Conference on Principles of Security and Trust. Springer, 285\u2013305."},{"issue":"3","key":"e_1_3_2_3_2","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1287\/opre.37.3.478","article-title":"Multidimensional stochastic ordering and associated random variables","volume":"37","author":"Baccelli Fran\u00e7ois","year":"1989","unstructured":"Fran\u00e7ois Baccelli and Armand M. Makowski. 1989. Multidimensional stochastic ordering and associated random variables. Operat. Res. 37, 3 (1989), 478\u2013487.","journal-title":"Operat. Res."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.75415"},{"key":"e_1_3_2_5_2","first-page":"124","volume-title":"Proceedings of the International Computer Performance and Dependability Symposium.","author":"Bobbio Andrea","year":"1995","unstructured":"Andrea Bobbio and Miklos Telek. 1995. Markov regenerative SPN with non-overlapping activity cycles. In Proceedings of the International Computer Performance and Dependability Symposium.124\u2013133."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3381453"},{"key":"e_1_3_2_7_2","doi-asserted-by":"crossref","unstructured":"Dario Bruneo Salvatore Distefano Francesco Longo and Marco Scarpa. 2012. Stochastic evaluation of QoS in service-based systems. IEEE Transactions on Parallel and Distributed Systems 24 10 (2012) 2090\u20132099.","DOI":"10.1109\/TPDS.2012.313"},{"key":"e_1_3_2_8_2","volume-title":"Introduction to Rare Event Simulation","author":"Bucklew James","year":"2013","unstructured":"James Bucklew. 2013. Introduction to Rare Event Simulation. Springer Science & Business Media."},{"key":"e_1_3_2_9_2","first-page":"463","volume-title":"Proceedings of the International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS\u201920)","author":"Budde Carlos E.","year":"2020","unstructured":"Carlos E. Budde, Marco Biagi, Ra\u00fal E. Monti, Pedro R. D\u2019Argenio, and Mari\u00eblle Stoelinga. 2020. Rare event simulation for non-markovian repairable fault trees. In Proceedings of the International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS\u201920). Springer, 463\u2013482."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICWS.2005.96"},{"key":"e_1_3_2_11_2","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/978-3-030-85172-9_5","volume-title":"Proceedings of the International Conference on Quantitative Evaluation of Systems (QEST\u201921)","volume":"12846","author":"Carnevali Laura","year":"2021","unstructured":"Laura Carnevali, Marco Paolieri, Riccardo Reali, and Enrico Vicario. 2021. Compositional safe approximation of response time distribution of complex workflows. In Proceedings of the International Conference on Quantitative Evaluation of Systems (QEST\u201921), Vol. 12846. Springer, 83\u2013104."},{"key":"e_1_3_2_12_2","volume-title":"Proceedings of the International Conference on Quantitative Evaluation of Systems (QEST\u201922)","author":"Carnevali Laura","year":"2022","unstructured":"Laura Carnevali, Riccardo Reali, and Enrico Vicario. 2022. Eulero: A tool for quantitative modeling and evaluation of complex workflows. In Proceedings of the International Conference on Quantitative Evaluation of Systems (QEST\u201922)."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3427921.3450250"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.297939"},{"key":"e_1_3_2_15_2","unstructured":"Tony Andrews Francisco Curbera Hitesh Dholakia Yaron Goland Johannes Klein Frank Leymann Kevin Liu Dieter Roller Doug Smith Satish Thatte Ivana Trickovic and Sanjiva Weerawarana. 2003. Business process execution language for web services. http:\/\/xml.coverpages.org\/BPELv11-May052003Final.pdf."},{"key":"e_1_3_2_16_2","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1016\/S0927-0507(03)11012-2","article-title":"Planning supply chain operations: Definition and comparison of planning concepts","volume":"11","author":"de Kok Ton G.","year":"2003","unstructured":"Ton G. de Kok and Jan C. Fransoo. 2003. Planning supply chain operations: Definition and comparison of planning concepts. In Handbooks in Operations Research and Management Science, Vol. 11. Elsevier, 597\u2013675.","journal-title":"Handbooks in Operations Research and Management Science"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-52148-8_17"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3375555.3383120"},{"issue":"7","key":"e_1_3_2_19_2","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.peva.2011.11.002","article-title":"Transient analysis of non-Markovian models using stochastic state classes","volume":"69","author":"Horv\u00e1th Andr\u00e1s","year":"2012","unstructured":"Andr\u00e1s Horv\u00e1th, Marco Paolieri, Lorenzo Ridi, and Enrico Vicario. 2012. Transient analysis of non-Markovian models using stochastic state classes. Perf. Eval. 69, 7-8 (2012), 315\u2013335.","journal-title":"Perf. Eval."},{"key":"e_1_3_2_20_2","first-page":"112","volume-title":"Proceedings of the IEEE Real-Time Systems Symposium (RTSS\u201985)","volume":"85","author":"Jensen E. Douglas","year":"1985","unstructured":"E. Douglas Jensen, C. Douglas Locke, and Hideyuki Tokuda. 1985. A time-driven scheduling model for real-time operating systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS\u201985), Vol. 85. 112\u2013122."},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1145\/178243.178258","volume-title":"ACM SIGPLAN\u201994 Conference on Programming Language Design and Implementation (PLDI\u201994)","author":"Johnson Richard","year":"1994","unstructured":"Richard Johnson, David Pearson, and Keshav Pingali. 1994. The program structure tree: Computing control regions in linear time. In ACM SIGPLAN\u201994 Conference on Programming Language Design and Implementation (PLDI\u201994). ACM, 171\u2013185."},{"key":"e_1_3_2_22_2","first-page":"119","volume-title":"European Workshop on Performance Engineering","author":"Koren\u010diak L\u2019ubo\u0161","year":"2014","unstructured":"L\u2019ubo\u0161 Koren\u010diak, Jan Kr\u010d\u00e1l, and Vojt\u011bch \u0158eh\u00e1k. 2014. Dealing with zero density using piecewise phase-type approximation. In European Workshop on Performance Engineering. Springer, 119\u2013134."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.61115"},{"key":"e_1_3_2_24_2","first-page":"699","volume-title":"Proceedings of the IEEE International Conference on Dependable, Autonomic and Secure Computing, International Conference on Pervasive Intelligence and Computing, International Conference on Cloud and Big Data Computing, and International Conference on Cyber Science and Technology Congress (DASC\u201919\/PiCom\u201919\/CBDCom\u201919\/CyberSciTech\u201919)","author":"Liu Yanjie","year":"2019","unstructured":"Yanjie Liu, Zheng Zheng, and Jiantao Zhang. 2019. Markov model of web services for their performance based on phase-type expansion. In Proceedings of the IEEE International Conference on Dependable, Autonomic and Secure Computing, International Conference on Pervasive Intelligence and Computing, International Conference on Cloud and Big Data Computing, and International Conference on Cyber Science and Technology Congress (DASC\u201919\/PiCom\u201919\/CBDCom\u201919\/CyberSciTech\u201919). IEEE, 699\u2013704."},{"key":"e_1_3_2_25_2","article-title":"On a generalization of the jensen-shannon divergence and the JS-symmetrization of distances relying on abstract means","author":"Nielsen Frank","year":"2019","unstructured":"Frank Nielsen. 2019. On a generalization of the jensen-shannon divergence and the JS-symmetrization of distances relying on abstract means. arXiv:1904.04017. Retrieved from https:\/\/arxiv.org\/abs\/1904.04017.","journal-title":"arXiv:1904.04017"},{"key":"e_1_3_2_26_2","doi-asserted-by":"crossref","unstructured":"Marco Paolieri Marco Biagi Laura Carnevali and Enrico Vicario. 2021. The ORIS tool: Quantitative evaluation of non-markovian systems. IEEE Trans. Softw. Eng. 47 6 (June2021) 1211\u20131225.","DOI":"10.1109\/TSE.2019.2917202"},{"key":"e_1_3_2_27_2","first-page":"200","volume-title":"Proceedings of the IEEE International Conference on Cloud Engineering (IC2E\u201919)","author":"Rahman Joy","year":"2019","unstructured":"Joy Rahman and Palden Lama. 2019. Predicting the end-to-end tail latency of containerized microservices in the cloud. In Proceedings of the IEEE International Conference on Cloud Engineering (IC2E\u201919). IEEE, 200\u2013210."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2015.04.004"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/1643623"},{"key":"e_1_3_2_30_2","first-page":"06","article-title":"Workflow Control-flow Patterns: A Revised View","author":"Russell Nick","year":"2006","unstructured":"Nick Russell, Arthur H. M. Ter Hofstede, Wil M. P. Van Der Aalst, and Nataliya Mulyar. 2006. Workflow Control-flow Patterns: A Revised View. BPM Center Report BPM-06-22, BPMcenter. Org (2006), 06\u201322.","journal-title":"BPM Center Report BPM-06-22, BPMcenter. Org"},{"key":"e_1_3_2_31_2","first-page":"59","volume-title":"Proceedings of the International Conference on Quantitative Evaluation of Systems","author":"Sassoli Luigi","year":"2007","unstructured":"Luigi Sassoli and Enrico Vicario. 2007. Close form derivation of state-density functions over DBM domains in the analysis of non-Markovian models. In Proceedings of the International Conference on Quantitative Evaluation of Systems. IEEE, 59\u201368."},{"key":"e_1_3_2_32_2","unstructured":"SIRIO Library. 2022. Retrieved from https:\/\/github.com\/oris-tool\/sirio."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/1530873.1530884"},{"issue":"01","key":"e_1_3_2_34_2","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1142\/S0218126698000043","article-title":"The application of Petri nets to workflow management","volume":"8","author":"Aalst Wil M. P. Van der","year":"1998","unstructured":"Wil M. P. Van der Aalst. 1998. The application of Petri nets to workflow management. J. Circ. Syst. Comput. 8, 01 (1998), 21\u201366.","journal-title":"J. Circ. Syst. Comput."},{"key":"e_1_3_2_35_2","first-page":"21","volume-title":"Companion of the ACM\/SPEC International Conference on Performance Engineering","author":"Eyk Erwin Van","year":"2018","unstructured":"Erwin Van Eyk, Alexandru Iosup, Cristina L. Abad, Johannes Grohmann, and Simon Eismann. 2018. A SPEC RG cloud group\u2019s vision on the performance challenges of FaaS cloud architectures. In Companion of the ACM\/SPEC International Conference on Performance Engineering. 21\u201324."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2009.02.015"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.940727"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2009.36"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02742-0_22"},{"key":"e_1_3_2_40_2","first-page":"210","volume-title":"IEEE International Symposium on Software Reliability Engineering","author":"Zhang Yilei","year":"2011","unstructured":"Yilei Zhang, Zibin Zheng, and Michael R. Lyu. 2011. WSPred: A time-aware personalized QoS prediction framework for web services. In IEEE International Symposium on Software Reliability Engineering. IEEE, 210\u2013219."},{"issue":"3","key":"e_1_3_2_41_2","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1109\/TSC.2015.2475957","article-title":"Semi-Markov models of composite web services for their performance, reliability and bottlenecks","volume":"10","author":"Zheng Zheng","year":"2015","unstructured":"Zheng Zheng, Kishor S. Trivedi, Kun Qiu, and Ruofan Xia. 2015. Semi-Markov models of composite web services for their performance, reliability and bottlenecks. IEEE Trans. Serv. Comput. 10, 3 (2015), 448\u2013460.","journal-title":"IEEE Trans. Serv. Comput."}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3591205","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3591205","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:46Z","timestamp":1750178866000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3591205"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,26]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1145\/3591205"],"URL":"https:\/\/doi.org\/10.1145\/3591205","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"value":"1049-3301","type":"print"},{"value":"1558-1195","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,26]]},"assertion":[{"value":"2022-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}