Logo image
Back
Effect of Monotonic Filtering on Graph Collection Dynamics
Conference proceeding

Effect of Monotonic Filtering on Graph Collection Dynamics

Hunza Zainab, Giorgio Audrito, Soura Dasgupta and Jacob Beal
2021 IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion (ACSOS-C), pp.68-73
IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion (Washington, DC, USA, 09/27/2021–10/01/2021)
09/2021
DOI: 10.1109/ACSOS-C52956.2021.00036

View Online

Abstract

Distributed data collection is a fundamental task in open systems. In such networks, data is aggregated across a network to produce a single aggregated result at a source device. Though self-stabilizing, algorithms performing data collection can produce large overestimates of aggregates in the transient phase. For example, in [1] we demonstrated that in a line graph, a switch of sources after initial stabilization may produce overestimates that are quadratic in the network diameter. We also proposed monotonic filtering as a strategy for removing such large overestimates. Monotonic filtering prevents the transfer of data from device A to device B unless the distance estimate at A is more than that at B at the previous iteration. For a line graph, [1] shows that monotonic filtering prevents quadratic overestimates. This paper analyzes monotonic filtering for an arbitrary graph topology, showing that for an N device network, the largest overestimate after switching sources is at most 2N .
 data aggregation Data collection edge computing Filtering Heuristic algorithms Open systems Performance evaluation Perturbation methods self-stabilization Switches

Details

Metrics

7 Record Views
1 Times Cited - Web of Science
Logo image