Self-correcting Broadcast in Distributed Hash Tables

A. Ghodsi, L.O. Alima, S. El-Ansary, P. Brand, and S. Haridi (Sweden)


Distributed Algorithms, Distributed Hash Tables, GroupCommunication, Peer-to-Peer .


We present two broadcast algorithms that can be used on top of distributed hash tables (DHTs) to perform group communication and arbitrary queries. Unlike other P2P group communication mechanisms, which either embed extra information in the DHTs or use random overlay net works, our algorithms take advantage of the structured DHT overlay networks without maintaining additional in formation. The proposed algorithms do not send any re dundant messages. Furthermore the two algorithms en sure 100% coverage of the nodes in the system even when routing information is outdated as a result of dynamism in the network. The first algorithm performs some correction of outdated routing table entries with a low cost of cor rection traffic. The second algorithm exploits the nature of the broadcasts to extensively update erroneous routing information at the cost of higher correction traffic. The algorithms are validated and evaluated in our stochastic distributed-algorithms simulator.

Important Links:

Go Back