An Alternative View of Fairness in Petri Nets

ABSTRACT

In modelling and analysis of concurrent systems is usually placed the main emphasis on their accuracy and validity, i.e. the model meets the formal specification and also modelled the relevant facts. Moreover, in recent years in various fields, the importance of the concept of fairness starts to develop, which covers such requirements on system/model, such as uniformity of resource usage, fair queuing policy, the problem of starvation and many others. The aim of this work is to define a method of calculating the uniformity of the distribution of specific system states that can be used to investigate the uniformity of the workload of individual entities / elements of the system. The method is based on modelling by classical Place/Transition Petri nets and measuring the entropy of subsets of specific markings in the reachability graph of the Petri net. The presented method is an alternative view on the fairness of the already defined fairness which in the theory of Petri nets deals with transitions.

References

1. "Fairness" 2011. Oxford Advanced American Dictionary for learners of English
2. Apt, K., Francez, N., and Katz, S. 1988. Appraising fairness in languages for distributed programming. Distributed Computing 2, 4 (1988/12/01), 226--241. DOI= http://dx.doi.org/10.1007/bf01872848.
3. Avi-Itzhak, B., Levy, H., and Raz, D. 2008. Quantifying fairness in queuing systems: Principles, approaches, and applicability. Probab. Eng. Inf. Sci. 22, 4, 495--517. DOI= http://dx.doi.org/10.1017/s0269964808000302.
4. Baier, C. and Katoen, J.-P. 2008. Principles of model checking. The MIT Press, Cambridge, Mass.
5. Jaffe, J. 1981. Bottleneck Flow Control. Communications, IEEE Transactions on 29, 7, 954--962. DOI= http://dx.doi.org/10.1109/tcom.1981.1095081.
6. Jensen, K. 2009. Coloured Petri nets: modeling and validation of concurrent systems. Springer, New York.
7. Kelly, F. 1997. Charging and rate control for elastic traffic. European Transactions on Telecommunications 8, 1, 33--37. DOI= http://dx.doi.org/10.1002/ett.4460080106.
8. Marsan, M.A. 1990. Stochastic Petri nets: an elementary introduction. In Advances in Petri nets 1989, R. Grzegorz Ed. Springer-Verlag New York, Inc., 1--29.
9. Molloy, M.K. 1982. Performance Analysis Using Stochastic Petri Nets. Computers, IEEE Transactions on C-31, 9, 913--917. DOI= http://dx.doi.org/10.1109/tc.1982.1676110.
10. Petri, C.A. 1962. Kommunikation mit Automaten Bonn: Institut für Instrumentelle Mathematik, Schriften des IIM Nr. 2.
11. Raz, D., Levy, H., and Avi-Itzhak, B. 2004. A resource-allocation queueing fairness measure. SIGMETRICS Perform. Eval. Rev. 32, 1, 130--141. DOI= http://dx.doi.org/10.1145/1012888.1005704.
12. Völzer, H. and Varacca, D. 2012. Defining Fairness in Reactive and Concurrent Systems. Journal of the ACM 59, 3, 13--13:37. DOI= http://dx.doi.org/10.1145/2220357.2220360.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Metrics