Brief announcement: Exponential speed-up of local algorithms using non-local communication
C Lenzen, R Wattenhofer - Proceedings of the 29th ACM SIGACT …, 2010 - dl.acm.org
Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of …, 2010•dl.acm.org
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) …
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) …
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.
ACM Digital Library