Accession Number : ADA188745
Title : Measure Theory and Fair Arbiters.
Descriptive Note : Interim rept.,
Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Personal Author(s) : McKeown, David M , Jr
PDF Url : ADA188745
Report Date : Dec 1987
Pagination or Media Count : 18
Abstract : This paper considered the fairness of mutual exclusion elements, the most important building block for any arbiter, A probabilistic choice set model was introduced to capture the choice behavior of such elements. Using this model on infinite sequences we defined a probabilistic notion of fairness, and shown that mutual exclusion elements are fair in general, provided that a simple assumption about their probabilistic behavior is satisfied. (Any well-designed mutual exclusion element does satisfy the assumption.) We extended this result to establish the fairness of a wide class of arbiters including virtually all known non-prioritized multi-input designs. This essentially settles the weak fairness question for non-prioritized arbiters; in general such arbiters are fair in a sense that is very close to the standard notion of weak fairness.
Descriptors : *MEASURE THEORY, INFINITE SERIES, MATHEMATICAL MODELS, MODELS, MODULAR CONSTRUCTION, PROBABILITY, SEQUENCES
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE