DATE: Thursday, August 17, 2006
TIME: 12:00 noon - 1:00 pm
PLACE: Wean Hall 8220

SPEAKER:
Brighten Godfrey
UC Berkeley

TITLE:
Minimizing Churn in Distributed Systems

ABSTRACT:
A pervasive requirement of distributed systems is to deal with churn --- change in the set of participating nodes due to joins, graceful leaves, and failures. A high churn rate can increase costs or decrease service quality. This paper studies how to reduce churn by selecting which subset of a set of available nodes to use.

First, we provide a comparison of the performance of a range of different node selection strategies in five real-world traces. Among our findings is that the simple strategy of picking a uniform-random replacement whenever a node fails performs surprisingly well. We explain its performance through analysis in a stochastic model.

Second, we show that a class of strategies, which we call "Preference List" strategies, arise commonly as a result of optimizing for a metric other than churn, and produce high churn relative to more randomized strategies under realistic node failure patterns. Using this insight, we demonstrate and explain differences in performance for designs that incorporate varying degrees of randomization. We give examples from a variety of protocols, including anycast, overlay multicast, and distributed hash tables. In many cases, simply adding some randomization can go a long way towards reducing churn.

This is joint work with Scott Shenker and Ion Stoica and is to appear in SIGCOMM'06.

BIO:
Brighten Godfrey is a Ph.D. student advised by Ion Stoica at UC Berkeley.  His research interests include algorithms for and analysis of distributed systems, networking, and peer-to-peer systems.

For Further Seminar Info:
, or visit http://www.pdl.cmu.edu/SDI/