Minimizing churn in distributed systems

P. Brighten Godfrey, Scott Shenker, Ion Stoica

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)147-158
Number of pages12
JournalComputer Communication Review
Issue number4
StatePublished - Oct 2006
Externally publishedYes


  • Churn
  • DHT
  • Multicast
  • Node selection

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications


Dive into the research topics of 'Minimizing churn in distributed systems'. Together they form a unique fingerprint.

Cite this