Exploring the interdisciplinary connections of gossip-based systems

ABSTRACT

In recent years the labels "gossip" and "gossip-based" have been applied to an increasingly general class of algorithms, including approaches to information aggregation, overlay network management and clock synchronization. These algorithms are intuitively similar, irrespective of their purpose. Their distinctive features include relying on local information, being round-based and relatively simple, and having a bounded information transmission and processing complexity in each round. Our position is that this class can and should be significantly extended to involve algorithms from other disciplines that share the same or similar distinctive features, like certain parallel numerical algorithms, routing protocols, bio-inspired algorithms and cellular automata, to name but a few. Such a broader perspective would allow us to import knowledge and tools to design and understand gossip-based distributed systems, and we could also export accumulated knowledge to re-interpret some of the problems in other disciplines, such as vehicular traffic control. In this position paper we describe a number of areas that show parallels with gossip protocols. These example areas will hopefully serve as inspiration for future research. In addition, we believe that comparisons with other fields also helps clarify the definition of gossip protocols and represents a necessary first step towards an eventual formal definition.

REFERENCES

• 1: BMW Connected Drive, July 2004. http://www.connected-drive.de.
• 2: R. Axelrod. The Evolution of Cooperation. Basic books, New York, US, 1984.
• 3: Ozalp Babaoglu , Toni Binci , Mark Jelasity , Alberto Montresor, Firefly-inspired Heartbeat Synchronization in Overlay Networks, Proceedings of the First International Conference on Self-Adaptive and Self-Organizing Systems, p.77-86, July 09-11, 2007 [doi>10.1109/SASO.2007.25]
• 4: Zhaojun Bai , James Demmel , Jack Dongarra , Axel Ruhe , Henk van der Vorst, Templates for the solution of algebraic eigenvalue problems: a practical guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 5: R. Baldoni, A. Corsaro, L. Querzoni, S. Scipioni, and S. Tucci-Piergiovanni. An adaptive coupling-based algorithm for internal clock synchronization of large scale dynamic systems. Technical report, MidLab 2/07 -- Università degli Studi di Roma "La Sapienza", 2007.
• 6: R. Beraldi, L. Querzoni, and R. Baldoni. A hint-based probabilistic protocol for unicast communications in manets. Ad Hoc Networks, 4(5):547--566, 2006.
• 7: H. J. Blok and B. Bergersen. Synchronous versus asynchronous updating in the "game of life". Phys. Rev. E, 59:3876--9, 1999. http://rikblok.shorturl.com/lib/blok99.html.
• 8: M. Brunato, R. Battiti, and A. Montresor. GOSH! Gossiping Optimization Search Heuristics. In Proceedings of the Learning and Intelligent Optimization Workshop (LION 2007), Andalo, Italy, 2007.
• 9: B. Bullnheimer, R. Hartl, and C. Strauss. An Improved Ant System Algorithm for the Vehicle Routing Problem. Annals of Operations Research, 89:319--328, 1999.
• 10: G. D. Caro and M. Dorigo. AntNet: Distributed Stigmergetic Control for Communications Networks. Journal of Artificial Intelligence Research (JAIR), 9:317--365, 1998.
• 11: B. Cohen. Incentives Build Robustness in BitTorrent. In Proceedings of the 1^st Workshop on Economics of Peer-to-Peer Systems, Berkeley, CA, USA, 2003.
• 12: 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]
• 13: Matthijs den Besten , Thomas Stützle , Marco Dorigo, Ant Colony Optimization for the Total Weighted Tardiness Problem, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.611-620, September 18-20, 2000
• 14: J. L. Deneubourg, S. Aron, S. Goss, and J. M. Pasteels. The self-organizing exploratory pattern of the argentine ant. Journal of Insect Behavior, 3:159--168, 1990.
• 15: G. Di Caro, F. Ducatelle, and L. Gambardella. AntHocNet: An Adaptive Nature-inspired Algorithm for Routing in Mobile Ad Hoc Networks. European Transactions on Telecommunications, 15(4), 2005.
• 16: Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
• 17: Marco Dorigo , Gianni Di Caro, The ant colony optimization meta-heuristic, New ideas in optimization, McGraw-Hill Ltd., UK, Maidenhead, UK, 1999
• 18: M. Felegyhazi and J. P. Hubaux. Game theory in wireless networks: A tutorial. Technical report, EPFL, 2006.
• 19: Antonio Fernandez , Vincent Gramoli , Ernesto Jimenez , Anne-Marie Kermarrec , Michel Raynal, Distributed Slicing in Dynamic Systems, Proceedings of the 27th International Conference on Distributed Computing Systems, p.66, June 25-27, 2007 [doi>10.1109/ICDCS.2007.102]
• 20: A. Festag, H. Fußler, H. Hartenstein, A. Sarma, and R. Schmitz. FLEETNET: Bringing car-to-car communication into the real world. Computer, 4(L15):16.
• 21: Gary William Flake, The computational beauty of nature, MIT Press, Cambridge, MA, 1998
• 22: P. P. Grassé. Les Insectes Dans Leur Univers. Ed. du Palais de la decouverte, Paris, France, 1946.
• 23: N. W. Group. Routing information protocol. rfc 1058, 1988.
• 24: N. W. Group. Rip version 2. rfc 2453, 1998.
• 25: W. J. Gutjahr. On the finite-time dynamics of ant colony optimization. Methodology And Computing In Applied Probability, 8(1):105--133, 2006.
• 26: Zygmunt J. Haas , Joseph Y. Halpern , Li Li, Gossip-based ad hoc routing, IEEE/ACM Transactions on Networking (TON), v.14 n.3, p.479-491, June 2006 [doi>10.1109/TNET.2006.876186]
• 27: R. Hadji, M. Rahoual, E. Talbi, and V. Bachelet. Ant colonies for the set covering problem. In In Proceedings of ANTS2000: From Ant Colonies to Artificial Ants, pages 63--66, Bruxelles, 2000.
• 28: David Hales , Stefano Arteconi, SLACER: A Self-Organizing Protocol for Coordination in Peer-to-Peer Networks, IEEE Intelligent Systems, v.21 n.2, p.29-35, March 2006 [doi>10.1109/MIS.2006.35]
• 29: Joseph Y. Halpern , Barbara Simons , Ray Strong , Danny Dolev, Fault-tolerant clock synchronization, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.89-102, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806739]
• 30: K. Iwanicki, M. van Steen, and S. Voulgaris. Gossip-based clock synchronization for large decentralized systems. In Proceedings of the Second IEEE International Workshop on Self-Managed Networks, Systems and Services (SelfMan 2006), pages 28--42, Dublin, Ireland, June 2006.
• 31: M. Jelasity and O. Babaoglu. T-Man: Gossip-based overlay topology management. In S. A. Brueckner, G. Di Marzo Serugendo, D. Hales, and F. Zambonelli, editors, Engineering Self-Organising Systems: Third International Workshop (ESOA 2005), Revised Selected Papers, volume 3910 of Lecture Notes in Computer Science, pages 1--15. Springer-Verlag, 2006.
• 32: Márk Jelasity , Rachid Guerraoui , Anne-Marie Kermarrec , Maarten van Steen, The peer sampling service: experimental evaluation of unstructured gossip-based implementations, Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, October 18-22, 2004, Toronto, Canada
• 33: Márk Jelasity , Alberto Montresor , Ozalp Babaoglu, Gossip-based aggregation in large dynamic networks, ACM Transactions on Computer Systems (TOCS), v.23 n.3, p.219-252, August 2005 [doi>10.1145/1082469.1082470]
• 34: Håvard Johansen , André Allavena , Robbert van Renesse, Fireflies: scalable support for intrusion-tolerant network overlays, Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 2006, April 18-21, 2006, Leuven, Belgium
• 35: David Kempe , Alin Dobra , Johannes Gehrke, Gossip-Based Computation of Aggregate Information, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.482, October 11-14, 2003
• 36: L. Lamport. Solved problems, unsolved problems and nonproblems in concurrency. In Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, Aug. 1984.
• 37: E. L. Lawler, J. K. Lenstra, A. H. G. R. Kan, and D. B. Shmoys. The Travelling Salesman Problem. John Wiley & Sons, Chichester, UK, 1985.
• 38: Boris Lubachevsky , Debasis Mitra, A chaotic asynchronous algorithm for computing the fixed point of a nonnegative matrix of unit spectral radius, Journal of the ACM (JACM), v.33 n.1, p.130-150, Jan. 1986 [doi>10.1145/4904.4801]
• 39: J. Matthews. Conway's game of life project. 5 2000.
• 40: D. L. Mills, Network Time Protocol (version 1) specification and implementation, RFC Editor, 1988
• 41: Chrystopher L. Nehaniv, Self-Reproduction in Asynchronous Cellular Automata, Proceedings of the 2002 NASA/DoD Conference on Evolvable Hardware (EH'02), p.201, July 15-18, 2002
• 42: L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998.
• 43: Marco Schneider, Self-stabilization, ACM Computing Surveys (CSUR), v.25 n.1, p.45-67, March 1993 [doi>10.1145/151254.151256]
• 44: T. K. Srikanth , Sam Toueg, Optimal clock synchronization, Journal of the ACM (JACM), v.34 n.3, p.626-645, July 1987 [doi>10.1145/28869.28876]
• 45: T. Stützle and M. Dorigo. Evolutionary Algorithms in Engineering and Computer Science, chapter ACO algorithms for the traveling salesman problem, pages 163--183. John Wiley & Sons, Chichester, UK, 1999.
• 46: D. Subramanian, P. Druschel, and J. Chen. Ants and Reinforcement Learning: A Case Study in Routing in Dynamic Networks. In Proc. Fifteenth International Joint Conference on Artificial Intelligence (IJCAI97), pages 832--839, Nagoya, Japan, 1997.
• 47: R. Sumner. In-vehicle traffic congestion information system, Nov. 17 1992. US Patent 5,164,904.
• 48: Robbert Van Renesse , Kenneth P. Birman , Werner Vogels, Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining, ACM Transactions on Computer Systems (TOCS), v.21 n.2, p.164-206, May 2003 [doi>10.1145/762483.762485]
• 49: S. Voulgaris and M. van Steen. Epidemic-style management of semantic overlays for content-based searching. In J. C. Cunha and P. D. Medeiros, editors, Proc. Euro-Par, number 3648 in Lecture Notes in Computer Science, pages 1143--1152. Springer, 2005.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Network operating systems

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
      D.4.4 Communications Management
      D.4.7 Organization and Design
          Subjects: Distributed systems

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Management, Theory