This paper presents the analysis of three revision algorithms
for 2-variable Constraint Satisfaction Problems (CSPs). The
revision algorithms under consideration are called L, L', and L''.
For 2-variable CSPs L models an optimal arc consistency algorithm
which exploits multi-directionality. However, L' and L'' do not
exploit multi-directionality. For 2-variable CSPs L' is equivalent
to the arc consistency algorithm AC-3. The expected number and the
variance of the checks are presented for L, L', and L''. Writing
A < B if the expected number of checks for A is less than for B,
we have L < L' < L''. The results are parametrised over the
probability p that a random check succeeds and probability q = 1-p
that it fails. It is proved that the difference between the
expected number of checks of any two algorithms is bounded by
min(b, 1 + ceiling( ln(a)/ln(1/q)))/p. Using a variance analysis,
it is proved that, as the domain sizes a and b become large, the
number of checks which are required by the revision algorithms is
sharply concentrated about their expected number of checks.
Finally, our analysis allows us to find an upper bound of
2 e d /p + (2 e - n) d(d - 1)/2 p for the expected time complexity
of AC-3, where e is the number of constraints, n the number of
variables, and d the maximum domain size. These results are novel
and encouraging.  First they provide the first non-trivial upper
bound on the expected time complexity of AC-3. Second, they
demonstrate that on average there is a small margin separating
L, L', and L''.  Finally, they present the first results about
the variance of the checks required by revision algorithms.