On Fairness Notions in Distributed Systems I. A Characterization of Implementability

AbstractThis is the first part of a two-part paper in which we discuss the implementability of fairness notions in distributed systems where asynchronous processes interact via synchronous constructs—usually called multiparty interactions. In this part we present a criterion for fairness notions and show that if a fairness notion violates the criterion, then no deterministic algorithm for scheduling multiparty interactions can satisfy the fairness notion. Conversely, the implementation is possible if the criterion is obeyed. Thus, the criterion is sufficient and necessary to guarantee the implementability of all possible fairness notions. To our knowledge, this is the first such criterion to appear in the literature. The main benefit of the proposed criterion is that it reduces reasoning about a complex and concrete implementation model to reasoning about a simpler and abstract model for process interaction. To illustrate this, we use the criterion to examine several important fairness notions, including strong interaction fairness, strong process fairness, weak process fairness, U-fairness, and hyperfairness. All, except weak process fairness, fail to pass the criterion. Moreover, we also apply the criterion to analyze the system structures rendering the impossibility phenomena. This analysis helps us separate, for each fairness notion, the set of systems for which the fairness notion can be implemented from those for which it cannot