We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
What can be sampled locally?
- Authors
Feng, Weiming; Sun, Yuxin; Yin, Yitong
- 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.
- Subjects
DISTRIBUTED algorithms; MARKOV random fields; GIBBS sampling; GRAPH algorithms; BOLTZMANN factor; DISTRIBUTED computing; MARKOV chain Monte Carlo
- Publication
Distributed Computing, 2020, Vol 33, Issue 3/4, p227
- ISSN
0178-2770
- Publication type
Article
- DOI
10.1007/s00446-018-0332-8