AVMON: Optimal and Scalable Discoveryof Consistent Availability MonitoringOverlays for Distributed SystemsRamse´s Morales, Student Member, IEEE, and Indranil Gupta, Member, IEEEAbstract—This paper proposes to build overlays that help in the monitoring of long-term availability histories of hosts, with a focus onlarge-scale distributed settings where hosts may be selfish or colluding (but not malicious). Concretely, we focus on the importantproblems of selection and discovery of such an availability monitoring overlay. We motivate six significant goals for theseproblems—the first three goals are consistency, verifiability, and randomness in selecting the availability monitors of nodes, so as to beprobabilistically resilient to selfish and colluding nodes. The next three goals are discoverability, load balancing, and scalability infinding these monitors. We then present AVMON, an availability monitoring overlay that is the first system to satisfy all the above sixrequirements. The core algorithmic contribution of this paper is a range of protocols for discovering the availability monitoring overlay ina scalable and efficient manner, given any arbitrary monitor selection scheme that is consistent and verifiable. We mathematicallyanalyze the performance of AVMON’s discovery protocols with respect to scalability and discovery time of monitors. Most interestingly,we are able to derive optimal variants of AVMON, with the aim of minimizing memory, bandwidth, computation, and discovery time ofmonitors (or a subset of these metrics). Our analysis indicates that these optimal variants are also practically feasible. Finally, weperform extensive experimental evaluations of AVMON by using three types of availability traces—synthetic, from PlanetLab, and froma peer-to-peer system (Overnet). Our results demonstrate that AVMON would work well in a wide variety of distributed systems.Index Terms—D.4.7.b Distributed systems, churn, availability, monitoring, overlay, consistency, scalability, optimality.Ç1INTRODUCTIONLARGE-SCALE distributed applications running atop peer-to-peer (P2P) settings, as well as PlanetLab [2] andEnterprise Grids [3], have to deal with the phenomenon ofchurn. Churn refers to rapid and continuous arrival anddeparture, failure, and birth and death of computer hosts(nodes) in the system. Such availability variation acrossnodes and across time has recently led to the design ofmany availability-aware strategies for distributed computingproblems such as replication, multicast, etc. [4], [5], [6], [7],[8], [9]. These strategies aim to make such distributedsystems churn resistant and churn adaptive.However, such availability-aware strategies necessarilyrely on the presence of an underlying availability monitoringservice. The high-level goal of an availability monitoringservice is to maintain long-term availability information foreach host (i.e., for each node) in the system. While a fewavailability monitoring solutions have been proposed in theliterature (e.g., [4], [5], and [8]), the generic availabilitymonitoring problem has not been addressed as yet. Thispaper is the first to explicitly define goals for the availabilitymonitoring problem to address these goals with a generaland overlay-independent solution and to explore theoptimality of discovery protocols for the overlay.The problem challenge, in the availability monitoringoverlay problem, comes from the fact that nodes may beselfish or colluding. Such nodes are not malicious but reporthigher-than-measured availabilities for themselves and their“friend” nodes (we will elaborate on this soon). Never-theless, the benefits of an availability monitoring service thatovercomes this challenge are numerous and varied. Applica-tions that rely on such a service include availability-basedreplica selection [4], [5], [6], [9], availability-based parentselection in overlay multicast trees [6], and implementationof availability-based reliability predicates for multicast [8]. Infact, Godfrey et al. recently showed in [6] that with detailedavailability history about each node in the system, one candesign “smart” node selection strategies for the replication ofa service or a file and that these outperform availability-agnostic strategies. Finally, availability histories of nodes caneven be used to predict availability of individual nodes in thefuture, e.g., [7].Concretely, this availability monitoring problem consistsof two orthogonal subproblems: 1) Selection and Discoveryof the Availability Monitoring Overlay, for each node x, selectand discover a list of nodes who monitor node x, and2) Availability History Maintenance, what is the exactmechanism used by a monitor of a given node x to storex’s availability history. While several different techniqueshave been proposed for the subproblem 2, i.e., how amonitor maintains history (see, e.g., [4] and [7]), the solutionspace for subproblem 1 is relatively less explored. In otherwords, any existing technique for availability historyIEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 20, NO. X, XXX 2009 1. The authors are with the Department of Computer Science, University ofIllinois at Urbana-Champaign, Siebel Center for Computer Science, MC-258, 201 N. Goodwin Avenue, Urbana, Illinois 61801.E-mail: {rvmorale, indy}@cs.uiuc.edu.Manuscript received 13 Sept. 2007; revised 31 Mar. 2008; accepted 2 May2008; published online 22 May 2008.Recommended for acceptance by C. Shahabi.For information on obtaining reprints of this article, please send e-mail to:[email protected], and reference IEEECS Log Number TPDS-2007-09-0314.Digital Object Identifier no. 10.1109/TPDS.2008.84.1045-9219/09/$25.00 ß 2009 IEEE Published by the IEEE Computer SocietyThis article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.Authorized licensed use limited to: IEEE Xplore. Downloaded on March 26, 2009 at 16:16 from IEEE Xplore. Restrictions apply.maintenance (e.g., raw, aged, recent, etc. [7]) can be usedorthogonally with a given availability monitoring overlay.Thus, our focus in this paper is only on the morechallenging subproblem 1: of selection and discovery of theAvailability Monitoring Overlay. Formally, this problemcan be stated as follows: (following the notation of [8]). Foreach node x, select and discover a small subset of nodes tomonitor x. Denote this monitoring set of x as PSðxÞ, calledthe pinging set
View Full Document
Unlocking...