Concurrency, σ-Alebras, and Probabilistic Fairness

摘要

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 S_0, contained in the Borel σ-algebra S of Ω. Equality S_0 = S holds when confusion is finite (formally, for the class of locally finite event structures), but inclusion So is contained in S is strict in general. We show the existence of an increasing chain S_0 is contained in S_1 is contained in S_2 is contained in ... of sub-σ-algebras of S 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 S in finitely many steps.rnThe construction of probabilities typically relies on a Kolmogorov extension argument. Such arguments can achieve the construction of probabilities on the σ-algebra S_0 only, while one is interested in probabilities defined on the entire Borel σ-algebra S. We prove that, when the event structure unfolds a 1-safe net, then unfair executions all belong to some set of S_0 of zero probability. Whence S_0=S modulo 0 always holds, whereas S_0≠ S in general. This yields a new construction of Markovian probabilistic nets, carrying a natural interpretation that "unfair executions possess zero probability".