Towards Optimal Deterministic LOCAL Algorithms on Trees

While obtaining optimal algorithms for the most important problems in the LOCAL model has been one of the central goals in the area of distributed algorithms since its infancy, tight complexity bounds are elusive for many problems even when considering deterministic complexities on trees. We take a step towards remedying this issue by providing a way to relate the complexity of a problem Π on trees to its truly local complexity, which is the (asymptotically) smallest function f such that Π can be solved in O(f(Δ) + log* n) rounds. More specifically, we develop a transformation that takes an algorithm A for Π with a runtime of O(f(Δ) + log* n) rounds as input and transforms it into an O(f(g(n)) +log* n)-round algorithm A′ on trees, where g is the function that satisfies g(n)f(g(n)) = n. If f is the truly local complexity of Π (i.e., if A is asymptotically optimal), then A′ is an asymptotically optimal algorithm on trees, conditioned on a natural assumption on the nature of the worst-case instances of Π.