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