The paper proposes a surprisingly simple characterization of a large class of models of distributed computing, via an agreement function: for each set of processes, the function determines the best level of set consensus these processes can reach. We show that the task computability of a large class of fair adversaries that includes, in particular superset-closed and symmetric one, is precisely captured by agreement functions.
Taubenfeld introduced in @cite_12 the notion of a symmetric progress conditions, which is equivalent to our symmetric adversaries.
@cite_12
1792996693
Understanding the effect of different progress conditions on the computability of distributed systems is an important and exciting research direction. For a system with n processes, we define exponentially many new progress conditions and explore their properties and strength. We cover all the known, symmetric and asymmetric, progress conditions and many new interesting conditions. Together with our technical results, the new definitions provide a deeper understanding of synchronization and concurrency.