What can be sampled locally?

Abstract

The local computation of Linial [FOCS’87] and Naor and Stockmeyer [STOC’93] studies whether a locally defined distributed computing problem is locally solvable. In classic local computation tasks, the goal of distributed algorithms is to construct a feasible solution for some constraint satisfaction problem (CSP) locally defined on the network. In this paper, we consider the problem of sampling a uniform CSP solution by distributed algorithms in the LOCAL model, and ask whether a locally definable joint distribution is locally sample-able. We use Markov random fields and Gibbs distributions to model locally definable joint distributions. We give two distributed algorithms based on Markov chains, called LubyGlauber and LocalMetropolis, which we believe to represent two basic approaches for distributed Gibbs sampling. The algorithms achieve respective mixing times O(Δlog n) and O(log n) under typical mixing conditions, where n is the number of vertices and Δ is the maximum degree of the graph. We show that the time bound Θ(log n) is optimal for distributed sampling. We also show a strong Ω(diam) lower bound: in particular for sampling independent set in graphs with maximum degree Δ≥ 6. This gives a strong separation between sampling and constructing locally checkable labelings.