Exploiting the Synergy Between Gossiping and Structured Overlays

Ghodsi, Ali and Haridi, Seif and Weatherspoon, Hakim (2007) Exploiting the Synergy Between Gossiping and Structured Overlays. ACM SIGOPS Operating Systems Review, 41 (5). pp. 61-66.



In this position paper we argue for exploiting the synergy between gossip-based algorithms and structured overlay networks (SON). These two strands of research have both aimed at building fault-tolerant, dynamic, self-managing, and large-scale distributed systems. Despite the common goals, the two areas have, however, been relatively isolated. We focus on three problem domains where there is an untapped potential of using gossiping combined with SONs. We argue for applying gossip-based membership for ring-based SONs---such as Chord and Bamboo---to make them handle partition mergers and loopy networks. We argue that small world SONs---such as Accordion and Mercury---are specifically well-suited for gossip-based membership management. The benefits would be better graph-theoretic properties. Finally, we argue that gossip-based algorithms could use the overlay constructed by SONs. For example, many unreliable broadcast algorithms for SONs could be augmented with anti-entropy protocols. Similarly, gossip-based aggregation could be used in SONs for network size estimation and load-balancing purposes.

Item Type:Article
Uncontrolled Keywords:distributed hash tables, gossip-based algorithms, structured overlay networks
ID Code:2641
Deposited By:Vicki Carleson
Deposited On:14 Apr 2009
Last Modified:18 Nov 2009 16:12

Repository Staff Only: item control page