{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:02:01Z","timestamp":1750309321566,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,3,18]],"date-time":"2024-03-18T00:00:00Z","timestamp":1710720000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"PRIN 2020 \u201cNirvana - Noninterference and Reversibility Analysis in Private Blockchains\u201d","award":["20202FCJMH"],"award-info":[{"award-number":["20202FCJMH"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Perform. Eval. Comput. Syst."],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>In queueing networks, product-form solutions are of fundamental importance to efficiently compute performance metrics in complex models of computer systems. The product-form property entails that the steady-state probabilities of the joint stochastic process underlying the network can be expressed as the normalized product of functions that only depend on the local state of the components. In many relevant cases, product-forms are the only way to perform exact quantitative analyses of large systems.<\/jats:p>\n          <jats:p>In this work, we introduce a novel class of product-form queueing networks where servers are always busy. Applications include model of systems where successive refinements on jobs improve the processes quality but are not strictly required to obtain a result. To this aim, we define a job movement policy that admits instantaneous migrations of jobs from non-empty waiting buffers to empty ones. Thus, the resulting routing scheme is state-dependent. This class of networks maximizes the system throughput.<\/jats:p>\n          <jats:p>This model can be implemented with arbitrary topology, including feedback, and both in an open and closed setting. As far as closed systems are concerned, we give a convolution algorithm and the corresponding mean value analysis to compute expected performance indices for closed models.<\/jats:p>","DOI":"10.1145\/3643845","type":"journal-article","created":{"date-parts":[[2024,2,3]],"date-time":"2024-02-03T11:45:21Z","timestamp":1706960721000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A Product-form Network for Systems with Job Stealing Policies"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7361-819X","authenticated-orcid":false,"given":"Diletta","family":"Olliaro","sequence":"first","affiliation":[{"name":"DAIS, Universit\u00e0 Ca\u2019 Foscari di Venezia, Mestre Venezia, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4548-7951","authenticated-orcid":false,"given":"Giuliano","family":"Casale","sequence":"additional","affiliation":[{"name":"Department of Computing, Imperial College London, London, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5958-1204","authenticated-orcid":false,"given":"Andrea","family":"Marin","sequence":"additional","affiliation":[{"name":"DAIS, Universit\u00e0 Ca\u2019 Foscari di Venezia, Mestre Venezia, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1189-4439","authenticated-orcid":false,"given":"Sabina","family":"Rossi","sequence":"additional","affiliation":[{"name":"DAIS, Universit\u00e0 Ca\u2019 Foscari di Venezia, Mestre Venezia, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,3,18]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/1811099.1811043","article-title":"A unifying approach to product-forms in networks with finite capacity constraints","volume":"38","author":"Balsamo S.","year":"2010","unstructured":"S. Balsamo, P. G. Harrison, and A. Marin. 2010. A unifying approach to product-forms in networks with finite capacity constraints. ACM SIGMETRICS Performance Evaluation Review 38, 1 (2010), 25\u201336.","journal-title":"ACM SIGMETRICS Performance Evaluation Review"},{"issue":"9","key":"e_1_3_2_3_2","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1145\/362342.362345","article-title":"Computational algorithms for closed queueing networks with exponential servers","volume":"16","author":"Buzen J. P.","year":"1973","unstructured":"J. P. Buzen. 1973. Computational algorithms for closed queueing networks with exponential servers. Communications of the ACM 16, 9 (1973), 527\u2013531.","journal-title":"Communications of the ACM"},{"doi-asserted-by":"publisher","key":"e_1_3_2_4_2","DOI":"10.1093\/comjnl\/bxr094"},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/1811039.1811042","volume-title":"Proceedings of the SIGMETRICS 2010, International Conference on Measurement and Modeling of Computer Systems","author":"Gast N.","year":"2010","unstructured":"N. Gast and B. Gaujal. 2010. A mean field model of work stealing in large-scale systems. In Proceedings of the SIGMETRICS 2010, International Conference on Measurement and Modeling of Computer Systems. Association for Computer Machinery, New York, NY, USA, 13\u201324."},{"issue":"1","key":"e_1_3_2_6_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2307\/3215230","article-title":"Replacement of train wheels: An application of dynamic reversal of a Markov process","volume":"31","author":"Gates D.","year":"1994","unstructured":"D. Gates and M. Westcott. 1994. Replacement of train wheels: An application of dynamic reversal of a Markov process. Journal of Applied Probability 31, 1 (1994), 1\u20138.","journal-title":"Journal of Applied Probability"},{"key":"e_1_3_2_7_2","doi-asserted-by":"crossref","first-page":"656","DOI":"10.2307\/3214499","article-title":"Product-form queueing networks with negative and positive customers","volume":"28","author":"Gelenbe E.","year":"1991","unstructured":"E. Gelenbe. 1991. Product-form queueing networks with negative and positive customers. Journal of Applied Probability 28, 3 (1991), 656\u2013663.","journal-title":"Journal of Applied Probability"},{"issue":"3","key":"e_1_3_2_8_2","doi-asserted-by":"crossref","first-page":"742","DOI":"10.2307\/3214781","article-title":"G-network with triggered customer movement","volume":"30","author":"Gelenbe E.","year":"1993","unstructured":"E. Gelenbe. 1993. G-network with triggered customer movement. Journal of Applied Probability 30, 3 (1993), 742\u2013748.","journal-title":"Journal of Applied Probability"},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139226424","volume-title":"Performance Modeling and Design of Computer Systems: Queueing Theory in Action","author":"Harchol-Balter M.","year":"2013","unstructured":"M. Harchol-Balter. 2013. Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge Press, USA."},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/j.peva.2004.02.002","article-title":"Compositional reversed Markov processes, with applications to G-networks","volume":"57","author":"Harrison P. G.","year":"2004","unstructured":"P. G. Harrison. 2004. Compositional reversed Markov processes, with applications to G-networks. Performance Evaluation 57, 3 (2004), 379\u2013408.","journal-title":"Performance Evaluation"},{"issue":"3","key":"e_1_3_2_11_2","doi-asserted-by":"crossref","first-page":"1947","DOI":"10.1016\/S0304-3975(02)00375-4","article-title":"Turning back time in Markovian process algebra","volume":"290","author":"Harrison P. G.","year":"2003","unstructured":"P. G. Harrison. 2003. Turning back time in Markovian process algebra. Theoretical Computer Science 290, 3 (2003), 1947\u20131986.","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_2_12_2","first-page":"107","article-title":"Deriving the rate equations characterising product-form models and application to propagating synchronisations","volume":"6","author":"Harrison P. G.","year":"2012","unstructured":"P. G. Harrison and A. Marin. 2012. Deriving the rate equations characterising product-form models and application to propagating synchronisations. In Proceedings of the 6th International ICST Conference on Performance Evaluation Methodologies and Tools 6 (2012), 107\u2013116.","journal-title":"In Proceedings of the 6th International ICST Conference on Performance Evaluation Methodologies and Tools"},{"issue":"11","key":"e_1_3_2_13_2","doi-asserted-by":"crossref","first-page":"1693","DOI":"10.1093\/comjnl\/bxt103","article-title":"Product-forms in multi-way synchronizations","volume":"57","author":"Harrison P. G.","year":"2014","unstructured":"P. G. Harrison and A. Marin. 2014. Product-forms in multi-way synchronizations. The Computer Journal 57, 11 (2014), 1693\u20131710.","journal-title":"The Computer Journal"},{"key":"e_1_3_2_14_2","volume-title":"A Compositional Approach to Performance Modelling","author":"Hillston J.","year":"2005","unstructured":"J. Hillston. 2005. A Compositional Approach to Performance Modelling. Cambridge University Press, USA."},{"key":"e_1_3_2_15_2","volume-title":"Reversibility and Stochastic Networks","author":"Kelly F. P.","year":"1979","unstructured":"F. P. Kelly. 1979. Reversibility and Stochastic Networks. John Wiley & Sons, Cambridge Mathematical Library."},{"key":"e_1_3_2_16_2","series-title":"Proceedings of the fo Quantitative Evaluation of Systems QEST","first-page":"329","volume":"12846","author":"Kielanski G.","year":"2021","unstructured":"G. Kielanski and B. Van Houdt. 2021. Performance analysis of work stealing strategies in large scale multi-threaded computing. In Proceedings of the fo Quantitative Evaluation of Systems QESTLecture Notes in Computer Science, Vol. 12846. Association for Computing Machinery, New York, NY, USA, 329\u2013348."},{"key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1017\/S0269964816000048","article-title":"Product-form in G-Networks","volume":"30","author":"Marin A.","year":"2016","unstructured":"A. Marin. 2016. Product-form in G-Networks. Probability in Engineering and Informational Sciences 30, 3 (2016), 345\u2013360.","journal-title":"Probability in Engineering and Informational Sciences"},{"doi-asserted-by":"publisher","key":"e_1_3_2_18_2","DOI":"10.1016\/j.peva.2017.06.004"},{"key":"e_1_3_2_19_2","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1145\/1712605.1712632","volume-title":"Proceedings of the 1st joint WOSP\/SIPEW International Conference on Performance Engineering","author":"Marin A.","year":"2010","unstructured":"A. Marin and M. G. Vigliotti. 2010. A general result for deriving product-form solutions in markovian models. In Proceedings of the 1st joint WOSP\/SIPEW International Conference on Performance Engineering. ACM, New York, NY, USA, 165\u2013176."},{"issue":"7","key":"e_1_3_2_20_2","doi-asserted-by":"crossref","first-page":"2299","DOI":"10.1109\/TC.2015.2479598","article-title":"Truthful mechanisms for competitive reward-based scheduling","volume":"65","author":"Mashayekhy Lena","year":"2016","unstructured":"Lena Mashayekhy, Nathan Fisher, and Daniel Grosu. 2016. Truthful mechanisms for competitive reward-based scheduling. IEEE Transactions on computers 65, 7 (2016), 2299\u20132312.","journal-title":"IEEE Transactions on computers"},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1007\/978-3-031-43835-6_8","volume-title":"Proceedings of the Quantitative Evaluation of Systems: 20th International Conference","author":"Olliaro Diletta","year":"2023","unstructured":"Diletta Olliaro, Gianfranco Balbo, Andrea Marin, and Matteo Sereno. 2023. Skipping and fetching: Insights on non-conventional product-form solutions. In Proceedings of the Quantitative Evaluation of Systems: 20th International Conference . Springer-Verlag, Berlin, Heidelberg, 110\u2013126."},{"issue":"20","key":"e_1_3_2_22_2","doi-asserted-by":"crossref","first-page":"6174","DOI":"10.1080\/00207543.2015.1082669","article-title":"Models for integrated production-inventory systems: Steady state and cost analysis","volume":"54","author":"Otten S.","year":"2015","unstructured":"S. Otten, R. Krenzler, and H. Daduna. 2015. Models for integrated production-inventory systems: Steady state and cost analysis. International Journal of Production Research 54, 20 (2015), 6174\u20136191.","journal-title":"International Journal of Production Research"},{"issue":"4","key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1287\/moor.4.4.357","article-title":"Closed exponential networks of queues with saturation: The Jackson-Type stationary distribution and its asymptotic analysis","volume":"4","author":"Pittel B. G.","year":"1979","unstructured":"B. G. Pittel. 1979. Closed exponential networks of queues with saturation: The Jackson-Type stationary distribution and its asymptotic analysis. Mathematics of Operations Research 4, 4 (1979), 357\u2013378.","journal-title":"Mathematics of Operations Research"},{"issue":"2","key":"e_1_3_2_24_2","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1145\/322186.322195","article-title":"Mean-value analysis of closed multichain queuing networks","volume":"27","author":"Reiser M.","year":"1980","unstructured":"M. Reiser and S. S. Lavenberg. 1980. Mean-value analysis of closed multichain queuing networks. Journal of the ACM 27, 2 (1980), 313\u2013322.","journal-title":"Journal of the ACM"},{"issue":"2","key":"e_1_3_2_25_2","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1145\/322248.322257","article-title":"The distribution of queuing network states at input and output instants","volume":"28","author":"Sevcik K. C.","year":"1981","unstructured":"K. C. Sevcik and I. Mitrani. 1981. The distribution of queuing network states at input and output instants. Journal of the ACM 28, 2 (1981), 358\u2013371.","journal-title":"Journal of the ACM"},{"issue":"2","key":"e_1_3_2_26_2","doi-asserted-by":"crossref","first-page":"6:1\u20136:28","DOI":"10.1145\/3470887","article-title":"Performance analysis of work stealing in large-scale multithreaded computing","volume":"6","author":"Sonenberg N.","year":"2021","unstructured":"N. Sonenberg, G. Kielanski, and B. Van Houdt. 2021. Performance analysis of work stealing in large-scale multithreaded computing. ACM Transactions on Modeling and Performance Evaluation of Computing Systems 6, 2 (2021), 6:1\u20136:28.","journal-title":"ACM Transactions on Modeling and Performance Evaluation of Computing Systems"},{"doi-asserted-by":"publisher","key":"e_1_3_2_27_2","DOI":"10.1016\/j.ejor.2018.10.048"},{"issue":"3","key":"e_1_3_2_28_2","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1016\/j.ejor.2018.10.048","article-title":"Integrated storage-order picking systems: Technology, performance models, and design insights","volume":"274","author":"Tappia E.","year":"2018","unstructured":"E. Tappia, D. Roy, M. Melacini, and R. De Koster. 2018. Integrated storage-order picking systems: Technology, performance models, and design insights. European Journal of Operational Research 274, 3 (2018), 947\u2013965.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"e_1_3_2_29_2","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1287\/opre.2019.1885","article-title":"Capacity analysis of sequential zone picking systems","volume":"68","author":"Gaast J. P. Van der","year":"2019","unstructured":"J. P. Van der Gaast, R. B. M. de Koster, I. J. B. F. Adan, and J. A. C. Resing. 2019. Capacity analysis of sequential zone picking systems. Operations Research 68, 1 (2019), 161\u2013179.","journal-title":"Operations Research"},{"key":"e_1_3_2_30_2","first-page":"30","volume-title":"Proceedings of the 1990 Mathematics-in-Industry Study Group","author":"Westcott M.","year":"1990","unstructured":"M. Westcott. 1990. Modelling and analysis of wheel replacement and restoration. In Proceedings of the 1990 Mathematics-in-Industry Study Group, N. G. Barton (Ed.). CSIRO Division of Mathematics and Statistics, Clayton, Australia, 30\u201340."}],"container-title":["ACM Transactions on Modeling and Performance Evaluation of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3643845","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3643845","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:58Z","timestamp":1750291438000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3643845"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,18]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3643845"],"URL":"https:\/\/doi.org\/10.1145\/3643845","relation":{},"ISSN":["2376-3639","2376-3647"],"issn-type":[{"type":"print","value":"2376-3639"},{"type":"electronic","value":"2376-3647"}],"subject":[],"published":{"date-parts":[[2024,3,18]]},"assertion":[{"value":"2023-02-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-11","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}