{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T12:13:09Z","timestamp":1782735189220,"version":"3.54.5"},"reference-count":56,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2024,4,15]],"date-time":"2024-04-15T00:00:00Z","timestamp":1713139200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Project PRIN 2020 \u201cNirvana\u2014Noninterference and Reversibility Analysis in Private Blockchains\u201d","award":["20202FCJMH"],"award-info":[{"award-number":["20202FCJMH"]}]},{"name":"Project PRIN 2020 \u201cNirvana\u2014Noninterference and Reversibility Analysis in Private Blockchains\u201d","award":["PE00000014"],"award-info":[{"award-number":["PE00000014"]}]},{"name":"Project PRIN 2020 \u201cNirvana\u2014Noninterference and Reversibility Analysis in Private Blockchains\u201d","award":["CUP E53C23001670001"],"award-info":[{"award-number":["CUP E53C23001670001"]}]},{"name":"SERICS","award":["20202FCJMH"],"award-info":[{"award-number":["20202FCJMH"]}]},{"name":"SERICS","award":["PE00000014"],"award-info":[{"award-number":["PE00000014"]}]},{"name":"SERICS","award":["CUP E53C23001670001"],"award-info":[{"award-number":["CUP E53C23001670001"]}]},{"name":"European Union\u2014NextGenerationEU","award":["20202FCJMH"],"award-info":[{"award-number":["20202FCJMH"]}]},{"name":"European Union\u2014NextGenerationEU","award":["PE00000014"],"award-info":[{"award-number":["PE00000014"]}]},{"name":"European Union\u2014NextGenerationEU","award":["CUP E53C23001670001"],"award-info":[{"award-number":["CUP E53C23001670001"]}]},{"name":"GNCS INdAM project 2024 \u201cStrutture di matrici e di funzioni per la sintesi di circuiti quantistici efficienti\u201d","award":["20202FCJMH"],"award-info":[{"award-number":["20202FCJMH"]}]},{"name":"GNCS INdAM project 2024 \u201cStrutture di matrici e di funzioni per la sintesi di circuiti quantistici efficienti\u201d","award":["PE00000014"],"award-info":[{"award-number":["PE00000014"]}]},{"name":"GNCS INdAM project 2024 \u201cStrutture di matrici e di funzioni per la sintesi di circuiti quantistici efficienti\u201d","award":["CUP E53C23001670001"],"award-info":[{"award-number":["CUP E53C23001670001"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This paper explores the concept of proportional lumpability as an extension of the original definition of lumpability, addressing the challenges posed by the state space explosion problem in computing performance indices for large stochastic models. Lumpability traditionally relies on state aggregation techniques and is applicable to Markov chains demonstrating structural regularity. Proportional lumpability extends this idea, proposing that the transition rates of a Markov chain can be modified by certain factors, resulting in a lumpable new Markov chain. This concept facilitates the derivation of precise performance indices for the original process. This paper establishes the well-defined nature of the problem of computing the coarsest proportional lumpability that refines a given initial partition, ensuring a unique solution exists. Additionally, a polynomial time algorithm is introduced to solve this problem, offering valuable insights into both the concept of proportional lumpability and the broader realm of partition refinement techniques. The effectiveness of proportional lumpability is demonstrated through a case study that consists of designing a model to investigate selfish mining behaviors on public blockchains. This research contributes to a better understanding of efficient approaches for handling large stochastic models and highlights the practical applicability of proportional lumpability in deriving exact performance indices.<\/jats:p>","DOI":"10.3390\/a17040159","type":"journal-article","created":{"date-parts":[[2024,4,15]],"date-time":"2024-04-15T08:08:12Z","timestamp":1713168492000},"page":"159","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Efficient Algorithm for Proportional Lumpability and Its Application to Selfish Mining in Public Blockchains"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2072-1628","authenticated-orcid":false,"given":"Carla","family":"Piazza","sequence":"first","affiliation":[{"name":"Dipartimento di Scienze Matematiche, Informatiche e Fisiche, Universit\u00e0 degli Studi di Udine, Via delle Scienze, 206, 33100 Udine, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1189-4439","authenticated-orcid":false,"given":"Sabina","family":"Rossi","sequence":"additional","affiliation":[{"name":"Dipartimento di Scienze Ambientali, Informatica e Statistica, Universit\u00e0 Ca\u2019 Foscari Venezia, Via Torino, 155, 30123 Venezia, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5893-8259","authenticated-orcid":false,"given":"Daria","family":"Smuseva","sequence":"additional","affiliation":[{"name":"Dipartimento di Scienze Matematiche, Informatiche e Fisiche, Universit\u00e0 degli Studi di Udine, Via delle Scienze, 206, 33100 Udine, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2024,4,15]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"913","DOI":"10.1109\/TC.1982.1676110","article-title":"Performance Analysis Using Stochastic Petri Nets","volume":"31","author":"Molloy","year":"1982","journal-title":"IEEE Trans. Comput."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0022-0000(81)90067-2","article-title":"Petri nets and regular languages","volume":"23","author":"Valk","year":"1981","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1145\/317786.317819","article-title":"On the stochastic structure of parallelism and synchronization models for distributed algorithms","volume":"13","author":"Plateau","year":"1985","journal-title":"Sigmetrics Perf. Eval. Rev."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Fourneau, J.M., Plateau, B., and Stewart, W.J. (2007, January 22\u201327). Product form for stochastic automata networks. Proceedings of the ValueTools 2007 Conference, ICST, Brussels, Belgium.","DOI":"10.4108\/valuetools.2007.1980"},{"key":"ref_5","unstructured":"Balsamo, S., and Marin, A. (2007). LNCS, Springer. Chapter 2."},{"key":"ref_6","unstructured":"Lazowska, E.D., Zahorjan, J.L., Graham, G.S., and Sevcick, K.C. (1984). Quantitative System Performance: Computer System Analysis Using Queueing Network Models, Prentice Hall."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Hermanns, H. (2002). Interactive Markov Chains, Springer.","DOI":"10.1007\/3-540-45804-2"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Hillston, J. (1996). A Compositional Approach to Performance Modelling, Cambridge University Press.","DOI":"10.1017\/CBO9780511569951"},{"key":"ref_9","unstructured":"Schweitzer, P. (1983, January 26\u201330). Aggregation Methods for Large Markov Chains. Proceedings of the International Workshop on Computer Performance and Reliability, Pisa, Italy."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1145\/322374.322377","article-title":"Computable error bounds for aggregated Markov chains","volume":"30","author":"Stewart","year":"1983","journal-title":"J. ACM"},{"key":"ref_11","unstructured":"Kemeny, J.G., and Snell, J.L. (1976). Finite Markov Chains, Springer."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Baarir, S., Dutheillet, C., Haddad, S., and Ili\u00e8, J.M. (2005, January 19\u201322). On the use of exact lumping in partially symmetrical Well-formed Petri Nets. Proceedings of the International Conference on the Quantitative Evaluaiton of Systems (QEST\u201905), Torino, Italy.","DOI":"10.1109\/QEST.2005.26"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"59","DOI":"10.2307\/3215235","article-title":"Exact and Ordinary lumpability in finite Markov chains","volume":"31","author":"Buchholz","year":"1994","journal-title":"J. Appl. Probab."},{"key":"ref_14","unstructured":"Kant, K. (1992). Introduction to Computer System Performance Evaluation, McGraw-Hill."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0166-5316(94)90015-9","article-title":"Bounds for quasi-lumpable Markov chains","volume":"20","author":"Franceschinis","year":"1994","journal-title":"Perform. Eval."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"926","DOI":"10.1109\/JSAC.1986.1146398","article-title":"Computable Bounds for Conditional Steady-State Probabilities in Large Markov Chains and Queueing Models","volume":"4","author":"Courtois","year":"1986","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1109\/32.297940","article-title":"Computing Bounds for the Performance Indices of Quasi-Lumpable Stochastic Well-Formed Nets","volume":"20","author":"Franceschinis","year":"1994","journal-title":"IEEE Trans. Softw. Eng."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Baarir, S., Beccuti, M., Dutheillet, C., and Franceschinis, G. (2009, January 20\u201322). From partially to fully lumped Markov chains in stochastic well formed Petri nets. Proceedings of the Valuetools 2009 Conference, Pisa, Italy.","DOI":"10.4108\/ICST.VALUETOOLS2009.7733"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/j.peva.2015.09.004","article-title":"Component aggregation for PEPA models: An approach based on approximate strong equivalence","volume":"94","author":"Milios","year":"2015","journal-title":"Perform. Eval."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Marin, A., Piazza, C., and Rossi, S. (2019, January 27\u201329). Proportional Lumpability. Proceedings of the International Conference on Formal Modeling and Analysis of Timed Systems, FORMATS, Amsterdam, The Netherlands.","DOI":"10.1007\/978-3-030-29662-9_16"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/s00236-021-00404-y","article-title":"Proportional Lumpability and Proportional Bisimilarity","volume":"59","author":"Marin","year":"2021","journal-title":"Acta Inform."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0167-6377(93)90006-3","article-title":"A necessary condition for weak lumpability in finite Markov processes","volume":"13","author":"Ledoux","year":"1993","journal-title":"Oper. Res. Lett."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1021\/i160029a020","article-title":"Lumping analysis in monomolecular reaction systems. analysis of approximately lumpable system","volume":"8","author":"Kuo","year":"1969","journal-title":"Ind. Eng. Chem. Fundam."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1413","DOI":"10.1016\/0009-2509(89)85014-6","article-title":"A general analysis of exact lumping in chemical kinetics","volume":"44","author":"Li","year":"1989","journal-title":"Chem. Eng. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1007\/978-3-030-85172-9_20","article-title":"Reasoning about Proportional Lumpability","volume":"Volume 12846","author":"Piazza","year":"2021","journal-title":"Proceedings of the Quantitative Evaluation of Systems"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Smuseva, D., Marin, A., and Rossi, S. (2023, January 6\u20137). Selfish Mining in Public Blockchains: A Quantitative Analysis. Proceedings of the EAI International Conference on Performance Evaluation Methodologies and Tools, Crete, Greece.","DOI":"10.1007\/978-3-031-48885-6_2"},{"key":"ref_27","unstructured":"Ross, S.M. (1996). Stochastic Processes, John Wiley & Sons. [2nd ed.]."},{"key":"ref_28","unstructured":"Taylor, H.M., and Karlin, S. (1998). An Introduction to Stochastic Modeling, Academic Press. Chapter IX."},{"key":"ref_29","first-page":"296","article-title":"A robust spectral method for finding lumpings and meta stable states of non-reversible Markov chains","volume":"37","author":"Jacobi","year":"2010","journal-title":"Elect. Trans. Numer. Anal."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/S0020-0190(03)00343-0","article-title":"Optimal state-space lumping in Markov chains","volume":"87","author":"Derisavi","year":"2003","journal-title":"Elsevier Inf. Process. Lett."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/j.peva.2010.09.002","article-title":"Lumping partially symmetrical stochastic models","volume":"68","author":"Baarir","year":"2011","journal-title":"Perform. Eval."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1080\/15326348908807099","article-title":"Lumpability and time-reversibility in the aggregation-disaggregation method for large Markov chains","volume":"5","author":"Sumita","year":"1989","journal-title":"Commun. Stat. Stoch. Models"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1021\/i160029a019","article-title":"Lumping analysis in monomolecular reaction systems. Analysis of the exactly lumpable system","volume":"8","author":"Wei","year":"1969","journal-title":"Ind. Eng. Chem. Fundam."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1531","DOI":"10.1137\/S0036139995293294","article-title":"The effect of lumping and expanding on kinetic differential equations","volume":"57","author":"Tomlin","year":"1997","journal-title":"SIAM J. Appl. Math."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/S0377-2217(98)00032-0","article-title":"Jointly optimal allocation of a repairman and optimal control of service rate for machine repairman problem","volume":"116","author":"Frostig","year":"1999","journal-title":"Eur. J. Oper. Res."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0166-5316(99)00081-4","article-title":"On the convergence of the power series algorithm","volume":"42","author":"Hooghiemstra","year":"2000","journal-title":"Perform. Eval."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1287\/moor.9.4.615","article-title":"Optimal Repair Allocation in a Series System","volume":"9","author":"Katehakis","year":"1984","journal-title":"Math. Oper. Res."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1017\/S0269964812000150","article-title":"A successive lumping procedure for a class of markov chains","volume":"26","author":"Katehakis","year":"2012","journal-title":"Probab. Eng. Informational Sci."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/s10586-006-4897-9","article-title":"Deferred Assignment Scheduling in Cluster-Based Servers","volume":"9","author":"Ungureanu","year":"2006","journal-title":"Clust. Comput."},{"key":"ref_40","first-page":"38","article-title":"Simple O(m logn) Time Markov Chain Lumping","volume":"Volume 6015","author":"Valmari","year":"2010","journal-title":"Proceedings of the International Conference on TACAS"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Groote, J.F., Rivera Verduzco, J., and De Vink, E.P. (2018). An Efficient Algorithm to Determine Probabilistic Bisimulation. Algorithms, 11.","DOI":"10.3390\/a11090131"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3233\/FI-2021-2049","article-title":"Persistent stochastic non-interference","volume":"181","author":"Hillston","year":"2021","journal-title":"Fundam. Informaticae"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1145\/1530873.1530880","article-title":"The PEPA Eclipse Plug-in","volume":"36","author":"Tribastone","year":"2009","journal-title":"Perf. Eval. Rev."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Carlsten, M., Kalodner, H., Weinberg, S.M., and Narayanan, A. (2016, January 24\u201328). On the instability of bitcoin without the block reward. Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria.","DOI":"10.1145\/2976749.2978408"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1145\/3212998","article-title":"Majority is not enough: Bitcoin mining is vulnerable","volume":"61","author":"Eyal","year":"2018","journal-title":"Commun. ACM"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.peva.2016.07.001","article-title":"Bitcoin blockchain dynamics: The selfish-mine strategy in the presence of propagation delay","volume":"104","author":"Keeler","year":"2016","journal-title":"Perform. Eval."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Wright, C.S. (2018). The Fallacy of the Selfish Miner in Bitcoin: An Economic Critique. Soc. Sci. Res. Netw.","DOI":"10.2139\/ssrn.3151923"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"724","DOI":"10.1109\/TNSE.2021.3050034","article-title":"The Impact of Selfish Mining on Bitcoin Network Performance","volume":"8","author":"Motlagh","year":"2021","journal-title":"IEEE Trans. Netw. Sci. Eng."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1145\/79147.214074","article-title":"Approximate mean value analysis algorithms for queuing networks: Existence, uniqueness, and convergence results","volume":"37","author":"Pattipati","year":"1990","journal-title":"J. ACM"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1147\/rd.191.0043","article-title":"Approximate Analysis of General Queueing Networks","volume":"19","author":"Chandy","year":"1975","journal-title":"IBM J. Res. Dev."},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Miner, A.S., Ciardo, G., and Donatelli, S. (2000, January 18\u201321). Using the exact state space of a Markov model to compute approximate stationary measures. Proceedings of the 2000 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, New York, NY, USA.","DOI":"10.1145\/339331.339417"},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1109\/32.922715","article-title":"An Efficient Algorithm for Aggregating PEPA Models","volume":"27","author":"Gilmore","year":"2001","journal-title":"IEEE Trans. Softw. Eng."},{"key":"ref_53","doi-asserted-by":"crossref","unstructured":"Casagrande, A., Dreossi, T., and Piazza, C. (2012, January 3). Hybrid Automata and \u03f5-Analysis on a Neural Oscillator. Proceedings of the Proceedings First International Workshop on Hybrid Systems and Biology, HSB, Newcastle Upon Tyne, UK.","DOI":"10.4204\/EPTCS.92.5"},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1049\/ip-cdt:20030282","article-title":"Approximate solution of PEPA models using component substitution","volume":"Volume 150","author":"Thomas","year":"2023","journal-title":"Proceedings of the IEE Proceedings\u2014Computers and Digital Technique"},{"key":"ref_55","unstructured":"Thomas, N. (2002). Proceedings of the First Workshop on Process Algebra with Stochastic Timed Activities (PASTA\u201902), Edinburgh, UK, 2002, Newcastle University Library."},{"key":"ref_56","unstructured":"Gribaudo, M., and Sereno, M. (2000, January 20\u201321). Approximation Technique of Finite Capacity Queuing Networks Exploiting Petri Net Analysis. Proceedings of the Fourth International Workshop on Queuing Networks with Finite Capacity (QNETs 2000), lkley, UK."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/4\/159\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:28:05Z","timestamp":1760106485000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/4\/159"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,15]]},"references-count":56,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2024,4]]}},"alternative-id":["a17040159"],"URL":"https:\/\/doi.org\/10.3390\/a17040159","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,15]]}}}