On routing in Distributed Hash Tables: Is reputation a shelter from malicious behavior and churn?

Recently, it has been argued that reputation mechanisms could be used to improve routing by conditioning next-hop decisions to the past behavior of peers. However, churn may severely hinder the applicability of reputations mechanisms. In particular, short peer lifetimes imply that reputations are typically generated from a small number of transactions and are few reliable. To examine how high rates of churn affect reputation systems, we present an analytical model to study the potential damage done by malicious peers together with churn. With our model, we show that it cannot be expected in general that reputations are reliable. We then analyze the impact of this result by proposing a new routing protocol for Chord. Mainly, the protocol exploits reputation to improve the decision about which neighbor select as next-hop peer. Our experimental results show that routing algorithms can obtain important benefits from reputation - even when peer lifetimes are short and the fraction of bad users is moderate.