Fast self-healing gradients

Jacob Beal; Jonathan Bachrach; Dan Vickery; Mark Tobenkin

doi:10.1145/1363686.1364163

Back

Conference proceeding

Fast self-healing gradients

Jacob Beal, Jonathan Bachrach, Dan Vickery and Mark Tobenkin

Proceedings of the 2008 ACM symposium on Applied computing, pp.1969-1975

ACM Conferences

SAC '08: The 2008 ACM Symposium on Applied Computing

03/16/2008

DOI: 10.1145/1363686.1364163

View Online

Abstract

We present CRF-Gradient, a self-healing gradient algorithm that provably reconfigures in O(diameter) time. Self-healing gradients are a frequently used building block for distributed self-healing systems, but previous algorithms either have a healing rate limited by the shortest link in the network or must rebuild invalid regions from scratch. We have verified CRF-Gradient in simulation and on a network of Mica2 motes. Our approach can also be generalized and applied to create other self-healing calculations, such as cumulative probability fields.

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: Fast self-healing gradients
Creators: Jacob Beal - IIT@MIT
Jonathan Bachrach - IIT@MIT
Dan Vickery - IIT@MIT
Mark Tobenkin - IIT@MIT
Resource Type: Conference proceeding
Publication Details: Proceedings of the 2008 ACM symposium on Applied computing, pp.1969-1975
Conference: SAC '08: The 2008 ACM Symposium on Applied Computing
Publisher: ACM
Series: ACM Conferences
DOI: 10.1145/1363686.1364163
Language: English
Date published: 03/16/2008
Academic Unit: Electrical and Computer Engineering
Record Identifier: 9984627186202771

Fast self-healing gradients

View Online

Abstract

Details

Metrics