  Inspired by distributed algorithms, we introduce a new class of finite graph
automata that recognize precisely the graph languages definable in monadic
second-order logic. For the cases of words and trees, it has been long known
that the regular languages are precisely those definable in monadic
second-order logic. In this regard, the automata proposed in the present work
can be seen, to some extent, as a generalization of finite automata to graphs.
  Furthermore, we show that, unlike for finite automata on words and trees, the
deterministic, nondeterministic and alternating variants of our automata form a
strict hierarchy with respect to their expressive power. For the weaker
variants, the emptiness problem is decidable.
