Measure Theory and Fair Arbiters.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1987
- Accession Number
- ADA188745
Entities
People
- David M. Mckeown Jr.
Organizations
- Carnegie Mellon University