Self-Correcting Broadcast in Distributed Hash Tables

Ghodsi, Ali and Onana Alima, Luc and El-Ansary, Sameh and Brand, Per and Haridi, Seif (2003) Self-Correcting Broadcast in Distributed Hash Tables. In: 15th International Conference Parallel and Distributed Computing and Systems (PDCS'2003), 2003, Marina Del Rey, California.


Official URL:


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 networks, our algorithms take advantage of the structured DHT overlay networks without maintaining additional information. The proposed algorithms do not send any redundant messages. Furthermore the two algorithms ensure 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 correction 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.

Item Type:Conference or Workshop Item (Paper)
ID Code:257
Deposited By:DSL Researcher
Deposited On:30 Jan 2006
Last Modified:18 Nov 2009 15:55

Repository Staff Only: item control page