Gossiping over storage systems is practical

ABSTRACT

Gossip-based mechanisms are touted for their simplicity, limited resource usage, robustness to failures, and tunable system behavior. These qualities make gossiping an ideal mechanism for storage systems that are responsible for maintaining and updating data in a mist of failures and limited resources (e.g., intermittent network connectivity, limited bandwidth, constrained communication range, or limited battery power). We focus on persistent storage systems that, unlike mere caches, are responsible for both the durability and the consistency of data. Examples of such systems may be encountered in many different environments, in particular: wide-area networks (constrained by limited bandwidth), wireless sensor networks (characterized by limited resources), and mobile ad hoc networks (suffering from intermittent connectivity). In this paper, we demonstrate the qualities of gossiping in these three respective environments.

REFERENCES

• 1: Agency, N. S. Global Information Grid (GIG). http://www.nsa.gov/ia/industry/gig.cfm. May 2007.
• 2: Akdere, M., Bilgin, C. Ç., Korpeoglu, I., Ulusoy, O., and Çetintemel, U. A comparison of epidemic algorithms in wireless sensor networks. Computer Communications (Elsevier) 29 (2006), 2450--2457.
• 3: Akyildiz, I. F., Su, W., Sankarasubramaniam, Y., and Cayirci, E. A survey on sensor networks. IEEE Communications Magazine 40, 8 (2002), 102--114.
• 4: Bailey, N. T. J. The Mathematical Theory of Infectious Diseases and its Applications, second ed. Hafner Press, 1975.
• 5: Andy Bavier , Mic Bowman , Brent Chun , David Culler , Scott Karlin , Steve Muir , Larry Peterson , Timothy Roscoe , Tammo Spalink , Mike Wawrzoniak, Operating system support for planetary-scale network services, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.19-19, March 29-31, 2004, San Francisco, California
• 6: Philip A. Bernstein , Nathan Goodman, Multiversion concurrency control—theory and algorithms, ACM Transactions on Database Systems (TODS), v.8 n.4, p.465-483, Dec. 1983 [doi>10.1145/319996.319998]
• 7: Charles Blake , Rodrigo Rodrigues, High availability, scalable storage, dynamic peer networks: pick two, Proceedings of the 9th conference on Hot Topics in Operating Systems, p.1-1, May 18-21, 2003, Lihue, Hawaii
• 8: Eric A. Brewer, Towards robust distributed systems (abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.7, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343502]
• 9: Busnel, Y., Bertier, M., Fleury, E., and Kermarrec, A.-M. GCP : Gossip-based code propagation for large-scaled mobile wireless sensor network. Tech. rep., INRIA, 2007.
• 10: Byung-Gon Chun , Frank Dabek , Andreas Haeberlen , Emil Sit , Hakim Weatherspoon , M. Frans Kaashoek , John Kubiatowicz , Robert Morris, Efficient replica maintenance for distributed storage systems, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.4-4, May 08-10, 2006, San Jose, CA
• 11: Brian A Coan , Brian M Oki , Elliot K Kolodner, Limitations on database availability when networks partition, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.187-194, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10606]
• 12: Frank Dabek , M. Frans Kaashoek , Robert T. Morris, A distributed hash table, Massachusetts Institute of Technology, Cambridge, MA, 2006
• 13: 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]
• 14: Drabkin, V., Friedman, R., Kliot, G., and Segal, M. RAPID: Reliable probabilistic dissemination in wireless ad-hoc networks. Tech. Rep. CS-2006-19, Computer Science Department, Technion -- Israel Institute of Technology, 2006.
• 15: Gavidia, D., Voulgaris, S., and van Steen, M. Epidemic-style monitoring in large-scale wireless sensor networks. Tech. Rep. IR-CS-012, Vrije Universiteit Amsterdam, 2005.
• 16: Ghose, A., Grossklags, J., and Chuang, J. Resilient data-centric storage in wireless sensor networks. IEEE Distributed Systems Online (2003).
• 17: Seth Gilbert , Nancy Lynch, Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services, ACM SIGACT News, v.33 n.2, June 2002 [doi>10.1145/564585.564601]
• 18: Haas, Z. J., Halpern, J. Y., and Li, L. Gossip-based ad hoc routing. In Proceedings of the 21st Annual Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM 2002) (2002), pp. 1707--1716.
• 19: Hara, T. Effective replica allocation in ad hoc networks for improving data accessibility. In Proc. of the 20th Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM 2001) (2001), pp. 1568--1576.
• 20: Takahiro Hara, Replica Allocation in Ad Hoc Networks with Periodic Data Update, Proceedings of the Third International Conference on Mobile Data Management, p.79-86, January 08-11, 2002
• 21: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 22: Jelasity, M., and Babaoglu, O. T-Man: Fast gossip-based construction of large-scale overlay topologies. Tech. Rep. UBLCS-2004-7, University of Bologna, Department of Computer Science, 2004.
• 23: David B. Johnson , David A. Maltz , Josh Broch, DSR: the dynamic source routing protocol for multihop wireless ad hoc networks, Ad hoc networking, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 24: Anne-Marie Kermarrec , Laurent Massoulié , Ayalvadi J. Ganesh, Probabilistic Reliable Dissemination in Large-Scale Systems, IEEE Transactions on Parallel and Distributed Systems, v.14 n.3, p.248-258, March 2003 [doi>10.1109/TPDS.2003.1189583]
• 25: Luo, J., Eugster, P., and Hubaux, J.-P. Route driven gossip: probabilistic reliable multicast in ad hoc networks. In Proceedings of the 22nd Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM 2003) (2003), pp. 2229--2239.
• 26: Jun Luo , Patrick Th. Eugster , Jean-Pierre Hubaux, Pilot: Probabilistic Lightweight Group Communication System for Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.3 n.2, p.164-179, April 2004 [doi>10.1109/TMC.2004.12]
• 27: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 28: Gaurav Mathur , Peter Desnoyers , Deepak Ganesan , Prashant Shenoy, Ultra-low power data storage for sensor networks, Proceedings of the fifth international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127833]
• 29: Miranda, H., Leggio, S., Rodrigues, L., and Raatikainen, K. A stateless neighbour-aware cooperative caching protocol for ad-hoc networks. DI/FCUL TR 05-23, Department of Informatics, University of Lisbon, 2005.
• 30: Morales, R., and Gupta, I. Providing both scale and security through a single core probabilstic protocol. In Proceedings of the Workshop on Stochasticity in Distributed Systems (StoDiS 2005) (2005).
• 31: Christos H. Papadimitriou, The serializability of concurrent database updates, Journal of the ACM (JACM), v.26 n.4, p.631-653, Oct. 1979 [doi>10.1145/322154.322158]
• 32: Larry Peterson , Andy Bavier , Marc E. Fiuczynski , Steve Muir, Experiences building PlanetLab, Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, p.25-25, November 06-08, 2006, Seattle, WA
• 33: Boris Pittel, On spreading a rumor, SIAM Journal on Applied Mathematics, v.47 n.1, p.213-223, Feb. 1987 [doi>10.1137/0147013]
• 34: Stefan Pleisch , Mahesh Balakrishnan , Ken Birman , Robbert van Renesse, MISTRAL: efficient flooding in mobile ad-hoc networks, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132907]
• 35: Ramabhadran, S., and Pasquale, J. Analysis of long-running replicated systems. In Proceedings of the 25th Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM 2006) (2006).
• 36: Sylvia Ratnasamy , Brad Karp , Li Yin , Fang Yu , Deborah Estrin , Ramesh Govindan , Scott Shenker, GHT: a geographic hash table for data-centric storage, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570750]
• 37: Sit, E., Haeberlen, A., Dabek, F., Chun, B.-G., Weatherspoon, H., Morris, R., Kaashoek, M. F., and Kubiatowicz, J. Proactive replication for data durability. In Proceedings of the 5th Int'l Workshop on Peer-to-Peer Systems (IPTPS 2006) (2006).
• 38: D. B. Terry , M. M. Theimer , Karin Petersen , A. J. Demers , M. J. Spreitzer , C. H. Hauser, Managing update conflicts in Bayou, a weakly connected replicated storage system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.172-182, December 03-06, 1995, Copper Mountain, Colorado, United States
• 39: van Renesse, R. Power-aware epidemics. In Int'l Workshop on Reliable Peer-to-Peer Systems (2002).
• 40: 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]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Reliability

Keywords:
distributed storage, durability, gossip-based storage, gossiping, mobile ad hoc networks, persistent storage, update propagation, wide-area networks, wireless sensor networks