|
 ABSTRACT
A “majority consensus” algorithm which represents a new solution to the update synchronization problem for multiple copy databases is presented. The algorithm embodies distributed control and can function effectively in the presence of communication and database site outages. The correctness of the algorithm is demonstrated and the cost of using it is analyzed. Several examples that illustrate aspects of the algorithm operation are included in the Appendix.
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
|
SHAPIRO, R.M., AND MILLSTEIN, R.E. The NSW reliability plan. Rep. CA-7701.1411, Massachusetts Computer Associates, June 1977.
|
| |
2
|
ROTHNIE, J.B., GOODMAN, N., AND BERNSTEIN, P.A. The redundant update methodology of SDD-I: A system for distributed data bases (the fully redundant case). Tech. Rep. CCA-77-02, Computer Corp. of America, Cambridge, Mass., June 1977.
|
| |
3
|
ALSBERG, P.A., AND DAY, J.D. A principle for resilient sharing of distributed resources. Rep. from Ctr. for Advanced Comput., U. of Illinois at Urbana-Champaign, Urbana, Ill., 1976.
|
 |
4
|
D. Austin Henderson, Jr. , Theodore H. Myer, Issues in message technology, Proceedings of the fifth symposium on Data communications, p.6.1-6.9, September 27-29, 1977, Snowbird, Utah, United States
[doi> 10.1145/800103.803348]
|
| |
5
|
ROBERTS, L.G., AND WESSLER, B.D. Computer network development to achieve resource sharing. Proc. AFIPS 1970 SJCC, AFIPS Press, Montvale, N.J., pp. 543-549.
|
| |
6
|
|
| |
7
|
CERF, V., AND KAHN, R. A protocol for packet network interconnection. IEEE Trans. Comm. Comm-22, 5 (May 1974), 637-648.
|
| |
8
|
JOHNSON, P., AND THOMAS, R. The maintenance of duplicate data bases. Network Information Center (NIC) Document #31507, ARPA Network Working Group Request for Comments (RFC) ~77, Jan. 1975.
|
| |
9
|
|
| |
10
|
I~MPORT, L. Time, clocks and the ordering of events in a distributed system. Rep. CA-7603-2911, Massachusetts Computer Associates, March 1976; also submitted to Comm. ACM.
|
CITED BY 225
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Rudolf Bayer , Klaus Elhardt , Hans Heller , Angelika Reiser, Distributed concurrency control in database systems, Proceedings of the sixth international conference on Very Large Data Bases, p.275-284, October 01-03, 1980, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Daniel Barbara , Hector Garcia-Molina , Annemarie Spauster, Protocols for dynamic vote reassignment, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.195-205, August 11-13, 1986, Calgary, Alberta, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Svend Frølund , Arif Merchant , Yasushi Saito , Susan Spence , Alistair Veitch, FAB: enterprise storage systems on a shoestring, Proceedings of the 9th conference on Hot Topics in Operating Systems, p.29-29, May 18-21, 2003, Lihue, Hawaii
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Andrea Pietracaprina , Geppino Pucci , Jop F. Sibeyn, Constructive deterministic PRAM simulation on a mesh-connected computer, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.248-256, June 27-29, 1994, Cape May, New Jersey, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Toyokazu Akiyama , Shinobu Sakai , Akimichi Umigai , Takahiro Hara , Masahiko Tsukamoto , Shojiro Nishio, Design and implementation of DB-MANα: does database migration work well in a real environment?, Australian Computer Science Communications, v.24 n.2, p.23-31, January-February 2002
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Chagit Attiya , Danny Dolev , Joseph Gil, Asynchronous Byzantine consensus, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.119-133, August 27-29, 1984, Vancouver, British Columbia, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Brendan Tangney , Vinny Cahill , Chris Horn , Dominic Herity , Alan Judge , Gradimir Starovic , Mark Sheppard, Some ideas on support for fault tolerance in COMANDOS, an object oriented distributed system, ACM SIGOPS Operating Systems Review, v.25 n.2, p.130-135, April 1991
|
|
|
|
|
|
|
|
|
|
|
|
Brendan Tangney , Vinny Cahill , Chris Horn , Dominic Herity , Alan Judge , Gradimir Starovic , Mark Sheppard, Some ideas on support for fault tolerance in COMANDOS, an object oriented distributed system, Proceedings of the 4th workshop on ACM SIGOPS European workshop, p.1-6, September 03-05, 1990, Bologna, Italy
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Giuseppe DeCandia , Deniz Hastorun , Madan Jampani , Gunavardhan Kakulapati , Avinash Lakshman , Alex Pilchin , Swaminathan Sivasubramanian , Peter Vosshall , Werner Vogels, Dynamo: amazon's highly available key-value store, ACM SIGOPS Operating Systems Review, v.41 n.6, December 2007
|
|
|
Anupam Gupta , Bruce M. Maggs , Florian Oprea , Michael K. Reiter, Quorum placement in networks to minimize access delays, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
|
|
|
|
|
|
|
|
|
A. Fekete , N. Lynch , M. Merrit , W. Weihl, Nested transactions and read-write locking, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.97-111, March 23-25, 1987, San Diego, California, United States
|
|
|
|
|
|
Alan Fekete , David Gupta , Victor Luchangco , Nancy Lynch , Alex Shvartsman, Eventually-serializable data services, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.300-309, May 23-26, 1996, Philadelphia, Pennsylvania, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
J. B. Rothnie, Jr. , P. A. Bernstein , S. Fox , N. Goodman , M. Hammer , T. A. Landers , C. Reeve , D. W. Shipman , E. Wong, Introduction to a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.5 n.1, p.1-17, March 1980
|
|
|
|
|
|
|
|
|
|
|
|
Dahlia Malkhi , Michael Reiter , Rebecca Wright, Probabilistic quorum systems, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.267-273, August 21-24, 1997, Santa Barbara, California, United States
|
|
|
|
|
|
Gérald Oster , Pascal Urso , Pascal Molli , Abdessamad Imine, Data consistency for P2P collaborative editing, Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work, November 04-08, 2006, Banff, Alberta, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
D. Agrawal , A. El Abbadi , R. C. Steinke, Epidemic algorithms in replicated databases (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.161-172, May 11-15, 1997, Tucson, Arizona, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Daniel Golovin , Anupam Gupta , Bruce M. Maggs , Florian Oprea , Michael K. Reiter, Quorum placement in networks: minimizing network congestion, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Dahlia Malkhi , Michael Reiter , Avishai Wool, The load and availability of Byzantine quorum systems, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.249-257, August 21-24, 1997, Santa Barbara, California, United States
|
|
|
|
|
|
|
|
|
David Peleg , Avishai Wool, How to be an efficient snoop, or the probe complexity of quorum systems (extended abstract), Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.290-299, May 23-26, 1996, Philadelphia, Pennsylvania, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Pdf