Evaluation of alternatives for the broadcast operation in Kademlia under churn

During recent years, considerable effort has been devoted to the enhancement of Distributed Hash Table (DHT) systems with broadcasting capabilities. Such systems typically provide individual node routing but a broadcast primitive is required for functionalities such as information dissemination or data aggregation. Broadcasting can also be used as the basis for partial keyword searches. Little work has however specifically addressed Kademlia, a well known DHT, used in real applications. Our work exposes the particularities of this system, notably its XOR-based distance metrics, and analytically studies what broadcasting techniques can be applied to it. A model that estimates node coverage as a function of the probability that individual messages reach their destination has been also developed. For validation, several broadcasting algorithms have been implemented and comprehensively evaluated, considering node coverage, messages to nodes ratio, latency and imbalance factor. Moreover, several techniques are proposed to enhance the bare protocols when adverse circumstances such as churn and failure rate conditions are present. These include redundancy, resubmissions or flooding, and also combinations of those. All have been implemented and fully tested. An analysis of the strengths and weaknesses of algorithms and additional techniques, and a discussion on the choices and compromises to make, depending on system characteristics or application priorities, is finally presented.