Miner More, Sara ;
Naumov, Pavel ;
Sapp, Benjamin
Concurrency Semantics for the GeigerPazPearl Axioms of Independence
Abstract
Independence between two sets of random variables is a wellknown relation in probability theory. Its origins trace back to Abraham de Moivre's work in the 18th century. The propositional theory of this relation was axiomatized by Geiger, Paz, and Pearl.
Sutherland introduced a relation in information flow theory that later became known as "nondeducibility." Subsequently, the first two authors generalized this relation from a relation between two arguments to a relation between two sets of arguments and proved that it is completely described by essentially the same axioms as independence in probability theory.
This paper considers a noninterference relation between two groups of concurrent processes sharing common resources. Two such groups are called noninterfering if, when executed concurrently, the only way for them to reach deadlock is for one of the groups to deadlock internally. The paper shows that a complete axiomatization of this relation is given by the same GeigerPazPearl axioms.
BibTeX  Entry
@InProceedings{minermore_et_al:LIPIcs:2011:3248,
author = {Sara Miner More and Pavel Naumov and Benjamin Sapp},
title = {{Concurrency Semantics for the GeigerPazPearl Axioms of Independence}},
booktitle = {Computer Science Logic (CSL'11)  25th International Workshop/20th Annual Conference of the EACSL},
pages = {443457},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897323},
ISSN = {18688969},
year = {2011},
volume = {12},
editor = {Marc Bezem},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3248},
URN = {urn:nbn:de:0030drops32480},
doi = {http://dx.doi.org/10.4230/LIPIcs.CSL.2011.443},
annote = {Keywords: independence, concurrency, information flow, axiomatization}
}
2011
Keywords: 

independence, concurrency, information flow, axiomatization 
Seminar: 

Computer Science Logic (CSL'11)  25th International Workshop/20th Annual Conference of the EACSL

Issue date: 

2011 
Date of publication: 

2011 