Question: Two Phase Routing Algorithm: use the analysis of the first phase to give a full analysis (no "symmetry" argument) of the second phase.
In particular, prove: The second phase of the algorithm terminates in O(n) steps with probability 1 - N^(-alpha) for some constant alpha > 0
Explore the two phase routing algorithm and second phase of the algorithm.