Fault-tolerant aggregation: flow-updating meets mass-distribution

DOI10.1007/S00446-016-0288-5MaRDI QIDQ2401680zbMATH OpenOpenAlexFDO

Authors Paulo Sérgio Almeida, Carlos Baquero, Martin Farach-Colton, Paulo Jesus, Miguel A. Mosteiro

Publication date 4 September 2017

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.4373

zbMATH Keywords

aggregate computationcommunication networksdistributed computingradio networks

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Abstract: Flow-Updating (FU) is a fault-tolerant technique that has proved to be efficient in practice for the distributed computation of aggregate functions in communication networks where individual processors do not have access to global information. Previous distributed aggregation protocols, based on repeated sharing of input values (or mass) among processors, sometimes called Mass-Distribution (MD) protocols, are not resilient to communication failures (or message loss) because such failures yield a loss of mass. In this paper, we present a protocol which we call Mass-Distribution with Flow-Updating (MDFU). We obtain MDFU by applying FU techniques to classic MD. We analyze the convergence time of MDFU showing that stochastic message loss produces low overhead. This is the first convergence proof of an FU-based algorithm. We evaluate MDFU experimentally, comparing it with previous MD and FU protocols, and verifying the behavior predicted by the analysis. Finally, given that MDFU incurs a fixed deviation proportional to the message-loss rate, we adjust the accuracy of MDFU heuristically in a new protocol called MDFU with Linear Prediction (MDFU-LP). The evaluation shows that both MDFU and MDFU-LP behave very well in practice, even under high rates of message loss and even changing the input values dynamically.

Recommendations

• Near-optimal communication-time tradeoff in fault-tolerant computation of aggregate functions
• Near-optimal communication-time tradeoff in fault-tolerant computation of aggregate functions
• Robust gossip-based aggregation: a practical point of view
• Practical fault-tolerant data aggregation
• Efficient Dynamic Aggregation

Cites work

• An early-stopping protocol for computing aggregate functions in Sensor Networks
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Communication in dynamic radio networks
• Consensus Problems in Networks of Agents With Switching Topology and Time-Delays
• Fast linear iterations for distributed averaging
• Fault-tolerant aggregation: flow-updating meets mass-distribution
• Geographic Gossip: Efficient Averaging for Sensor Networks
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 5454133 (Why is no real title available?)
• scientific article; zbMATH DE number 878897 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• Probability and Computing
• Time complexity of radio broadcasting: adaptiveness vs. obliviousness and randomization vs. determinism

Cited in

(4)

• A faster exact-counting protocol for anonymous dynamic networks
• LiMoSense: live monitoring in dynamic sensor networks
• Fault-tolerant aggregation: flow-updating meets mass-distribution
• Sublinear algorithms in \(T\)-interval dynamic networks

Describes a project that uses

Uses Software

• TAG

This page was built for publication: Fault-tolerant aggregation: flow-updating meets mass-distribution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2401680)