Error in Self-Stabilizing Spanning-Tree Estimation of Collective State

Yuanqiu Mo; Jacob Beal; Soura Dasgupta

doi:10.1109/FAS-W.2017.112

Back

Conference proceeding

Error in Self-Stabilizing Spanning-Tree Estimation of Collective State

Yuanqiu Mo, Jacob Beal and Soura Dasgupta

2017 IEEE 2nd International Workshops on Foundations and Applications of Self Systems (FASW), pp.1-6

09/2017

DOI: 10.1109/FAS-W.2017.112

View Online

Abstract

Estimating collective state is an important component of many distributed systems, but has inherent challenges in balancing the availability of estimates against their accuracy. In this paper, we analyze the error bounds and dynamics of a commonly used family of self-stabilizing state estimation algorithms based on spanning trees. We find that in the worst case transients can duplicate values leading to exponential overestimates or can drop values leading to near total loss of information. The same analysis, however, also suggests that these problems can be mitigated by prioritizing smoothness in the adaptation of distance estimates used to maintain the spanning tree, and this mitigating effect is supported by results in simulation.

aggregate programming

Aggregates

Algorithm design and analysis

Conferences

control theory

Electronic mail

Heuristic algorithms

predictable composition

State estimation

Details

Title: Subtitle: Error in Self-Stabilizing Spanning-Tree Estimation of Collective State
Creators: Yuanqiu Mo - University of Iowa
Jacob Beal - Raytheon (United States)
Soura Dasgupta - University of Iowa
Resource Type: Conference proceeding
Publication Details: 2017 IEEE 2nd International Workshops on Foundations and Applications of Self Systems (FASW), pp.1-6
DOI: 10.1109/FAS-W.2017.112
Publisher: IEEE
Language: English
Date published: 09/2017
Academic Unit: Electrical and Computer Engineering
Record Identifier: 9984197302902771

Metrics

14 Record Views

16 Times Cited - Web of Science