Efficient Implementation of Fairness in Discrete-Event Systems Using Queues

摘要

Fair synthesis of supervisory control for discrete-event systems is discussed. It is argued that a least restrictive supervisor does not in general exist unless a bound is placed on the number of transitions before which a desired event is required to happen. It is shown how such bounded fairness can be implemented using first-input-first-output (FIFO) queues. Although the language generated by a queue is not the largest among bounded fair restrictions of a behavior, nonoptimality can be exploited in hierarchical implementation of queues by grouping a subset of subsystems as a team and designing two modular queues: one to implement fairness locally among the team members, and the other to implement fairness globally between the team and other subsystems.