On spreading recommendations via social gossip

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: David Kempe , Jon Kleinberg , Éva Tardos, Maximizing the spread of influence through a social network, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956769]
• 3: Yaron M. Minsky , Fred B. Schneider, Tolerating malicious gossip, Distributed Computing, v.16 n.1, p.49-68, February 2003 [doi>10.1007/s00446-002-0082-4]
• 4: Dahlia Malkhi , Elan Pavlov , Yaron Sella, Optimal Unconditional Information Diffusion, Proceedings of the 15th International Conference on Distributed Computing, p.63-77, October 03-05, 2001
• 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: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 7: . J. Watts and S. H. Strogatz. Collective dynamics of Şsmall-worldŤ networks. Nature, pages 440--442, 1998.
• 8: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 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: Damon Mosk-Aoyama , Devavrat Shah, Computing separable functions via gossip, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146401]
• 12: Kurt Lidl , Josh Osborne , Joseph Malcolm, Drinking from the firehose: multicast USENET news, Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference, p.5-5, January 17-21, 1994, San Francisco, California
• 13: Andrew D. Birrell , Roy Levin , Michael D. Schroeder , Roger M. Needham, Grapevine: an exercise in distributed computing, Communications of the ACM, v.25 n.4, p.260-274, April 1982 [doi>10.1145/358468.358487]
• 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.
• 16: Robbert Van Renesse, Scalable and Secure Resource Location, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 4, p.4012, January 04-07, 2000
• 17: P. Th. Eugster , R. Guerraoui , S. B. Handurukande , P. Kouznetsov , A.-M. Kermarrec, Lightweight probabilistic broadcast, ACM Transactions on Computer Systems (TOCS), v.21 n.4, p.341-374, November 2003 [doi>10.1145/945506.945507]
• 18: Ayalvadi J. Ganesh , Anne-Marie Kermarrec , Laurent Massoulié, Peer-to-Peer Membership Management for Gossip-Based Protocols, IEEE Transactions on Computers, v.52 n.2, p.139-149, February 2003 [doi>10.1109/TC.2003.1176982]
• 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.
• 22: R. Karp , C. Schindelhauer , S. Shenker , B. Vocking, Randomized rumor spreading, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.565, November 12-14, 2000
• 23: Dahlia Malkhi , Yishay Mansour , Michael K. Reiter, On Diffusing Updates in a Byzantine Environment, Proceedings of the 18th IEEE Symposium on Reliable Distributed Systems, p.134, October 18-21, 1999
• 24: Michal Feldman , John Chuang, Overcoming free-riding behavior in peer-to-peer systems, ACM SIGecom Exchanges, v.5 n.4, p.41-50, July, 2005 [doi>10.1145/1120717.1120723]
• 25: Alice Cheng , Eric Friedman, Sybilproof reputation mechanisms, Proceedings of the 2005 ACM SIGCOMM workshop on Economics of peer-to-peer systems, August 22-22, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080192.1080202]
• 26: Michal Feldman , Kevin Lai , Ion Stoica , John Chuang, Robust incentive techniques for peer-to-peer networks, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988788]
• 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: Sepandar D. Kamvar , Mario T. Schlosser , Hector Garcia-Molina, The Eigentrust algorithm for reputation management in P2P networks, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775242]
• 29: L. Mui , M. Mohtashemi , A. Halberstadt, A Computational Model of Trust and Reputation for E-businesses, Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 7, p.188, January 07-10, 2002
• 30: Paul Resnick , Ko Kuwabara , Richard Zeckhauser , Eric Friedman, Reputation systems, Communications of the ACM, v.43 n.12, p.45-48, Dec. 2000 [doi>10.1145/355112.355122]
• 31: John R. Douceur, The Sybil Attack, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.251-260, March 07-08, 2002
• 32: Rida A. Bazzi , Goran Konjevod, On the establishment of distinct identities in overlay networks, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073873]
• 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.
• 34: Haifeng Yu , Michael Kaminsky , Phillip B. Gibbons , Abraham Flaxman, SybilGuard: defending against sybil attacks via social networks, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 35: Petros Maniatis , Mema Roussopoulos , T. J. Giuli , David S. H. Rosenthal , Mary Baker, The LOCKSS peer-to-peer digital preservation system, ACM Transactions on Computer Systems (TOCS), v.23 n.1, p.2-50, February 2005 [doi>10.1145/1047915.1047917]
• 36: Kevin Walsh , Emin Gün Sirer, Experience with an object reputation system for peer-to-peer filesharing, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.1-1, May 08-10, 2006, San Jose, CA
• 37: Kevin Walsh , Emin Gün Sirer, Fighting peer-to-peer SPAM and decoys with object reputation, Proceedings of the 2005 ACM SIGCOMM workshop on Economics of peer-to-peer systems, August 22-22, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080192.1080204]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Theory

Keywords:
epidemic algorithms, gossip algorithms, message dissemination, randomized algorithms