  We conduct a systematic study of asynchronous models of distributed computing
consisting of identical finite-state devices that cooperate in a network to
decide if the network satisfies a given graph-theoretical property. Models
discussed in the literature differ in the detection capabilities of the agents
residing at the nodes of the network (detecting the set of states of their
neighbors, or counting the number of neighbors in each state), the notion of
acceptance (acceptance by halting in a particular configuration, or by stable
consensus), the notion of step (synchronous move, interleaving, or arbitrary
timing), and the fairness assumptions (non-starving, or stochastic-like). We
study the expressive power of the combinations of these features, and show that
the initially twenty possible combinations fit into seven equivalence classes.
The classification is the consequence of several equi-expressivity results with
a clear interpretation. In particular, we show that acceptance by halting
configuration only has non-trivial expressive power if it is combined with
counting, and that synchronous and interleaving models have the same power as
those in which an arbitrary set of nodes can move at the same time. We also
identify simple graph properties that distinguish the expressive power of the
seven classes.
