AVMEM - Availability-aware overlays for management operations in non-cooperative distributed systems

Ramsés Morales, Brian Cho, Indranil Gupta

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


Monitoring and management operations that query nodes based on their availability can be extremely useful in a variety of large-scale distributed systems containing hundreds to thousands of hosts, e.g., p2p systems, Grids, and PlanetLab. This paper presents decentralized and scalable solutions to a subset of such availability-based management tasks. Specifically, we propose AVMEM, which is the first availability-aware overlay to date. AVMEM is intended for generic non-cooperative scenarios where nodes may be selfish and may wish to route messages to a large set of other nodes, especially if the selfish node has low availability. Under this setting, our concrete contributions are the following: (1) AVMEM allows arbitrary classes of application-specified predicates to create the membership relationships in the overlay. In order to avoid selfish nodes from exploiting the system, we focus on predicates that are random and consistent. In other words, whether a given node y is a neighbor of a given node x is decided based on a consistent and probabilistic predicate, dependent solely on the identifiers and availabilities of these two nodes, but without using any external inputs. (2) AVMEM protocols discover and maintain the overlay spanned by the application-specified AVMEM predicate in a scalable and fast manner. (3) We use AVMEM to execute important availability-based management operations, focusing on range-anycast, range-multicast, threshold-anycast, and threshold-multicast. AVMEM works well in the presence of selfish nodes, scales to thousands of nodes, and executes each of the targeted operations quickly and reliably. Our evaluation is driven by real-life churn traces from the Overnet p2p system, and shows that AVMEM works well in practical settings.

Original languageEnglish (US)
Title of host publicationMiddleware 2007 - ACM/IFIP/USENIX 8th International Middleware Conference, Proceedings
EditorsRenato Cerqueira, Roy H. Campbell
Number of pages21
ISBN (Print)9783540767770
StatePublished - 2007
Event8th International Middleware Conference, Middleware 2007 - Newport Beach, CA, United States
Duration: Nov 26 2007Nov 30 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4834 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other8th International Middleware Conference, Middleware 2007
Country/TerritoryUnited States
CityNewport Beach, CA


  • Availability variation
  • Distributed algorithms
  • Management
  • Membership protocols
  • P2P systems
  • Predicates

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'AVMEM - Availability-aware overlays for management operations in non-cooperative distributed systems'. Together they form a unique fingerprint.

Cite this