Preprint
Monotonic Filtering for Distributed Collection
ArXiv.org
07/12/2021
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 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.
Details
- Title: Subtitle
- Monotonic Filtering for Distributed Collection
- Creators
- Hunza ZainabGiorgio AudritoSoura DasguptaJacob Beal
- Resource Type
- Preprint
- Publication Details
- ArXiv.org
- ISSN
- 2331-8422
- Language
- English
- Date posted
- 07/12/2021
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984198014302771
Metrics
3 Record Views