Distributed Metropolis Sampler with Optimal Parallelism
  The Metropolis-Hastings algorithm is a fundamental Markov chain Monte Carlo
(MCMC) method for sampling and inference. With the advent of Big Data,
distributed and parallel variants of MCMC methods are attracting increased
attention. In this paper, we give a distributed algorithm that can correctly
simulate sequential single-site Metropolis chains without any bias in a fully
asynchronous message-passing model. Furthermore, if a natural Lipschitz
condition is satisfied by the Metropolis filters, our algorithm can simulate
$N$-step Metropolis chains within $O(N/n+\log n)$ rounds of asynchronous
communications, where $n$ is the number of variables. For sequential
single-site dynamics, whose mixing requires $\Omega(n\log n)$ steps, this
achieves an optimal linear speedup. For several well-studied important
graphical models, including proper graph coloring, hardcore model, and Ising
model, our condition for linear speedup is weaker than the respective
uniqueness (mixing) conditions.
  The novel idea in our algorithm is to resolve updates in advance: the local
Metropolis filters can often be executed correctly before the full information
about neighboring spins is available. This achieves optimal parallelism without
introducing any bias.
