Efficient solutions to the replicated log and dictionary problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient solutions to the replicated log and dictionary problems

Full text

Pdf (731 KB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the third annual ACM symposium on Principles of distributed computing table of contents

Vancouver, British Columbia, Canada

Pages: 233 - 242

Year of Publication: 1984

ISBN:0-89791-143-1

Authors

Gene T.J. Wuu
Arthur J. Bernstein

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 67, Citation Count: 36

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/800222.806750 What is a DOI?

ABSTRACT

We propose efficient algorithms to maintain a replicated dictionary using a log in an unreliable network. A non-serializable approach is used to achieve high concurrency. The solutions are resilient to both node and communication failures. Optimizations are developed for networks which are not completely connected.

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	Michael J. Fischer , Alan Michael, Sacrificing serializability to attain high availability of data in an unreliable network, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588124]
	2	Hector Garcia-Molina, Using semantic knowledge for transaction processing in a distributed database, ACM Transactions on Database Systems (TODS), v.8 n.2, p.186-213, June 1983 [doi>10.1145/319983.319985]
	3	Lui Sha , E. Douglas Jensen , Richard F. Rashid , J. Duane Northcutt, Distributed co-operating processes and transactions, Proceedings of the symposium on Communications Architectures & Protocols, March 08-09, 1983, Austin, Texas
	4	Philip A. Bernstein , Nathan Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.185-221, June 1981 [doi>10.1145/356842.356846]
	5	D. Dolev and R. Strong, "Distributed Commit with Bounded Waiting", IEEE Symposium on Reliability in Distributed Software and Database Systems, 1982.
	6	Robert H. Thomas, A Majority consensus approach to concurrency control for multiple copy databases, ACM Transactions on Database Systems (TODS), v.4 n.2, p.180-209, June 1979 [doi>10.1145/320071.320076]
	7	Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
	8	James Edward Allchin, An architecture for reliable decentralized systems, 1983
	9	Fred B. Schneider, Synchronization in Distributed Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.125-148, April 1982 [doi>10.1145/357162.357163]
	10	Butler W. Lampson, Atomic Transactions, Distributed Systems - Architecture and Implementation, An Advanced Course, p.246-265, January 1981
	11	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]
	12	Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
	13	G.T. Wuu and A.J. Bernstein, "Efficient Solutions to the Replicated Log and Dictionary Problems", Technical Report 84/077, May 1984.

CITED BY 36

	Pierangela Samarati , Paul Ammann , Sushil Jajodia, Propagation of authorizations in distributed database systems, Proceedings of the 2nd ACM Conference on Computer and communications security, p.136-147, November 1994, Fairfax, Virginia, United States
	Malolan Chetlur , Philip A. Wilsey, Causality representation and cancellation mechanism in time warp simulations, Proceedings of the fifteenth workshop on Parallel and distributed simulation, p.165-172, May 15-18, 2001, Lake Arrowhead, California, United States
	Rivka Ladin , Barbara Liskov , Liuba Shrira, Lazy replication: exploiting the semantics of distributed services, Proceedings of the 4th workshop on ACM SIGOPS European workshop, p.1-6, September 03-05, 1990, Bologna, Italy
	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
	Karin Petersen , Mike J. Spreitzer , Douglas B. Terry , Marvin M. Theimer , Alan J. Demers, Flexible update propagation for weakly consistent replication, ACM SIGOPS Operating Systems Review, v.31 n.5, p.288-301, Dec. 1997
	Rivka Ladin , Barbara Liskov , Liuba Shrira, Lazy replication: exploiting the semantics of distributed services, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.43-57, August 22-24, 1990, Quebec City, Quebec, Canada
	Yasushi Saito , Brian N. Bershad , Henry M. Levy, Manageability, availability and performance in Porcupine: a highly scalable, cluster-based mail service, ACM SIGOPS Operating Systems Review, v.33 n.5, p.1-15, Dec. 1999
	Rivka Ladin , Barbara Liskov , Liuba Shrira , Sanjay Ghemawat, Providing high availability using lazy replication, ACM Transactions on Computer Systems (TOCS), v.10 n.4, p.360-391, Nov. 1992
	Narayanan Krishnakumar , Arthur J. Bernstein, Bounded ignorance in replicated systems, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.63-74, May 29-31, 1991, Denver, Colorado, United States
	Yasushi Saito , Brian N. Bershad , Henry M. Levy, Manageability, availability, and performance in porcupine: a highly scalable, cluster-based mail service, ACM Transactions on Computer Systems (TOCS), v.18 n.3, p.298, Aug. 2000
	Narayanan Krishnakumar , Arthur J. Bernstein, Bounded ignorance: a technique for increasing concurrency in a replicated system, ACM Transactions on Database Systems (TODS), v.19 n.4, p.586-625, Dec. 1994
	Michiel Ronsse , Koen De Bosschere, RecPlay: a fully integrated practical record/replay system, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.133-152, May 1999
	R. Mukkamala, Storage Efficient and Secure Replicated Distributed Databases, IEEE Transactions on Knowledge and Data Engineering, v.6 n.2, p.337-341, April 1994
	D. Agrawal , S. Sengupta, Modular Synchronization in Distributed, Multiversion Databases: Version Control and Concurrency Control, IEEE Transactions on Knowledge and Data Engineering, v.5 n.1, p.126-137, February 1993
	D. Agrawal , A. El Abbadi, Storage Efficient Replicated Databases, IEEE Transactions on Knowledge and Data Engineering, v.2 n.3, p.342-352, September 1990
	JoAnne Holliday , Robert Steinke , Divyakant Agrawal , Amr El Abbadi, Epidemic Algorithms for Replicated Databases, IEEE Transactions on Knowledge and Data Engineering, v.15 n.5, p.1218-1238, September 2003
	O. T. Satyanarayanan , D. Agrawal, Efficient Execution of Read-Only Transactions in Replicated Multiversion Databases, IEEE Transactions on Knowledge and Data Engineering, v.5 n.5, p.859-871, October 1993
	Lúcia M. A. Drummond , Valmir C. Barbosa, On reducing the complexity of matrix clocks, Parallel Computing, v.29 n.7, p.895-905, July 2003
	Joanne Holliday , Divyakant Agrawal , Amr El Abbadi, Disconnection modes for mobile databases, Wireless Networks, v.8 n.4, p.391-402, July 2002
	Ajay D. Kshemkalyani, The power of logical clock abstractions, Distributed Computing, v.17 n.2, p.131-150, August 2004
	Michel Raynal , Mukesh Singhal, Logical Time: Capturing Causality in Distributed Systems, Computer, v.29 n.2, p.49-56, February 1996
	Yasushi Saito , Marc Shapiro, Optimistic replication, ACM Computing Surveys (CSUR), v.37 n.1, p.42-81, March 2005
	Ajay D. Kshemkalyani , Mukesh Singhal, Necessary and sufficient conditions on information for causal message ordering and their optimal implementation, Distributed Computing, v.11 n.2, p.91-111, April 1998
	Reinhard Schwarz , Friedemann Mattern, Detecting causal relationships in distributed computations: in search of the holy grail, Distributed Computing, v.7 n.3, p.149-174, March 1994
	D. Agrawal , A. J. Bernstein, A Nonblocking Quorum Consensus Protocol for Replicated Data, IEEE Transactions on Parallel and Distributed Systems, v.2 n.2, p.171-179, April 1991
	I. A. Zhuklinets , D. A. Khotimsky, Logical Time in Distributed Software Systems, Programming and Computing Software, v.28 n.3, p.174-184, May-June 2002
	Michiel Ronsse , Koen De Bosschere, Non-Intrusive Detection of Synchronization Errors Using Execution Replay, Automated Software Engineering, v.9 n.1, p.95-121, January 2002
	Narayanan Krishnakumar , Arthur J. Bernstein, High Throughput Escrow Algorithms for Replicated Databases, Proceedings of the 18th International Conference on Very Large Data Bases, p.175-186, August 23-27, 1992
	Divyakant Agrawal , Amr El Abbadi, Reducing Storage for Quorum Consensus Algorithms, Proceedings of the 14th International Conference on Very Large Data Bases, p.419-430, August 29-September 01, 1988
	T. Cornilleau , E. Gressier-Soudan, A combined-consistency approach: sequential amp; causal-consistency, ACM SIGOPS Operating Systems Review, v.30 n.4, p.33-44, Oct. 1996
	Eddy Fromentin , Michel Raynal, Local states in distributed computations: a few relations and formulas, ACM SIGOPS Operating Systems Review, v.28 n.2, p.65-72, April 1994
	Rivka Ladin , Barbara Liskov , Liuba Shrira, Lazy replication: exploiting the semantics of distributed services (extended abstract), ACM SIGOPS Operating Systems Review, v.25 n.1, p.49-55, Jan. 1991
	Michel Raynal, About logical clocks for distributed systems, ACM SIGOPS Operating Systems Review, v.26 n.1, p.41-48, Jan. 1992
	Lorenzo Bettini, Timed buffers: A technique for update propagation in nomadic environments, Computer Communications, v.31 n.14, p.3209-3222, September, 2008
	Philippe Laumay , Eric Bruneton , Noel De Palma , Sacha Krakowiak, Preserving Causality in a Scalable Message-Oriented Middleware, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.311-328, November 12-16, 2001
	Shiva Chaitanya , Prasenjit Sarkar, CD-PAN: a protocol for peer-to-peer content distribution in a weakly connected and heterogeneous personal area network, Proceedings of the 4th Annual International Conference on Wireless Internet, November 17-19, 2008, Maui, Hawaii