Gossip

Gossip

When you have a ham­mer, eve­ry­thing looks like a nail. For a whi­le, I had a ”gos­sip” ham­mer: eve­ry pro­blem loo­ked sol­va­ble throu­gh a gos­sip pro­to­col. Clearly this was not true, but it is inte­re­sting to see how many pro­blems can be sol­ved with the same algo­ri­th­mic sche­me. So far:

  • entro­py-reduc­tion pro­to­cols for the com­pu­ta­tion of a lar­ge set of aggre­ga­te func­tions, inclu­ding maxi­mum and mini­mum, ave­ra­ge, sum, pro­duct, geo­me­tric mean, varian­ce, ran­king, etc [DSN04] [ICDCS04] [TOCS05] [Selfman08] [ComCom10]
  • size esti­ma­tion [P2P09]
  • load balan­cing [LNCS04]
  • pro­to­cols for orga­ni­zing and mana­ging struc­tu­red topo­lo­gies like super-peer based net­works [P2P04] [Selfman06] [TNSM07]
  • gene­ric topo­lo­gy mana­ge­ment pro­to­cols [TMan09]
  • pro­to­cols for boo­tstrap­ping DHT topo­lo­gies like Chord from scratch [P2P05] [IWDDS06]
  • sli­cing pro­to­col to obtain a ”sli­ce” of nodes sati­sfy­ing a given con­di­tion [Hotp2p08]
  • sche­du­ling in P2P video strea­ming [IWSOS09]
  • fire­fly-inspi­red heart­beat syn­chro­ni­sa­tion [SASO07]
  • top‑k com­pu­ta­tion  [Computing13] [EuroPar14]

A sum­ma­ry of the poten­tia­li­ty of this approach can be found in [IDC08]; inter­di­sci­pli­na­ry aspec­ts of gos­sip are discus­sed in [OSR07]. If you are loo­king for a sur­vey of the topic, I have been asked to wri­te an arti­cle for the Wiley Encyclopedia of Electrical and Electronics Engineering about gos­sip [Wiley17].

[DSN04]   Alberto Montresor, Márk Jelasity, and Ozalp Babaoglu. Robust aggre­ga­tion pro­to­cols for lar­ge-sca­le over­lay net­works. In Proc. of the 2004 Int. Conference on Dependable Systems and Networks (DSN’04), pages 19–28. IEEE Computer Society, Florence, Italy, June 2004. [PDF], [Bibtex].

[ICDCS04]   Márk Jelasity and Alberto Montresor. Epidemic-sty­le proac­ti­ve aggre­ga­tion in lar­ge over­lay net­works. In Proc. of the 24th Int. Conference on Distributed Computing Systems (ICDCS’04), pages 102–109. IEEE Computer Society, Tokyo, Japan, March 2004. [PDF], [Bibtex].

[LNCS04]   Márk Jelasity, Alberto Montresor, and Ozalp Babaoglu. A modu­lar para­digm for buil­ding self-orga­ni­zing peer-to-peer appli­ca­tions. In Engineering Self-Organising Systems: Nature-Inspired Approaches to Software Engineering, num­ber 2977 in Lecture Notes in Artificial Intelligence, pages 265–282. Springer-Verlag, April 2004. [PDF], [Bibtex] .

[P2P04]   Alberto Montresor. A robu­st pro­to­col for buil­ding super­peer over­lay topo­lo­gies. In Proc. of the 4th Int. Conference on Peer-to-Peer Computing, pages 202–209. IEEE, Zurich, Switzerland, August 2004. [PDF], [Bibtex] .

[TOCS05]   Márk Jelasity, Alberto Montresor, and Ozalp Babaoglu. Gossip-based aggre­ga­tion in lar­ge dyna­mic net­works. ACM Trans. Comput. Syst., 23 (1):219–252, August 2005. [PDF], [Bibtex].

[P2P05]   Alberto Montresor, Márk Jelasity, and Ozalp Babaoglu. Chord on demand. In Proc. of the 5th Int. Conference on Peer-to-Peer Computing (P2P’05), pages 87–94. IEEE, Konstanz, Germany, August 2005. [PDF] , [Bibtex].

[IWDDS06]   Márk Jelasity, Alberto Montresor, and Ozalp Babaoglu. The boo­tstrap­ping ser­vi­ce. In Proc. of Int. ICDCS Workshop on Dynamic Distributed Systems (ICDCS-IWDDS’06). IEEE Computer Society, Lisboa, Portugal, July 2006. [PDF], [Bibtex].

[SelfMan06]   Gian Paolo Jesi, Alberto Montresor, and Ozalp Babaoglu. Proximity-aware super­peer over­lay topo­lo­gies. In Proc. of SelfMan’06, volu­me 3996 of Lecture Notes in Computer Science, pages 43–57. Springer-Verlag, Dublin, Ireland, June 2006. Best paper award. [PDF] , [Bibtex].

[TNSM07]   Gian Paolo Jesi, Alberto Montresor, and Ozalp Babaoglu. Proximity-aware super­peer over­lay topo­lo­gies. IEEE Transactions on Network and Service Management, 4(2):74–83, September 2007. [PDF], [Bibtex].

[SASO07]   Ozalp Babaoglu, Toni Binci, Márk Jelasity, and Alberto Montresor. Firefly-inspi­red heart­beat syn­chro­ni­za­tion in over­lay net­works. In Proc. of the First IEEE Int. Conference on Self-Adaptive and Self-Organizing Systems (SASO’07). IEEE, Boston, MA, USA, July 2007. [PDF], [Bibtex].

[OSR07]   Paolo Costa, Vincent Gramoli, Márk Jelasity, Gian Paolo Jesi, Erwan Le Merrer, Alberto Montresor, and Leonardo Querzoni. Exploring the inter­di­sci­pli­na­ry con­nec­tions of gos­sip-based systems. SIGOPS Oper. Syst. Rev., 41(5):51–60, October 2007. ISSN 0163–5980. [PDF], [Bibtex] .

[IDC08]   Alberto Montresor. Intelligent gos­sip. In 2nd Int. Symposium on Intelligent Distributed Computing (IDC’08). Springer, Catania, Italy, September 2008. Invited paper. [PDF], [Bibtex].

[Selfman08]   Alberto Montresor, Márk Jelasity, and Ozalp Babaoglu. Decentralized ran­king in lar­ge-sca­le over­lay net­works. In Proc. of the 1st IEEE Selfman SASO Workshop, pages 208–213. IEEE, Isola di San Servolo, Venice, Italy, November 2008. An exten­ded ver­sion of the paper can be found here . [PDF], [Bibtex].

[HOTP2P08]   Alberto Montresor and Roberto Zandonati. Absolute sli­cing in peer-to-peer systems. In Proc. of the 5th Int. Workshop on Hot Topics in Peer-to-Peer Systems (HotP2P’08). IEEE, Miami, FL, USA, April 2008. [PDF], [Bibtex].

[IWSOS09]   Luca Abeni and Alberto Montresor. Scheduling in p2p strea­ming: From algo­ri­thms to pro­to­cols. In Thrasyvoulos Spyropoulos and Karin Anna Hummel, edi­tors, Proc. of the 4th IFIP Int. Workshop on Self-Organizing Systems (IWSOS’09), volu­me 5918 of Lecture Notes in Computer Science, pages 201–206. Springer, Zurich, Switzerland, December 2009. ISBN 978–3–642–10864–8. [PDF], [Bibtex].

[P2P09]   Alber­to Montresor and Ali Ghodsi. Towards robu­st peer coun­ting. In Proc. of the 9th Int. Conference on Peer-to-Peer (P2P’09), pages 143–146. IEEE, Seattle, WA, September 2009. [PDF], [Bibtex].

[ComNet09]   Márk Jelasity, Alberto Montresor, and Ozalp Babaoglu. T‑Man: Gossip-based fast over­lay topo­lo­gy con­struc­tion. Computer Networks, 53 (13):2321–2339, 2009. [PDF], [Bibtex].

[ComCom10]   Alessio Guerrieri, Iacopo Carreras, Francesco De Pellegrini, Daniele Miorandi, and Alberto Montresor. Distributed esti­ma­tion of glo­bal para­me­ters in delay–tolerant net­works. Computer Communications, 33 (13):1472–1482, August 2010.[PDF], [Bibtex].

[Computing13]   Jan Sacha and Alberto Montresor. Identifying fre­quent items in distri­bu­ted data sets. Computing, 95(4):289–307, 2013. [PDF], [Bibtex] .

[EuroPar14]   Alessio Guerrieri, Alberto Montresor, and Yannis Velegrakis. Top‑k item iden­ti­fi­ca­tion on dyna­mic and distri­bu­ted data­se­ts. In Proc. of the 20th International Conference on Parallel Processing, EuroPar’14. Springer, 2014. [PDF], [Bibtex].

[Wiley17]   Alberto Montresor. Gossip and epi­de­mic pro­to­col. Wiley Encyclopedia of Electrical and Electronics Engineering, 1, 2017. [PDF], [Bibtex].

Scroll to top