AVCOL: Availability-aware information aggregation in large distributed systems under uncollaborative behavior

Ramsés Morales, Indranil Gupta

Research output: Contribution to journalArticlepeer-review

Abstract

Aggregation of system-wide information in large-scale distributed systems, such as p2p systems and Grids, can be unfairly influenced by nodes that are selfish, colluding with each other, or are offline most of the time. We present AVCOL, which uses probabilistic and gossip-style techniques to provide availability-aware aggregation. Concretely, AVCOL is the first aggregation system that: (1) implements any (arbitrary) global predicate that explicitly specifies any node's probability of inclusion in the global aggregate, as a mathematical function of that node's availability (i.e., percentage time online); (2) probabilistically tolerates large numbers of selfish nodes and large groups of colluders; and (3) scales well with hundreds to thousands of nodes. AVCOL uses several unique design decisions: per-aggregation tree construction where nodes are allowed a limited but flexible probabilistic choice of parents or children, probabilistic aggregation along trees, and auditing of nodes both during aggregation as well as in gossip-style (i.e., periodically). We have implemented AVCOL, and we experimentally evaluated it using real-life churn traces. Our evaluation and our mathematical analysis show that AVCOL satisfies arbitrary predicates, scales well, and withstands a variety of selfish and colluding attacks.

Original languageEnglish (US)
Pages (from-to)2360-2372
Number of pages13
JournalComputer Networks
Volume53
Issue number13
DOIs
StatePublished - Aug 28 2009

Keywords

  • Aggregation
  • Availability-aware
  • Colluding
  • Overlay
  • Predicates
  • Probabilistic protocol
  • Selfish

ASJC Scopus subject areas

  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'AVCOL: Availability-aware information aggregation in large distributed systems under uncollaborative behavior'. Together they form a unique fingerprint.

Cite this