It is well known (see, e.g.,
[1]}, [2]}, [3]})
that properties (1)–(3) ensure that a positive constant fraction of the
undecided edges become decided during \(\pi \)  with a positive constant
probability.
Using standard probabilistic arguments, we deduce that all edges become
decided within
\(O (\log n)\) 
phases in expectation and whp, thus, by applying properties (1) and (2) to the
nodes of degree
\(\operatorname{deg}_{G(U)}(v) = 0\) ,
all nodes become decided within
\(O (\log n)\) 
phases in expectation and whp.
Thm. REF  follows, again, by standard probabilistic
arguments.
We now turn to present the implementation of the three modules.
