What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing

Lélia Blin, Fedor V. Fomin, Pierre Fraigniaud +5

The question of 'what can be computed locally?' lies at the heart of distributed computing in networks. As established in Naor and Stockmeyer's seminal paper (STOC 1993), this ques…