More Web Proxy on the site http://driver.im/

research-article

Optimizing information flow in the gossip objects platform

Authors:

Ymir Vigfusson,

Deepak P. NatarajAuthors Info & Claims

ACM SIGOPS Operating Systems Review, Volume 44, Issue 2

Pages 71 - 76

https://doi.org/10.1145/1773912.1773930

Published: 14 April 2010 Publication History

Abstract

Gossip-based protocols are commonly used for diffusing information in large-scale distributed applications. GO (Gossip Objects) is a per-node gossip platform that we developed in support of this class of protocols. GO allows nodes to join multiple gossip groups without losing the appealing fixed bandwidth guarantee of gossip protocols, and the platform also optimizes latency in a principled manner. Our algorithm is based on the observations that multiple rumors can often be squeezed into a single IP packet, and that indirect routing of rumors can speed up delivery. We formalize these observations and develop a theoretical analysis of this algorithm. We have also implemented GO, and studied the effectiveness of the algorithm by comparing it to the more standard random dissemination gossip strategy.

References

[1]

L. Alvisi, J. Doumen, R. Guerraoui, B. Koldehofe, H. C. Li, R. van Renesse, and G. Trédan. How robust are gossip-based communication protocols? Operating Systems Review, 41(5):14--18, 2007.

Digital Library

[2]

M. Balakrishnan, K. P. Birman, A. Phanishayee, and S. Pleisch. Ricochet: Lateral error correction for time-critical multicast. In NSDI. USENIX, 2007.

Digital Library

[3]

K. Birman, A.-M. Kermarrec, K. Ostrowski, M. Bertier, D. Dolev, and R. van Renesse. Exploiting gossip for self-management in scalable event notification systems. Distributed Event Processing Systems and Architecture Workshop (DEPSA), 2007.

Digital Library

[4]

K. P. Birman. Replication and fault-tolerance in the isis system. In SOSP, pages 79--86, 1985.

Digital Library

[5]

K. P. Birman, M. Hayden, O. Ozkasap, Z. Xiao, M. Budiu, and Y. Minsky. Bimodal multicast. ACM Transactions on Computer Systems, 17:41--88, 1998.

Digital Library

[6]

B. Carmeli, G. Gershinsky, A. Harpaz, N. Naaman, H. Nelken, J. Satran, and P. Vortman. High throughput reliable message dissemination. In SAC, pages 322--327, 2004.

Digital Library

[7]

B. F. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H.-A. Jacobsen, N. Puz, D. Weaver, and R. Yerneni. PNUTS: Yahoo!'s hosted data serving platform. Proc. VLDB Endow., 1(2):1277--1288, 2008.

Digital Library

[8]

G. Decandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazon's highly available key-value store. In SOSP, pages 205--220, New York, NY, USA, 2007. ACM Press.

Digital Library

[9]

S. Deering. Host Extensions for IP Multicasting. RFC 1112, August 1989.

[10]

A. J. Demers, D. H. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. E. Sturgis, D. C. Swinehart, and D. B. Terry. Epidemic algorithms for replicated database maintenance. In PODC, pages 1--12, 1987.

Digital Library

[11]

P. T. Eugster, P. A. Felber, R. Guerraoui, and A.-M. Kermarrec. The many faces of publish/subscribe. ACM Comput. Surv., 35(2):114--131, 2003.

Digital Library

[12]

IBM. WebSphere. http://www-01.ibm.com/software/webservers/appserv/was/, 2008.

[13]

M. Jelasity, R. Guerraoui, A.-M. Kermarrec, and M. van Steen. The peer sampling service: Experimental evaluation of unstructured gossip-based implementations. In Middleware, Toronto, Canada, October 2004.

Digital Library

[14]

R. Karp, C. Schindelhauer, S. Shenker, and B. Vocking. Randomized rumor spreading. In FOCS, pages 565--574, 2000.

Digital Library

[15]

D. Kempe, J. M. Kleinberg, and A. J. Demers. Spatial gossip and resource location protocols. In STOC, pages 163--172, 2001.

Digital Library

[16]

K. Ostrowski, K. Birman, D. Dolev, and J. H. Ahnn. Programming with live distributed objects. In J. Vitek, editor, ECOOP, volume 5142 of Lecture Notes in Computer Science, pages 463--489. Springer, 2008.

Digital Library

[17]

L. Rodrigues, U. D. Lisboa, S. Handurukande, J. Pereira, J. P. U. do Minho, R. Guerraoui, and A.-M. Kermarrec. Adaptive gossip-based broadcast. In DSN, pages 47--56, 2003.

[18]

R. van Renesse, K. P. Birman, and W. Vogels. Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining. ACM Trans. Comput. Syst., 21(2):164--206, May 2003.

Digital Library

[19]

R. van Renesse, Y. Minsky, and M. Hayden. A gossip-style failure detection service. Technical Report TR98-1687, August, 1998.

Digital Library

[20]

T. von Eicken, A. Basu, V. Buch, and W. Vogels. U-net: A user-level network interface for parallel and distributed computing. In SOSP, pages 40--53, 1995.

Digital Library

Cited By

Princehouse LChenchu RJiang ZBirman KFoster NSoulé R(2014)MiCAProceedings of the 28th European Conference on ECOOP 2014 --- Object-Oriented Programming - Volume 858610.1007/978-3-662-44202-9_26(644-669)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.1007/978-3-662-44202-9_26

Index Terms

Optimizing information flow in the gossip objects platform
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles

Recommendations

Efficient and Adaptive Epidemic-Style Protocols for Reliable and Scalable Multicast

Epidemic-style (gossip-based) techniques have recently emerged as a class of scalable and reliable protocols for peer-to-peer multicast dissemination in large process groups. However, popular implementations of epidemic-style dissemination suffer from ...
Gossip-based search selection in hybrid peer-to-peer networks: Research Articles
Recent Advances in Peer-to-Peer Systems and Security (P2P 2006)

We present GAB, a search algorithm for hybrid peer-to-peer networks, that is, networks that search using both flooding and a distributed hash table (DHT). GAB uses a gossip-style algorithm to collect global statistics about document popularity to allow ...
Topology Dissemination for Reliable One-Hop Distributed Hash Tables

Many distributed hash tables (DHTs) resolve lookups in O(\log n) hops, where n is the number of nodes. One-hop DHTs give lower lookup latencies and lower lookup failure rates. However, it is hard to maintain large, wide-area one-hop topologies. We ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGOPS Operating Systems Review

ACM SIGOPS Operating Systems Review Volume 44, Issue 2

April 2010

92 pages

ISSN:0163-5980

DOI:10.1145/1773912

Issue’s Table of Contents

Copyright © 2010 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 April 2010

Published in SIGOPS Volume 44, Issue 2

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
121
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Princehouse LChenchu RJiang ZBirman KFoster NSoulé R(2014)MiCAProceedings of the 28th European Conference on ECOOP 2014 --- Object-Oriented Programming - Volume 858610.1007/978-3-662-44202-9_26(644-669)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.1007/978-3-662-44202-9_26

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents