AVMON: Optimal and scalable discovery of consistent availability monitoring overlays for distributed systems

Ramsés Morales, Indranil Gupta

Research output: Contribution to journalArticlepeer-review


This paper proposes to build overlays that help in monitoring of long-term availability histories of hosts, with a focus on large-scale distributed settings where hosts may be selfish or colluding. Concretely, we target the important problems of selection and discovery of an availability monitoring overlay. We motivate six significant goals - firstly, consistency, verifiability, and randomness, in selecting availability monitors of nodes, so as to be probabilistically resilient to selfish and colluding nodes. The next three goals are discoverability, load-balancing, and scalability in finding these monitors. We present AVMON, the first availability monitoring overlay to satisfy these six requirements. Our core algorithmic contribution is a range of protocols for discovering the availability monitoring overlay scalably and efficiently, given any arbitrary monitor selection scheme that is consistent and verifiable. We mathematically analyze the performance of AVMON's discovery protocols w.r.t. scalability and discovery time of monitors. Most interestingly, we are able to derive optimal (and practical) variants of AVMON, that minimize different combinations of memory, bandwidth, computation, and monitor discovery time. Finally, our extensive experimental evaluations using three types of availability traces - synthetic, from PlanetLab, and from the a peer-to-peer system (Overnet). Our results demonstrate AVMON's practicality in a variety of distributed systems.

Original languageEnglish (US)
Pages (from-to)446-459
Number of pages14
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number4
StatePublished - 2009


  • Availability
  • Churn
  • Consistency
  • Distributed systems
  • Monitoring
  • Optimality
  • Overlay
  • Scalability

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'AVMON: Optimal and scalable discovery of consistent availability monitoring overlays for distributed systems'. Together they form a unique fingerprint.

Cite this