Concurrency, sigma-algebras, and probabilistic fairness

Samy Abbes 1 Albert Benveniste 2
2 DISTRIBCOM - Distributed and Iterative Algorithms for the Management of Telecommunications Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : We extend previous constructions of probabilities for a prime event structure by allowing arbitrary confusion. Our study builds on results related to fairness in event structures that are of interest per se. Executions are captured by the set of maximal configurations. We show that the information collected by observing only fair executions is confined in some sigma-algebra contained in the Borel sigma-algebra. Equality holds when confusion is finite, but inclusion is strict in general. We show the existence of an increasing chain of sub-sigma-algebras that capture the information collected when observing executions of increasing unfairness. We show that, if the event structure unfolds a safe net, then unfairness remains quantitatively bounded, that is, the above chain gets steady in finitely many steps. The construction of probabilities typically relies on a Kolmogorov extension argument. We prove that, when the event structure unfolds a safe net, then unfair executions all belong to some set of zero probability. This yields a new construction of Markovian probabilistic nets, carrying a natural interpretation that ``unfair executions possess zero probability''.
Type de document :
Rapport
[Research Report] RR-6724, INRIA. 2008, pp.24
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00338784
Contributeur : Albert Benveniste <>
Soumis le : vendredi 14 novembre 2008 - 13:39:48
Dernière modification le : vendredi 16 novembre 2018 - 01:32:07
Document(s) archivé(s) le : lundi 7 juin 2010 - 22:57:34

Fichier

RR-6724.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00338784, version 1

Citation

Samy Abbes, Albert Benveniste. Concurrency, sigma-algebras, and probabilistic fairness. [Research Report] RR-6724, INRIA. 2008, pp.24. 〈inria-00338784〉

Partager

Métriques

Consultations de la notice

371

Téléchargements de fichiers

108