AVMON: Optimal and Scalable Discovery of Consistent Availability Monitoring Overlays for Distributed Systems
This paper proposes to build overlays that help in the monitoring of long-term availability histories of hosts, with a focus on large-scale distributed settings where hosts may be selfish or colluding (but not malicious). Concretely, we focus on the important problems of selection and discovery of such an availability monitoring overlay. We motivate six significant goals for these problems-the first three goals are consistency, verifiability, and randomness in selecting the 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 then present AVMON, an availability monitoring overlay that is the first system to satisfy all the above six requirements. The core algorithmic contribution of this paper is a range of protocols for discovering the availability monitoring overlay in a scalable and efficient manner, given any arbitrary monitor selection scheme that is consistent and verifiable. We mathematically analyze 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 of monitors (or a subset of these metrics). Our analysis indicates that these optimal variants are also practically feasible. Finally, we perform extensive experimental evaluations of AVMON by using three types of availability traces-synthetic, from PlanetLab, and from a peer-to-peer system (Overnet). Our results demonstrate that AVMON would work well in a wide variety of distributed systems.
optimality scalability consistency availability monitoring overlay distributed systems churn