Flexible self-healing gradients

Jacob Beal

doi:10.1145/1529282.1529550

Back

Conference proceeding

Flexible self-healing gradients

Jacob Beal

Proceedings of the 2009 ACM symposium on Applied Computing, pp.1197-1201

ACM Conferences

SAC09: The 2009 ACM Symposium on Applied Computing

03/08/2009

DOI: 10.1145/1529282.1529550

View Online

Abstract

Self-healing gradients are distributed estimates of the distance from each device in a network to the nearest device designated as a source, and are used in many pervasive computing systems. With previous self-healing gradient algorithms, even the smallest changes in the source or network can produce small estimate changes throughout the network, leading to high communication and energy costs. We observe, however, that in many applications, such as routing and geometric restriction of processes, devices far from the source need only coarse estimates, and that a device need not communicate when its estimate does not change. We have therefore developed Flex-Gradient, a new self-healing gradient algorithm with a tunable trade-off between precision and communication cost. When distance is estimated using Flex-Gradient, the constraints between neighboring devices are flexible, allowing estimates to vary by an amount proportional to a device's distance to the source. Frequent small changes in the network or source thus cause frequent estimate changes only within a distance proportional to the magnitude of the change, as verified in simulation on a network of 1000 devices. This can enable drastic reductions in the communication and energy cost of gradient-based algorithms.

Computing methodologies -- Distributed computing methodologies -- Distributed programming languages

Networks -- Network types -- Mobile networks

Networks -- Network types -- Wireless access networks

Software and its engineering -- Software notations and tools -- General programming languages -- Language types -- Distributed programming languages

Theory of computation -- Randomness, geometry and discrete structures

Theory of computation -- Randomness, geometry and discrete structures -- Computational geometry

Details

Title: Subtitle: Flexible self-healing gradients
Creators: Jacob Beal - BBN Technologies, Cambridge, Massachusetts
Resource Type: Conference proceeding
Publication Details: Proceedings of the 2009 ACM symposium on Applied Computing, pp.1197-1201
Conference: SAC09: The 2009 ACM Symposium on Applied Computing
Publisher: ACM
Series: ACM Conferences
DOI: 10.1145/1529282.1529550
Language: English
Date published: 03/08/2009
Academic Unit: Electrical and Computer Engineering
Record Identifier: 9984627236402771

Metrics

1 Record Views