Epidemic algorithms for replicated database maintenance

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Epidemic algorithms for replicated database maintenance

Full text

Pdf (1.71 MB)

Source

ACM SIGOPS Operating Systems Review archive
Volume 22 , Issue 1 (Jan., 1988) table of contents

Pages: 8 - 32

Year of Publication: 1988

ISSN:0163-5980

Authors

Alan Demers	Xerox Palo Alto Center, Palo Alto, NM
Dan Greene	Xerox Palo Alto Center, Palo Alto, NM
Carl Houser	Xerox Palo Alto Center, Palo Alto, NM
Wes Irish	Xerox Palo Alto Center, Palo Alto, NM
John Larson	Xerox Palo Alto Center, Palo Alto, NM
Scott Shenker	Xerox Palo Alto Center, Palo Alto, NM
Howard Sturgis	Xerox Palo Alto Center, Palo Alto, NM
Dan Swinehart	Xerox Palo Alto Center, Palo Alto, NM
Doug Terry	Xerox Palo Alto Center, Palo Alto, NM

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 18, Downloads (12 Months): 96, Citation Count: 17

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/43921.43922 What is a DOI?

ABSTRACT

When a database is replicated at many sites, maintaining mutual consistency among the sites in the face of updates is a significant problem. This paper describes several randomized algorithms for distributing updates and driving the replicas toward consistency. The algorithms are very simple and require few guarantees from the underlying communication system, yet they ensure that the effect of every update is eventually reflected in all replicas. The cost and performance of the algorithms are tuned by choosing appropriate distributions in the randomization step. The algorithms are closely analogous to epidemics, and the epidemiology literature aids in understanding their behavior. One of the algorithms has been implemented in the Clearinghouse servers of the Xerox Corporate Internet. solving long-standing problems of high traffic and database inconsistency.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Karl Abrahamson , Andrew Adler , Lisa Higham , David Kirkpatrick, Probabilistic solitude verification on a ring, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.161-173, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10604]
	2	Baruch Awerbuch , Shimon Even, Efficient and reliable broadcast is achievable in an eventually connected network(Extended Abstract), Proceedings of the third annual ACM symposium on Principles of distributed computing, p.278-281, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806754]
	3	[Ba] Norman T. J. Bailey. The Mathematical Theory of Infectious Diseases and its Applications (second edition). Hafner Press, Second Edition, 1975.
	4	Michael Ben-Or, Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.27-30, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806707]
	5	Michael Ben-Or, Fast asynchronous Byzantine agreement (extended abstract), Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.149-151, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323609]
	6	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]
	7	K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985 [doi>10.1145/214451.214456]
	8	[Fr] J.C. Frauenthal. Mathematical Modeling in Epidemiology, Pages 12-24. Springer-Verlag, 1980.
	9	David K. Gifford, Weighted voting for replicated data, Proceedings of the seventh ACM symposium on Operating systems principles, p.150-162, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806583]
	10	P. R. Johnson , R. Thomas, Maintenance of duplicate databases, RFC Editor, 1975
	11	Butler W Lampson, Designing a global name service, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.1-10, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10591]
	12	Paul V. Mockapetris, The domain name system, Proc. of the IFIP WG 6.5 working conference on Computer-based message services, p.61-72, November 1984, Nottingham, United Kingdom
	13	[Op] Derek C. Oppen and Yogen K. Dalal. The Clearinghouse: A Decentralized Agent for Locating Named Objects in a Distributed Environment. Xerox Technical Report: OPD-T8103, 1981.
	14	Boris Pittel, On spreading a rumor, SIAM Journal on Applied Mathematics, v.47 n.1, p.213-223, Feb. 1987 [doi>10.1137/0147013]
	15	[Ra] Michael O. Rabin. Randomized Byzantine Generals. 24th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, 1983, Pages 403-409.
	16	Sunil K. Sarin , Nancy A. Lynch, Discarding Obsolete Information in a Replicated Database System, IEEE Transactions on Software Engineering, v.13 n.1, p.39-47, January 1987 [doi>10.1109/TSE.1987.232564]

CITED BY 17

	Abdelmajid Khelil , Christian Becker , Jing Tian , Kurt Rothermel, An epidemic model for information diffusion in MANETs, Proceedings of the 5th ACM international workshop on Modeling analysis and simulation of wireless and mobile systems, September 28-28, 2002, Atlanta, Georgia, USA
	Nuno Preguiça , J. Legatheaux Martins , Henrique Domingos , Sérgio Duarte, Data management support for asynchronous groupware, Proceedings of the 2000 ACM conference on Computer supported cooperative work, p.69-78, December 2000, Philadelphia, Pennsylvania, United States
	Allan Beaufour , Martin Leopold , Philippe Bonnet, Smart-tag based data dissemination, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA
	Bo Xu , Ouri Wolfson , Sam Chamberlain , Naphtali Rishe, Cost based data dissemination in satellite networks, Mobile Networks and Applications, v.7 n.1, January 2002
	Arturo Crespo , Hector Garcia-Molina, Archival storage for digital libraries, Proceedings of the third ACM conference on Digital libraries, p.69-78, June 23-26, 1998, Pittsburgh, Pennsylvania, United States
	Leonard Kawell, Jr. , Steven Beckhardt , Timothy Halvorsen , Raymond Ozzie , Irene Greif, Replicated document management in a group communication system, Proceedings of the 1988 ACM conference on Computer-supported cooperative work, September 26-28, 1988, Portland, Oregon, United States
	Yatin Chawathe, Scattercast: an adaptable broadcast distribution framework, Multimedia Systems, v.9 n.1, p.104-118, July 2003
	Matthew Chalmers, A linear iteration time layout algorithm for visualising high-dimensional data, Proceedings of the 7th conference on Visualization '96, p.127-ff., October 28-29, 1996, San Francisco, California, United States
	Paolo Costa , Matteo Migliavacca , Gian Pietro Picco , Gianpaolo Cugola, Introducing reliability in content-based publish-subscribe through epidemic algorithms, Proceedings of the 2nd international workshop on Distributed event-based systems, June 08-08, 2003, San Diego, California
	Paul Tennent , Malcolm Hall , Barry Brown , Matthew Chalmers , Scott Sherwood, Three applications for mobile epidemic algorithms, Proceedings of the 7th international conference on Human computer interaction with mobile devices & services, September 19-22, 2005, Salzburg, Austria
	Christina Fragouli , Jörg Widmer , Jean-Yves Le Boudec, Efficient broadcasting using network coding, IEEE/ACM Transactions on Networking (TON), v.16 n.2, p.450-463, April 2008
	Graham Williamson , Graeme Stevenson , Steve Neely , Lorcan Coyle , Paddy Nixon, Scalable information dissemination for pervasive systems: implementation and evaluation, Proceedings of the 4th international workshop on Middleware for Pervasive and Ad-Hoc Computing (MPAC 2006), p.7, November 27-December 01, 2006, Melbourne, Australia
	Dejan Kostić , Adolfo Rodriguez , Jeannie Albrecht , Abhijeet Bhirud , Amin Vahdat, Using random subsets to build scalable network services, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.19-19, March 26-28, 2003, Seattle, WA
	C. Guéret , N. Monmarché , M. Slimane, A biology-inspired model for the automatic dissemination of information in P2P networks, Multiagent and Grid Systems, v.3 n.1, p.87-104, January 2007
	Pepijn Crouzen , Jaco van de Pol , Arend Rensink, Applying formal methods to gossiping networks with mCRL and groove, ACM SIGMETRICS Performance Evaluation Review, v.36 n.3, December 2008
	Evan P. C. Jones , Lily Li , Jakub K. Schmidtke , Paul A. S. Ward, Practical Routing in Delay-Tolerant Networks, IEEE Transactions on Mobile Computing, v.6 n.8, p.943-959, August 2007
	Lorenzo Bettini, Timed buffers: A technique for update propagation in nomadic environments, Computer Communications, v.31 n.14, p.3209-3222, September, 2008