An Efficient Broadcast Algorithm in Distributed Hash Table Under Churn

Abstract

Broadcasting has become a basic service that adds to existing DHT systems the ability to search using arbitrary queries as well as disseminate/collection global information. However, the phenomenon of system churn, a continuous process of needs joining and leaving the networks, degrades the broadcast performance of DHT systems and adversely impact the performance of applications built on top of them. In this paper, we present an efficient algorithm for performing a broadcast operation in DHT systems under churn. It is suitable for most DHT systems such as Chord, Tapestry, etc. Through the proposed algorithm, nodes in DHT system could perform broadcast operation rapidly, and will not send any redundant message. Furthermore, it ensures full coverage of the nodes in the system even when the churn rate is high. The algorithm is validated and evaluated through simulations.