research-article

On spreading recommendations via social gossip

Authors:

Yaacov Fernandess,

Dahlia MalkhiAuthors Info & Claims

SPAA '08: Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures

Pages 91 - 97

https://doi.org/10.1145/1378533.1378547

Published: 14 June 2008 Publication History

Abstract

This paper introduces and analyzes a variant of distributed gossip which is motivated by the sharing of recommendations in a social network. The social settings bear two implications on gossip. First, rumors fade after a few hops, and so does our gossip mechanism. Second, users require a rumor to be substantiated by multiple, independent sources in order to adopt it. Consequently, in our social gossip a message is adopted only when it is received over a threshold of independent paths. Social gossip is a new, highly relevant and practically motivated variant of distributed gossip, whose analysis contributes to the fundamental theory of distributed algorithms.

References

[1]

Nocturnal. http://research.microsoft.com/research/sv/Nocturnal/.

[2]

. Kempe, J. Kleinberg, and É. Tardos. Maximizing the Spread of Influence Through a Social Network. In KDD'03: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137--146, New York, NY, USA, 2003. ACM Press.

Digital Library

[3]

. M. Minsky and F. B. Schneider. Tolerating Malicious Gossip. Distributed Computing, 16(1):49--68, 2003.

Digital Library

[4]

. Malkhi, E. Pavlov, and Y. Sella. Optimal Unconditional Information Diffusion. In Proceedings of the 15th International Symposium on DIStributed Computing, 2001.

Digital Library

[5]

. Malkhi, M. K. Reiter, O. Rodeh, and Y. Sella. Efficient Update Diffusion in Byzantine Environments. In Proceedings of the 20th IEEE Symposium on Reliable Distributed Systems, Washington, DC, USA, 2001. IEEE Computer Society.

[6]

. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenkcr, H. Sturgis, D. Swinehart, and D. Terry. Epidemic Algorithms for Replicated Database Maintenance. In PODC'87: Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, pages 1--12, New York, NY, USA, 1987. ACM Press.

Digital Library

[7]

. J. Watts and S. H. Strogatz. Collective dynamics of Şsmall-worldŤ networks. Nature, pages 440--442, 1998.

[8]

. Kleinberg. The Small-world Phenomenon: An Algorithmic Perspective. In Proceedings of the 32nd ACM Symposium on Theory of Computing, 2000.

Digital Library

[9]

. D. Flaxman. Expansion and Lack Thereof in Randomly Perturbed Graphs. Technical report, 2006. Manuscript under submission.

[10]

. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Gossip Algorithms: Design, Analysis and Applications. In Proceedings of IEEE INFOCOM, 2005.

[11]

. Mosk-Aoyama and D. Shah. Computing Separable Functions via Gossip. In PODC'06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pages 113--122, New York, NY, USA, 2006. ACM Press.

Digital Library

[12]

. Lidl, J. Osborne, and J. Malcome. Drinking from the Firehose: Multicast Usenet News. In Proceedings of the Usenix Winter Conference, pages 33--45, January 1994.

Digital Library

[13]

. D. Birrell, R. Levin, R. M. Needham, and M. D. Schroeder. Grapevine, an Exercise in Distributed Computing. Communications of the ACM, 25(4):260--274, 1982.

Digital Library

[14]

. Haas, J. Y. Halpern, and L. Li. Gossip-based ad hoc Routing. In Proceedings of IEEE INFOCOM, June 2002.

[15]

. van Renesse, Y. Minsky, and M. Hayden. A Gossip-style Failure Detection Service. In Proceedings of Middleware, 1998.

Digital Library

[16]

.van Renesse. Scalable and Secure Resource Location. In Proceedings of IEEE Hawaii International Conference on System Sciences, January 2000.

Digital Library

[17]

. Th. Eugster, R. Guerraoui, S. B. Handurukande, P. Kouznetsov, and A.-M. Kermarrec. Lightweight Probabilistic Broadcast. ACM Trans. Comput. Syst., 21(4):341--374, 2003.

Digital Library

[18]

. J. Ganesh, A. Kermarrec, and L. Massoulié. Peer-to-peer Membership Management for Gossip-based Protocols. IEEE Transactions on Computers, 52(2), February 2003.

Digital Library

[19]

. Voulgaris, D. Gavidia, and M. van Steen. Cyclon: Inexpensive Membership Management for Unstructured p2p overlays. J. Network Syst. Manage., 13(2), 2005.

[20]

. Guerraoui, S. B. Handurukande, and A.-M. Kermarrec. GosSkip: a Gossip-based Structured Overlay Network for Efficient Content-based Filtering. Technical report, 2004.

[21]

. Fernandess and D. Malkhi. On Collaborative Content Distribution using Multi-message Gossip. In IPDPS: IEEE International Parallel and Distributed Processing Symposium. IEEE, April 2006.

Digital Library

[22]

. Karp, C. Schindelhauer, S. Shenker, and B. Vöcking. Randomized Rumor Spreading. In FOCS'00: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, page 565, Washington, DC, USA, 2000.

Digital Library

[23]

. Malkhi, Y. Mansour, and M. K. Reiter. On Diffusing Updates in a Byzantine Environment. In Proceedings of the 18th IEEE Symposium on Reliable Distributed Systems, page 134, Washington, DC, USA, 1999. IEEE Computer Society.

Digital Library

[24]

. Feldman and J. Chuang. Overcoming Free-riding Behavior in Peer-to-peer Systems. SIGecom Exch., 5(4):41--50, 2005.

Digital Library

[25]

. Cheng and E. Friedman. Sybilproof Reputation Mechanisms. In P2PECON'05: Proceeding of the 2005 ACM SIGCOMM workshop on Economics of peer-to-peer systems, pages 128--132, New York, NY, USA, 2005. ACM Press.

Digital Library

[26]

. Feldman, K. Lai, I. Stoica, and J. Chuang. Robust Incentive Techniques for Peer-to-peer Networks. In P2PECON'04: Proceeding of the 2004 ACM SIGCOMM workshop on Economics of peer-to-peer systems, pages 102--111, New York, NY, USA, 2004. ACM Press.

Digital Library

[27]

. Abrams and R. Mcgrew. Keeping Peers Honest in Eigentrust. In P2PECON'04: Proceeding of the 2004 ACM SIGCOMM workshop on Economics of peer-to-peer systems, pages 102--111, New York, NY, USA, 2004. ACM Press.

[28]

. D. Kamvar, M. T. Schlosser, and H. Garcia-Molina. The Eigentrust Algorithm for Reputation Management in p2p Networks. In WWW'03: Proceedings of the 12th international conference on World Wide Web, pages 640--651, New York, NY, USA, 2003. ACM Press.

Digital Library

[29]

. Mui, M. Mohtashemi, and A. Halberstadt. A Computational Model of Trust and Reputation for e-businesses. In HICSS'02: Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 7, page 188, Washington, DC, USA, 2002. IEEE Computer Society.

Digital Library

[30]

. Resnick, K. Kuwabara, R. Zeckhauser, and E. Friedman. Reputation Systems. Commun. ACM, 43(12):45--48, 2000.

Digital Library

[31]

. R. Douceur. The Sybil Attack. In IPTPS'01: Revised Papers from the First International Workshop on Peer-to-Peer Systems, pages 251--260, London, UK, 2002. Springer-Verlag.

Digital Library

[32]

. A. Bazzi and G. Konjevod. On the Establishment of Distinct Identities in Overlay Networks. In PODC'05: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, pages 312--320, New York, NY, USA, 2005. ACM Press.

Digital Library

[33]

. F. Kaashoek G. Danezis, C. Lesniewski-Laas and R. Anderson. Sybil-resistant DHT Routing. In In European Symposium On Research In Computer Security, pages 305--318, September 2005.

Digital Library

[34]

. Yu, M. Kaminsky, P. B. Gibbons, and A. Flaxman. Sybilguard: Defending Against Sybil Attacks via Social Networks. In SIGCOMM'06: Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, pages 267--278, New York, NY, USA, 2006. ACM Press.

Digital Library

[35]

. Maniatis, M. Roussopoulos, T.J. Giuli, D. S. H. Rosenthal, and M. Baker. The Lockss Peer-to-peer Digital Preservation System. ACM Trans. Comput. Syst., 23(1):2--50, 2005.

Digital Library

[36]

. Walsh and E. Sirer. Experience with an Object Reputation System for Peer-to-peer Filesharing. In NSDI'06: Proceedings of the 3rd conference on 3rd Symposium on Networked Systems Design & Implementation, pages 1--1, Berkeley, CA, USA, 2006. USENIX Association.

Digital Library

[37]

. Walsh and E. Sirer. Fighting peer-to-peer Spam and Decoys with Object Reputation. In P2PECON'05: Proceeding of the 2005 ACM SIGCOMM workshop on Economics of peer-to-peer systems, pages 138--143, New York, NY, USA, 2005. ACM.

Digital Library

Cited By

Nayak AHosseinalipour SDai H(2019)Smart Information Spreading for Opinion Maximization in Social NetworksIEEE INFOCOM 2019 - IEEE Conference on Computer Communications10.1109/INFOCOM.2019.8737538(2251-2259)Online publication date: Apr-2019
https://doi.org/10.1109/INFOCOM.2019.8737538
Georgiou CGilbert SKowalski D(2019)Confidential gossipDistributed Computing10.1007/s00446-019-00367-xOnline publication date: 3-Dec-2019
https://doi.org/10.1007/s00446-019-00367-x
Xuan QZhang ZFu CHu HFilkov V(2018)Social Synchrony on Complex NetworksIEEE Transactions on Cybernetics10.1109/TCYB.2017.269699848:5(1420-1431)Online publication date: May-2018
https://doi.org/10.1109/TCYB.2017.2696998
Show More Cited By

Index Terms

On spreading recommendations via social gossip
1. Networks
  1. Network protocols

Recommendations

Algebraic gossip: a network coding approach to optimal multiple rumor mongering
Special issue on networking and information theory

The problem of simultaneously disseminating k messages in a large network of n nodes, in a decentralized and distributed manner, where nodes only have knowledge about their own contents, is studied. In every discrete time-step, each node selects a ...
On collaborative content distribution using multi-message gossip

We study epidemic schemes in the context of collaborative data delivery. In this context, multiple chunks of data reside at different nodes, and the challenge is to simultaneously deliver all chunks to all nodes. Here we explore the inter-operation ...
An efficient gossip based overlay network for peer-to-peer networks
ICUFN'09: Proceedings of the first international conference on Ubiquitous and future networks

Overlay networks have emerged as a means to enhance end-to-end application performance and availability. Network topology plays an important role in utilizing resources in Peer-to-peer systems. Epidemic algorithms are potentially effective solutions for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '08: Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures

June 2008

380 pages

ISBN:9781595939739

DOI:10.1145/1378533

General Chair:
Friedhelm Meyer auf der Heide
University of Paderborn, Germany
,
Program Chair:
Nir Shavit
Tel-Aviv University, Israel, and Sun Labs, USA

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPAA08

Sponsor:

SPAA08: 20th ACM Symposium on Parallelism in Algorithms and Architectures

June 14 - 16, 2008

Munich, Germany

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
444
Total Downloads

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

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nayak AHosseinalipour SDai H(2019)Smart Information Spreading for Opinion Maximization in Social NetworksIEEE INFOCOM 2019 - IEEE Conference on Computer Communications10.1109/INFOCOM.2019.8737538(2251-2259)Online publication date: Apr-2019
https://doi.org/10.1109/INFOCOM.2019.8737538
Georgiou CGilbert SKowalski D(2019)Confidential gossipDistributed Computing10.1007/s00446-019-00367-xOnline publication date: 3-Dec-2019
https://doi.org/10.1007/s00446-019-00367-x
Xuan QZhang ZFu CHu HFilkov V(2018)Social Synchrony on Complex NetworksIEEE Transactions on Cybernetics10.1109/TCYB.2017.269699848:5(1420-1431)Online publication date: May-2018
https://doi.org/10.1109/TCYB.2017.2696998
Loh PLubetzky E(2013)Stochastic coalescence in logarithmic timeThe Annals of Applied Probability10.1214/11-AAP83223:2Online publication date: 1-Apr-2013
https://doi.org/10.1214/11-AAP832
Dolev SLiba OSchiller E(2013)Self-stabilizing Byzantine Resilient Topology Discovery and Message DeliveryRevised Selected Papers of the First International Conference on Networked Systems - Volume 785310.1007/978-3-642-40148-0_4(42-57)Online publication date: 2-May-2013
https://dl.acm.org/doi/10.1007/978-3-642-40148-0_4
Loh PLubetzky E(2012)Stochastic coalescence in logarithmic timeProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095162(541-550)Online publication date: 17-Jan-2012
https://dl.acm.org/doi/10.5555/2095116.2095162
Wang BYao YHou BLiao DChen D(2010)Knowledge Aggregation in Human Flesh SearchProceedings of the 2010 IEEE/ACM Int'l Conference on Green Computing and Communications & Int'l Conference on Cyber, Physical and Social Computing10.1109/GreenCom-CPSCom.2010.145(825-830)Online publication date: 18-Dec-2010
https://dl.acm.org/doi/10.1109/GreenCom-CPSCom.2010.145
Junapudi VUdgata GUdgata S(2010)Study of diffusion models in an academic social networkProceedings of the 6th international conference on Distributed Computing and Internet Technology10.1007/978-3-642-11659-9_29(267-278)Online publication date: 15-Feb-2010
https://dl.acm.org/doi/10.1007/978-3-642-11659-9_29
Wang BHou BYao YYan L(2009)Human Flesh Search Model Incorporating Network Expansion and GOSSIP with FeedbackProceedings of the 2009 13th IEEE/ACM International Symposium on Distributed Simulation and Real Time Applications10.1109/DS-RT.2009.36(82-88)Online publication date: 25-Oct-2009
https://dl.acm.org/doi/10.1109/DS-RT.2009.36
De Choudhury MSundaram HJohn ASeligmann D(2009)Social SynchronyProceedings of the 2009 International Conference on Computational Science and Engineering - Volume 0410.1109/CSE.2009.439(151-158)Online publication date: 29-Aug-2009
https://dl.acm.org/doi/10.1109/CSE.2009.439
Show More Cited By

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 Table of Contents