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

Paulo Sérgio Almeida, Carlos Baquero, Martín Farach-Colton, Paulo Jesus, Miguel A. Mosteiro

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationPrinciples of Distributed Systems - 15th International Conference, OPODIS 2011, Proceedings
Pages513-527
Number of pages15
DOIs
StatePublished - 2011
Event15th International Conference on Principles of Distributed Systems, OPODIS 2011 - Toulouse, France
Duration: Dec 13 2011Dec 16 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7109 LNCS

Other

Other15th International Conference on Principles of Distributed Systems, OPODIS 2011
Country/TerritoryFrance
CityToulouse
Period12/13/1112/16/11

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Aggregate computation
  • Communication networks
  • Distributed computing
  • Radio networks

Fingerprint

Dive into the research topics of 'Fault-tolerant aggregation: Fow-updating meets mass-distribution'. Together they form a unique fingerprint.

Cite this