Skip to main content


eCommons@Cornell >
Faculty of Computing and Information Science >
Computing and Information Science >
Computing and Information Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Latency- and Bandwidth-Minimizing Optimal Failure Detectors
Authors: So, Kelvin
Sirer, Emin Gun
Keywords: computer science
technical report
Issue Date: 1-May-2006
Publisher: Cornell University
Abstract: Failure detectors are fundamental building blocks in distributed systems. Multi-node failure detectors, where the detector is tasked with monitoring other nodes, play a critical role in overlay networks and peer-to-peer systems. In such networks, failures need to be detected quickly and with low overhead. Achieving these properties simultaneously poses a difficult tradeoff between detection latency and resource consumption. In this paper, we examine this central tradeoff, formalize it as an optimization problem and analytically derive the optimal closed form formulas for multi-node failure detectors. We provide two variants of the optimal solution for optimality metrics appropriate for two different deployment scenarios. The latency-minimizing failure detector (LM-OFD) achieves the lowest average failure detection latency given a fixed bandwidth constraint for system maintenance. The bandwidth-minimizing failure detector (BM-OFD) will meet a desired detection latency target with the least amount of bandwidth consumed. We evaluate our optimal results with node lifetimes chosen from bimodal and power-law distributions, as well as real-world trace data from PlanetLab hosts that spans five months. Compared to standard failure detectors in wide use, our approach reduces failure detection latencies by 40% on average for the same bandwidth consumption, or conversely, reduce the amount of bandwidth consumed by 30% for the same failure detection latency.
Appears in Collections:Computing and Information Science Technical Reports

Files in This Item:

File Description SizeFormat
TR2006-2025.pdf193.52 kBAdobe PDFView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us