Empirical Characterization of Discretization Error in Gradient-Based Algorithms

Many self-organizing and self-adaptive systems use the biologically inspired "gradient" primitive, in which each device in a network estimates its distance to the closest device designated as a source of the gradient. Distance through the network is often used as a proxy for geometric distance, but the accuracy of this approximation has not previously been quantified well enough to allow predictions of the behavior of gradient-based algorithms. We address this need with an empirical characterization of the discretization error of gradient on random unit disc graphs. This characterization has uncovered two troublesome phenomena: an unsurprising dependence of error on source shape and an unexpected transient that becomes a major source of error at high device densities. Despite these obstacles, we are able to produce a quantitative model of discretization error for planar sources at moderate densities, which we validate by using it to predict error of gradient-based algorithms for finding bisectors and communication channels. Refinement and extension of the gradient discretization error model thus offers the prospect of greatly improving the engineerability of self-organizing systems on spatial networks.