Abstract
We extend previous constructions of probabilities for a prime event structure E by allowing arbitrary confusion. Our study builds on results related to fairness in event structures that are of interest per se.
Executions of E are captured by the set Ω of maximal configurations. We show that the information collected by observing only fair executions of E is confined in some σ-algebra \(\mathfrak{F}_0\), contained in the Borelσ-algebra \(\mathfrak{F}\) of Ω. Equality \(\mathfrak{F}_0=\mathfrak{F}\) holds when confusion is finite (formally, for the class of locally finite event structures), but inclusion \(\mathfrak{F}_0\subseteq\mathfrak{F}\) is strict in general. We show the existence of an increasing chain \(\mathfrak{F}_0\subseteq\mathfrak{F}_1\subseteq\mathfrak{F}_2\subseteq\dots\) of sub-σ-algebra s of \(\mathfrak{F}\) that capture the information collected when observing executions of increasing unfairness. We show that, if the event structure unfolds a 1-safe net, then unfairness remains quantitatively bounded, that is, the above chain reaches \(\mathfrak{F}\) in finitely many steps.
The construction of probabilities typically relies on a Kolmogorov extension argument. Such arguments can achieve the construction of probabilities on theσ-algebra \(\mathfrak{F}_0\) only, while one is interested in probabilities defined on the entire Borel σ-algebra \(\mathfrak{F}\). We prove that, when the event structure unfolds a 1-safe net, then unfair executions all belong to some set of \(\mathfrak{F}_0\) of zero probability. Whence \(\mathfrak{F}_0=\mathfrak{F}\) modulo 0 always holds, whereas \(\mathfrak{F}_0\neq\mathfrak{F}\) in general. This yields a new construction of Markovian probabilistic nets, carrying a natural interpretation that “unfair executions possess zero probability”.
Chapter PDF
Similar content being viewed by others
Keywords
References
Abbes, S.: A (true) concurrent Markov property and some applications to Markov nets. In: Ciardo, G., Darondeau, P. (eds.) ICATPN 2005. LNCS, vol. 3536, pp. 70–89. Springer, Heidelberg (2005)
Abbes, S.: A projective formalism applied to topological and probabilistic event structures. Mathematical Structures in Computer Science 17, 819–837 (2007)
Abbes, S., Benveniste, A.: Branching cells as local states for event structures and nets: Probabilistic applications. In: Sassone, V. (ed.) FOSSACS 2005. LNCS, vol. 3441, pp. 95–109. Springer, Heidelberg (2005); Extended version available as Research Report INRIA RR-5347
Abbes, S., Benveniste, A.: Probabilistic models for true-concurrency: branching cells and distributed probabilities for event structures. Information & Computation 204(2), 231–274 (2006)
Abbes, S., Benveniste, A.: Concurrency, σ-algebras and probabilistic fairness. Technical report, PPS/Université Paris 7 Denis Diderot (2008), http://hal.archives-ouvertes.fr/hal-00267518/en/
Abbes, S., Benveniste, A.: Probabilistic true-concurrency models: Markov nets and a Law of large numbers. Theoretical Computer Science 390, 129–170 (2008)
Baccelli, F., Gaujal, B.: Stationary regime and stability of free-choice Petri nets. Springer, Heidelberg (1994)
Breiman, L.: Probability. SIAM, Philadelphia (1968)
Buchholz, P.: Compositional analysis of a Markovian process algebra. In: Rettelbach, M., Herzog, U. (eds.) Proceedings of 2nd process algebra and performance modelling workshop. Arbeitsberichte des IMMD, vol. 27 (1994)
Danos, V., Desharnais, J., Panangaden, P.: Labelled Markov processes: stronger and faster approximations. ENTCS 87, 157–203 (2004)
Darondeau, P., Nolte, D., Priese, L., Yoccoz, S.: Fairness, distance and degrees. Theoretical Computer Science 97, 131–142 (1992)
de Alfaro, L.: From fairness to chance. Electronic Notes in Theoretical Computer Science 22, 55–87 (1999)
Desharnais, J., Gupta, V., Jagadeesan, R., Panangaden, P.: Approximating labeled Markov processes. Information and Computation 184(1), 160–200 (2003)
Götz, N., Herzog, U., Rettelbach, M.: Multiprocessor and distributed system design: the integration of functional specification and performance analysis using stochastic process algebras. In: Proceedings of Performance 1993 (1993)
Herescu, O.M., Palamidessi, C.: Probabilistic asynchronous π-calculus. In: Tiuryn, J. (ed.) FOSSACS 2000. LNCS, vol. 1784, pp. 146–160. Springer, Heidelberg (2000)
Hillston, J.: A compositional approach to performance modelling. Cambridge University Press, Cambridge (1996)
Jou, C., Smolka, S.: Equivalences, congruences and complete axiomatizations of probabilistic processes. In: Baeten, J.C.M., Klop, J.W. (eds.) CONCUR 1990. LNCS, vol. 458, pp. 367–383. Springer, Heidelberg (1990)
Larsen, K., Skou, A.: Bisimulation through probabilistic testing. Information and Computation 94(1), 1–28 (1991)
Park, D.: Concurrency and automata on infinite sequences. In: Theoretical Computer Science, pp. 167–183. Springer, Heidelberg (1981)
Varacca, D., Völzer, H., Winskel, G.: Probabilistic event structures and domains. Theoretical Computer Science 358(2), 173–199 (2006)
Wilkinson, D.: Stochastic modelling for systems biology. Chapman & Hamm/CRC, Boca Raton (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Abbes, S., Benveniste, A. (2009). Concurrency, σ-Algebras, and Probabilistic Fairness. In: de Alfaro, L. (eds) Foundations of Software Science and Computational Structures. FoSSaCS 2009. Lecture Notes in Computer Science, vol 5504. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00596-1_27
Download citation
DOI: https://doi.org/10.1007/978-3-642-00596-1_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00595-4
Online ISBN: 978-3-642-00596-1
eBook Packages: Computer ScienceComputer Science (R0)