research-article

Fast self-healing gradients

Authors:

Jonathan Bachrach,

Mark TobenkinAuthors Info & Claims

SAC '08: Proceedings of the 2008 ACM symposium on Applied computing

Pages 1969 - 1975

https://doi.org/10.1145/1363686.1364163

Published: 16 March 2008 Publication History

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.

References

[1]

J. Bachrach and J. Beal. Programming a sensor network as an amorphous medium. In Distributed Computing in Sensor Systems (DCOSS) 2006 Poster, June 2006.

[2]

J. Bachrach, R. Nagpal, M. Salib, and H. Shrobe. Experimental results and theoretical analysis of a self-organizing global coordinate system for ad hoc sensor networks. Telecommunications Systems Journal, Special Issue on Wireless System Networks, 2003.

[3]

J. Beal. Programming an amorphous computational medium. In Unconventional Programming Paradigms International Workshop, September 2004.

Digital Library

[4]

J. Beal and J. Bachrach. Infrastructure for engineered emergence in sensor/actuator networks. IEEE Intelligent Systems, pages 10--19, March/April 2006.

Digital Library

[5]

J. Beal, J. Bachrach, and M. Tobenkin. Constraint and restoring force. Technical Report MIT-CSAIL-TR-2007-042, MIT, August 2007.

[6]

W. Butera. Programming a Paintable Computer. PhD thesis, MIT, 2002.

Digital Library

[7]

L. Clement and R. Nagpal. Self-assembly and self-repairing topologies. In Workshop on Adaptability in Multi-Agent Systems, RoboCup Australian Open, Jan. 2003.

[8]

A. Eames. Enabling path planning and threat avoidance with wireless sensor networks. Master's thesis, MIT, June 2005.

[9]

Q. Fang, J. Gao, L. Guibas, V. de Silva, and L. Zhang. Glider: Gradient landmark-based distributed routing for sensor networks. In INFOCOM 2005, March 2005.

[10]

D. Gay, P. Levis, R. von Behren, M. Welsh, E. Brewer, and D. Culler. The nesc language: A holistic approach to networked embedded systems. In Proceedings of Programming Language Design and Implementation (PLDI) 2003, June 2003.

Digital Library

[11]

C. Intanagonwiwat, R. Govindan, and D. Estrin. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Sixth Annual International Conference on Mobile Computing and Networking (MobiCOM '00), August 2000.

Digital Library

[12]

L. Kleinrock and J. Silvester. Optimum transmission radii for packet radio networks or why six is a magic number. In Natl. Telecomm. Conf., pages 4.3.1--4.3.5, 1978.

[13]

H. Luo, F. Ye, J. Cheng, S. Lu, and L. Zhang. Ttdd: A two-tier data dissemination model for large-scale wireless sensor networks. Journal of Mobile Networks and Applications (MONET), 2003.

[14]

M. Mamei, F. Zambonelli, and L. Leonardi. Co-fields: an adaptive approach for motion coordination. Technical Report 5-2002, University of Modena and Reggio Emilia, 2002.

[15]

F. Ye, G. Zhong, S. Lu, and L. Zhang. Gradient broadcast: a robust data delivery protocol for large scale sensor networks. ACM Wireless Networks (WINET), 11(3):285--298, 2005.

Digital Library

Cited By

Pianini DCasadei RViroli M(2022)Self-stabilising Priority-Based Multi-Leader Election and Network Partitioning2022 IEEE International Conference on Autonomic Computing and Self-Organizing Systems (ACSOS)10.1109/ACSOS55765.2022.00026(81-90)Online publication date: Sep-2022
https://doi.org/10.1109/ACSOS55765.2022.00026
Aguzzi GCasadei RViroli M(2022)Towards Reinforcement Learning-based Aggregate ComputingCoordination Models and Languages10.1007/978-3-031-08143-9_5(72-91)Online publication date: 14-Jun-2022
https://doi.org/10.1007/978-3-031-08143-9_5
Casadei RViroli MAudrito GDamiani F(2020)FScaFi : A Core Calculus for Collective Adaptive Systems ProgrammingLeveraging Applications of Formal Methods, Verification and Validation: Engineering Principles10.1007/978-3-030-61470-6_21(344-360)Online publication date: 27-Oct-2020
https://doi.org/10.1007/978-3-030-61470-6_21
Show More Cited By

Index Terms

Fast self-healing gradients

Recommendations

Flexible self-healing gradients
SAC '09: Proceedings of the 2009 ACM symposium on Applied Computing

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 ...
Self-healing for autonomic pervasive computing
SAC '07: Proceedings of the 2007 ACM symposium on Applied computing

Self-healing is one of the main challenges to growing autonomic pervasive computing. Fault detection and recovery are the main steps of self-healing. Due to the characteristics of pervasive computing the self-healing becomes difficult. In this paper, ...
Reflection, self-awareness and self-healing in OpenORB
WOSS '02: Proceedings of the first workshop on Self-healing systems

There is a growing interest in the area of self-healing systems. Self-healing does however impose considerable demands on system infrastructures---especially in terms of openness and support for reconfigurability. This paper proposes that the self-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SAC '08: Proceedings of the 2008 ACM symposium on Applied computing

March 2008

2586 pages

ISBN:9781595937537

DOI:10.1145/1363686

Conference Chairs:
Roger L. Wainwright
University of Tulsa
,
Hisham M. Haddad
Kennesaw State University

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 March 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SAC '08

Sponsor:

SIGAPP

SAC '08: The 2008 ACM Symposium on Applied Computing

March 16 - 20, 2008

Fortaleza, Ceara, Brazil

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25

Sponsor:
sigapp

The 40th ACM/SIGAPP Symposium on Applied Computing

March 31 - April 4, 2025

Catania , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

41
Total Citations
View Citations
209
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 27 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Pianini DCasadei RViroli M(2022)Self-stabilising Priority-Based Multi-Leader Election and Network Partitioning2022 IEEE International Conference on Autonomic Computing and Self-Organizing Systems (ACSOS)10.1109/ACSOS55765.2022.00026(81-90)Online publication date: Sep-2022
https://doi.org/10.1109/ACSOS55765.2022.00026
Aguzzi GCasadei RViroli M(2022)Towards Reinforcement Learning-based Aggregate ComputingCoordination Models and Languages10.1007/978-3-031-08143-9_5(72-91)Online publication date: 14-Jun-2022
https://doi.org/10.1007/978-3-031-08143-9_5
Casadei RViroli MAudrito GDamiani F(2020)FScaFi : A Core Calculus for Collective Adaptive Systems ProgrammingLeveraging Applications of Formal Methods, Verification and Validation: Engineering Principles10.1007/978-3-030-61470-6_21(344-360)Online publication date: 27-Oct-2020
https://doi.org/10.1007/978-3-030-61470-6_21
Mo YDasgupta SBeal J(2019)Robustness of the Adaptive Bellman –Ford Algorithm: Global Stability and Ultimate BoundsIEEE Transactions on Automatic Control10.1109/TAC.2019.290423964:10(4121-4136)Online publication date: Oct-2019
https://doi.org/10.1109/TAC.2019.2904239
Mo YDasgupta SBeal J(2019)Global Uniform Asymptotic Stability of a Generalized Adaptive Bellman-Ford Algorithm2019 IEEE 58th Conference on Decision and Control (CDC)10.1109/CDC40024.2019.9029773(1868-1873)Online publication date: Dec-2019
https://doi.org/10.1109/CDC40024.2019.9029773
Viroli MBeal JDamiani FAudrito GCasadei RPianini D(2019)From distributed coordination to field calculus and aggregate computingJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2019.100486109(100486)Online publication date: Dec-2019
https://doi.org/10.1016/j.jlamp.2019.100486
Viroli MAudrito GBeal JDamiani FPianini D(2018)Engineering Resilient Collective Adaptive Systems by Self-StabilisationACM Transactions on Modeling and Computer Simulation10.1145/317777428:2(1-28)Online publication date: 9-Mar-2018
https://dl.acm.org/doi/10.1145/3177774
Audrito GDamiani FViroli MBini E(2018)Distributed Real-Time Shortest-Paths Computations with the Field Calculus2018 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS.2018.00013(23-34)Online publication date: Dec-2018
https://doi.org/10.1109/RTSS.2018.00013
Mo YDasgupta SBeal J(2018)Robust Stability of Spreading Blocks in Aggregate Computing2018 IEEE Conference on Decision and Control (CDC)10.1109/CDC.2018.8618735(6007-6012)Online publication date: Dec-2018
https://doi.org/10.1109/CDC.2018.8618735
Viroli MBeal JDamiani FAudrito GCasadei RPianini D(2018)From Field-Based Coordination to Aggregate ComputingCoordination Models and Languages10.1007/978-3-319-92408-3_12(252-279)Online publication date: 27-May-2018
https://doi.org/10.1007/978-3-319-92408-3_12
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten