2009 | OriginalPaper | Buchkapitel
Fast Self-stabilization for Gradients
verfasst von : Jacob Beal, Jonathan Bachrach, Dan Vickery, Mark Tobenkin
Erschienen in: Distributed Computing in Sensor Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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[1] addresses these shortcomings, and in this paper we prove that it self-stabilizes in
O
(
diameter
) time—more specifically, in 4 ·
diameter
/
c
+
k
seconds, where
k
is a small constant and
c
is the minimum speed of multi-hop message propagation.