  We prove a Borel version of the local lemma, i.e. we show that, under
suitable assumptions, if the set of variables in the local lemma has a
structure of a Borel space, then there exists a satisfying assignment which is
a Borel function. The main tool which we develop for the proof, which is of
independent interest, is a parallel version of the Moser-Tardos algorithm which
uses the same random bits to resample clauses that are far enough in the
dependency graph.
