Abstract
We extend the general matching graph model to deal with matching graph where every node has a self loop. Thus the states on the Markov chain are associated with the independent sets of the matching graph. We prove that under i.i.d. arrivals assumptions the steady-state distribution of the Markov chain has a product form solution.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Mairesse, J., Moyal, P.: Stability of the stochastic matching model. J. Appl. Probab. 53(4), 1064–1077 (2018)
Gelenbe, E.: Product-form queuing networks with negative and positive customers. J. Appl. Probab. 28, 656–663 (1991)
Fourneau, J.-M., Gelenbe, E., Suros, R.: G-networks with multiple classes of positive and negative customers. Theoret. Comput. Sci. 155, 141–156 (1996)
Dao-Thi, T.-H., Fourneau, J.-M., Tran, M.-A.: Network of queues with inert customers and signals. In: 7th International Conference on Performance Evaluation Methodologies and Tools, ValueTools 2013, Italy, pp. 155–164. ICST/ACM (2013)
Marsan, M.A., Balbo, G., Bobbio, A., Chiola, G., Conte, G., Cumani, A.: On Petri nets with stochastic timing. In: International Workshop on Timed Petri Nets, Torino, Italy, 1–3 July 1985, pp. 80–87. IEEE Computer Society (1985)
Lazar, A.A., Robertazzi, T.G.: Markovian Petri net protocols with product form solution. Perform. Eval. 12(1), 67–77 (1991)
Haddad, S., Moreaux, P., Sereno, M., Silva, M.: Product-form and stochastic Petri nets: a structural approach. Perform. Eval. 59, 313–336 (2005)
Moyal, P., Bušić, A., Mairesse, J.: A product form for the general stochastic matching model. J. Appl. Probab. 57(2), 449–468 (2021)
Cadas, A., Doncel, J., Fourneau, J.-M., Busic, A.: Flexibility can hurt dynamic matching system performance. ACM SIGMETRICS Perform. Eval. Rev. 49(3), 37–42 (2021). IFIP Performance Evaluation (Short Paper)
Bušić, A., Gupta, V., Mairesse, J.: Stability of the bipartite matching model. Adv. Appl. Probab. 45(2), 351–378 (2013)
Caldentey, R., Kaplan, E.H., Weiss, G.: FCFS infinite bipartite matching of servers and customers. Adv. Appl. Probab. 41(3), 695730 (2009)
United Network for Organ Sharing. https://unos.org/wp-content/uploads/unos/living_donation_kidneypaired.pdf
Unver, U.: Dynamic kidney exchange. Rev. Econ. Stud. 77(1), 372–414 (2010)
Ashlagi, I., Jaillet, P., Manshadi, V.H.: Kidney exchange in dynamic sparse heterogenous pools. In: Proceedings of the Fourteenth ACM Conference on Electronic Commerce, EC 2013, pp. 25–26. ACM, New York (2013)
Begeot, J., Marcovici, I., Moyal, P., Rahme, Y.: A general stochastic matching model on multigraphs (2020). arXiv preprint https://arxiv.org/abs/2011.05169
Fourneau, J.M., Mahjoub, Y.A.E., Quessette, F., Vekris, D.: XBorne 2016: a brief introduction. In: Czachórski, T., Gelenbe, E., Grochla, K., Lent, R. (eds.) ISCIS 2016. CCIS, vol. 659, pp. 134–141. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-47217-1_15
Cadas, A., Doncel, J., Fourneau, J.-M., Busic, A.: Flexibility can hurt dynamic matching system performance, extended version on arXiv (2020)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Busic, A., Cadas, A., Doncel, J., Fourneau, JM. (2023). Product Form Solution for the Steady-State Distribution of a Markov Chain Associated with a General Matching Model with Self-loops. In: Gilly, K., Thomas, N. (eds) Computer Performance Engineering. EPEW 2022. Lecture Notes in Computer Science, vol 13659. Springer, Cham. https://doi.org/10.1007/978-3-031-25049-1_5
Download citation
DOI: https://doi.org/10.1007/978-3-031-25049-1_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-25048-4
Online ISBN: 978-3-031-25049-1
eBook Packages: Computer ScienceComputer Science (R0)