  In classic distributed graph problems, each instance on a graph specifies a
space of feasible solutions (e.g. all proper ($\Delta+1$)-list-colorings of the
graph), and the task of distributed algorithm is to construct a feasible
solution using local information.
  We study distributed sampling and counting problems, in which each instance
specifies a joint distribution of feasible solutions. The task of distributed
algorithm is to sample from this joint distribution, or to locally measure the
volume of the probability space via the marginal probabilities. The latter task
is also known as inference, which is a local counterpart of counting.
  For self-reducible classes of instances, the following equivalences are
established in the LOCAL model up to polylogarithmic factors:
  $\bullet$ For all joint distributions, approximate inference and approximate
sampling are computationally equivalent.
  $\bullet$ For all joint distributions defined by local constraints, exact
sampling is reducible to either one of the above tasks.
  $\bullet$ If further, sequentially constructing a feasible solution is
trivial locally, then all above tasks are easy if and only if the joint
distribution exhibits strong spatial mixing.
  Combining with the state of the arts of strong spatial mixing, we obtain
efficient sampling algorithms in the LOCAL model for various important sampling
problems, including: an $O(\sqrt{\Delta}\log^3n)$-round algorithm for exact
sampling matchings in graphs with maximum degree $\Delta$, and an
$O(\log^3n)$-round algorithm for sampling according to the hardcore model
(weighted independent sets) in the uniqueness regime, which along with the
$\Omega(\mathrm{diam})$ lower bound in arXiv:1702.00142 for sampling according
to the hardcore model in the non-uniqueness regime, gives the first
computational phase transition for distributed sampling.
