\{ b \}, b') = b$ for all $b, b' \in B$.

Peek Arc Consistency {#ss:pac}
--------------------

We now present the peek arc consistency algorithm. It attempts to find, for each variable $a \in A$, a value $b \in B$ such that when $a$ is set to $b$, the arc consistency check is passed.

[**Peek Arc Consistency**]{}\

------------------------------------------------------------------------

Peek arc consistency was introduced and studied by Bodirsky and Chen [@peek]; the notions and results that follow come from them. In their work, the algorithm is shown to solve certain constraint languages, including some languages having infinite-size universes; such languages actually gave the motivation for introducing the algorithm. In this work, it is pointed out that peek arc consistency can be readily parallelized; by invoking the arc consistency checks independently in parallel, one can achieve a linear parallel running time.

\[def:pacc\] An instance $({\mathbf{A}}, {\mathbf{B}})$ has the *peek arc consistency condition (PACC)* if for every element $a \in A$, there exists a homomorphism $h$ from ${\mathbf{A}}$ to ${\wp}({\mathbf{B}})$ such that $h(a)$ is a singleton.

\[prop:pacc\] The peek arc consistency algorithm does not reject an instance $({\mathbf{A}}, {\mathbf{B}})$ if and only if the instance has the PACC.

\[def:pac-solves\] Let ${\mathbf{B}}$ be a 