{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:35:53Z","timestamp":1750307753092,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2007,10,1]],"date-time":"2007-10-01T00:00:00Z","timestamp":1191196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGOPS Oper. Syst. Rev."],"published-print":{"date-parts":[[2007,10]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1317379.1317389","type":"journal-article","created":{"date-parts":[[2007,11,16]],"date-time":"2007-11-16T15:57:07Z","timestamp":1195228627000},"page":"61-66","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Exploiting the synergy between gossiping and structured overlays"],"prefix":"10.1145","volume":"41","author":[{"given":"Ali","family":"Ghodsi","sequence":"first","affiliation":[{"name":"Swedish Institute of Computer Science (SICS), Kista, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seif","family":"Haridi","sequence":"additional","affiliation":[{"name":"KTH---Royal Institute of Technology, Kista, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hakim","family":"Weatherspoon","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/945721.945729"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.1318567"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27860-3_10"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015467.1015507"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/312203.312207"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/972374.972397"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 2nd USENIX Symposium on Networked Systems Design and Implementation (NSDI'05)","author":"Castro M.","year":"2005","unstructured":"M. Castro , M. Costa , and A. Rowstron . Debunking Some Myths About Structured and Unstructured Overlays . In Proceedings of the 2nd USENIX Symposium on Networked Systems Design and Implementation (NSDI'05) , Boston, MA, USA , May 2005 . USENIX. M. Castro, M. Costa, and A. Rowstron. Debunking Some Myths About Structured and Unstructured Overlays. In Proceedings of the 2nd USENIX Symposium on Networked Systems Design and Implementation (NSDI'05), Boston, MA, USA, May 2005. USENIX."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11822035_3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/41840.41841"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/361179.361202"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS'03)","volume":"2735","author":"El-Ansary S.","year":"2003","unstructured":"S. El-Ansary , L. O. Alima , P. Brand , and S. Haridi . Efficient Broadcast in Structured P2P Netwoks . In Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS'03) , volume 2735 of Lecture Notes in Computer Science (LNCS), pages 304--314, Berkeley, CA, USA , 2003 . Springer-Verlag. S. El-Ansary, L. O. Alima, P. Brand, and S. Haridi. Efficient Broadcast in Structured P2P Netwoks. In Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS'03), volume 2735 of Lecture Notes in Computer Science (LNCS), pages 304--314, Berkeley, CA, USA, 2003. Springer-Verlag."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2004.1297243"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2003.1176982"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 15th International Conference, Parallel and Distributed Computing and Systems, Marina del Rey, CA, USA","author":"Ghodsi A.","year":"2003","unstructured":"A. Ghodsi , L. O. Alima , S. El-Ansary , P. Brand , and S. Haridi . Self-Correcting Broadcast in Distributed Hash Tables . In Proceedings of the 15th International Conference, Parallel and Distributed Computing and Systems, Marina del Rey, CA, USA , November 2003 . A. Ghodsi, L. O. Alima, S. El-Ansary, P. Brand, and S. Haridi. Self-Correcting Broadcast in Distributed Hash Tables. In Proceedings of the 15th International Conference, Parallel and Distributed Computing and Systems, Marina del Rey, CA, USA, November 2003."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 3rd International VLDB Workshop on Databases, Information Systems and Peer-to-Peer Computing (DBISP2P'05)","volume":"4125","author":"Ghodsi A.","year":"2005","unstructured":"A. Ghodsi , L. O. Alima , and S. Haridi . Symmetric Replication for Structured Peer-to-Peer Systems . In Proceedings of the 3rd International VLDB Workshop on Databases, Information Systems and Peer-to-Peer Computing (DBISP2P'05) , volume 4125 of Lecture Notes in Computer Science (LNCS), pages 74--85. Springer-Verlag , 2005 . A. Ghodsi, L. O. Alima, and S. Haridi. Symmetric Replication for Structured Peer-to-Peer Systems. In Proceedings of the 3rd International VLDB Workshop on Databases, Information Systems and Peer-to-Peer Computing (DBISP2P'05), volume 4125 of Lecture Notes in Computer Science (LNCS), pages 74--85. Springer-Verlag, 2005."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/863955.863998"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45172-3_15"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11734697_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1045658.1045666"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/977400.978026"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082469.1082470"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335325"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICON.2004.1409167"},{"key":"e_1_2_1_25_1","volume-title":"EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management. In 12th International Conference on Networks (ICON'04)","author":"Leong B.","year":"2004","unstructured":"B. Leong , B. Liskov , and E. Demaine . EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management. In 12th International Conference on Networks (ICON'04) , Singapore , November 2004 . IEEE Computer Society. B. Leong, B. Liskov, and E. Demaine. EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management. In 12th International Conference on Networks (ICON'04), Singapore, November 2004. IEEE Computer Society."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 2nd USENIX Symposium on Networked Systems Design and Implementation (NSDI'05)","author":"Li J.","year":"2005","unstructured":"J. Li , J. Stribling , R. Morris , and M. F. Kaashoek . Bandwidth-efficient management of DHT routing tables . In Proceedings of the 2nd USENIX Symposium on Networked Systems Design and Implementation (NSDI'05) , Boston, MA, USA , May 2005 . USENIX. J. Li, J. Stribling, R. Morris, and M. F. Kaashoek. Bandwidth-efficient management of DHT routing tables. In Proceedings of the 2nd USENIX Symposium on Networked Systems Design and Implementation (NSDI'05), Boston, MA, USA, May 2005. USENIX."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/646334.687817"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/571825.571857"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems (USITS'03)","author":"Manku G. S.","year":"2003","unstructured":"G. S. Manku , M. Bawa , and P. Raghavan . Symphony: Distributed Hashing in a Small World . In Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems (USITS'03) , Seattle, WA, USA , March 2003 . USENIX. G. S. Manku, M. Bawa, and P. Raghavan. Symphony: Distributed Hashing in a Small World. In Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems (USITS'03), Seattle, WA, USA, March 2003. USENIX."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/P2P.2005.4"},{"key":"e_1_2_1_31_1","volume-title":"http:\/\/www.p2psip.org","author":"PSIP.","year":"2006","unstructured":"P2 PSIP. http:\/\/www.p2psip.org , 2006 . P2PSIP. http:\/\/www.p2psip.org, 2006."},{"key":"e_1_2_1_32_1","volume-title":"http:\/\/www.ietf.org\/html.charters\/hip-charter.html","author":"Payload Host Identity","year":"2006","unstructured":"Host Identity Payload . http:\/\/www.ietf.org\/html.charters\/hip-charter.html , 2006 . Host Identity Payload. http:\/\/www.ietf.org\/html.charters\/hip-charter.html, 2006."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 5th International Workshop on Peer-to-Peer Systems (IPTPS'06)","author":"Pouwelse J. A.","year":"2006","unstructured":"J. A. Pouwelse , P. Garbacki , J. Wangand A. Bakker , J. Yang, A. Iosup, D. Epema, M. Reinders, M. van Steen, and H. J. Sips. Tribler: A social-based based peer to peer system . In Proceedings of the 5th International Workshop on Peer-to-Peer Systems (IPTPS'06) , February 2006 . J. A. Pouwelse, P. Garbacki, J. Wangand A. Bakker, J. Yang, A. Iosup, D. Epema, M. Reinders, M. van Steen, and H. J. Sips. Tribler: A social-based based peer to peer system. In Proceedings of the 5th International Workshop on Peer-to-Peer Systems (IPTPS'06), February 2006."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 2004 USENIX Annual Technical Conference (USENIX'04)","author":"Rhea S.","year":"2004","unstructured":"S. Rhea , D. Geels , T. Roscoe , and J. Kubiatowicz . Handling Churn in a DHT . In Proceedings of the 2004 USENIX Annual Technical Conference (USENIX'04) , Boston, MA, USA , June 2004 . USENIX. S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz. Handling Churn in a DHT. In Proceedings of the 2004 USENIX Annual Technical Conference (USENIX'04), Boston, MA, USA, June 2004. USENIX."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/646591.697650"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1306874.1307187"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/646334.687800"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2002.808407"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1659232.1659238"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10922-005-4441-x"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/11549468_125"}],"container-title":["ACM SIGOPS Operating Systems Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1317379.1317389","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1317379.1317389","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:39:17Z","timestamp":1750253957000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1317379.1317389"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10]]},"references-count":40,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2007,10]]}},"alternative-id":["10.1145\/1317379.1317389"],"URL":"https:\/\/doi.org\/10.1145\/1317379.1317389","relation":{},"ISSN":["0163-5980"],"issn-type":[{"type":"print","value":"0163-5980"}],"subject":[],"published":{"date-parts":[[2007,10]]},"assertion":[{"value":"2007-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}