Gradients are distributed distance estimates used as a building block in many sensor network applications. In large or long-lived deployments, it is important for the estimate to self-stabilize in response to changes in the network or ongoing computations, but existing algorithms may repair very slowly, produce distorted estimates, or suffer large transients. The CRF-Gradient algorithm addresses these shortcomings, and in this paper we prove that it self-stabilizes in
) time—more specifically, in 4 ·
is a small constant and
is the minimum speed of multi-hop message propagation.