Brief announcement:
exponential speed-up of local algorithms using non-local communication

Summary

We demonstrate how to leverage a system's capability for all-to-all communication to achieve an exponential speed-up of local algorithms despite bandwidth and memory restrictions. More precisely, if a network comprises n nodes with all-to-all bandwidth nε (ε > 0 constant) and nodes know their input and neighborhood with respect to a graph problem instance of polylogarithmic maximum degree, any local algorithm for this problem with running time r ∈ O(log n) and reasonably small states can be simulated within O(log r) rounds.