Weakly consistent transactions in ROSS

ABSTRACT

This paper describes the design of the weak consistency scheme used in ROSS, the EAN object store. ROSS supports nested atomic transactions on distributed and replicated objects. The weak consistency method falls into the family of optimistic protocols. After a partitioning, execution of transactions proceeds normally. If write-write conflicts are detected when partitions later merge, transactions may be rolled back to ensure consistency. One-copy serializability is not provided. This approach is particularly well suited to a common class of database applications where there is limited interdependency between objects. A distributed name service is one such application.

References

1. J. E. Allchin. "A Suite of Robust Algorithms for Maintaining Replicated Data Using Weak Consistency Conditions", Proc. Third IEEE Symp. on Reliability in Distributed Software and Database Systems, Oct. 1983, pp. 47--56.]]
2. Boaz Ben-Zvi. "Disconnected Actions: An Asynchronous Extension to a Nested Atomic Action System", MIT/LCS/TR-475, Jan. 1990.]]
3. Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman. "Concurrency Control and Recovery in Database Systems", Addison-Wesley, 1987.]]
4. Joshua Bloch. "Camelot and Avalon: A Distributed Transaction Facility", edited by J. Eppinger, L. Mummert, and A. Spector, Morgan Kaufmann, 1991, pp. 21--56.]]
5. Susan B. Davidson. "Optimism and Consistency in Partitioned Distributed Database Systems", ACM Trans. on Database Systems, vol. 9, no. 3, (Sept. 1984), pp. 456--481.]]
6. Susan B. Davidson, Hector Garcia-Molina, and Dale Skeen. "Consistency in Partitioned Networks", Computing Surveys, vol. 17, no. 3, (Sept. 1985), pp. 341--370.]]
7. Digital Equipment Corporation. "DNA Naming Service Functional Specification Version 1.0.1", Nov. 1988.]]
8. Alan Downing, Ira Greenberg, and Jon Peha. "OSCAR: A System for Weak-Consistency Replication", Proc. First Workshop on the Management of Replicated Data, Nov. 1990, pp. 26--30.]]
9. Robert Gruber. "Optimistic Concurrency Control for Nested Distributed Transactions", MIT/LCS/TR-453, June 1989.]]
10. Richard Guy and Gerald Popek. "Algorithms for Consistency in Optimistically Replicated File Systems", Technical Report CSD-910006, Dept. of Computer Science, UCLA, Mar. 1991.]]
11. James J. Kistler and M. Satyarnarayanan. "Disconnected Operation in the Coda File System", ACM Trans. on Computer Systems, vol. 10, no. 1, (Feb. 1992), pp. 3--25.]]
12. Rivka Ladin, Barbara Liskov, Liuba Shrira, and Sanjay Ghemawat. "Providing High Availability Using Lazy Replication", ACM Trans. on Computer Systems, vol. 10, no. 4, (Nov. 1992), pp. 360--391.]]
13. Butler Lampson. "Designing a Global Name Service", Proc. of the 5th Annual ACM Symp. on Principles of Distributed Computing, 1986, pp. 1--10.]]
14. David Mills. "RFC 1119: Network Time Protocol (Version 2) Specification and Implementation", University of Delaware, Sept. 1989.]]
15. Gerald Neufeld, Barry Brachman, Murray Goldberg, and Duncan Stickings. "The EAN X.500 Directory Service", Journal of Internetworking Research and Experience, Vol. 3, No. 2, (June 1992), pp. 55--82.]]
16. Derek Oppen and Yogen Dalal. "The Clearinghouse: A Decentralized Agent for Locating Named Objects in a Distributed Environment", Xerox Office Products Division, Tech. Report OPD-T8103, Oct. 1981.]]
17. D. Stott Parker, Jr., Gerald Popek, Gerard Rudisin, Allen Stoughton, Bruce Walker, Evelyn Walton, Johanna Chow, David Edwards, Stephen Kiser, and Charles Kline. "Detection of Mutual Inconsistency in Distributed Systems", IEEE Trans. on Software Engineering, vol. SE-9, no. 3, (May 1983), pp. 240--247.]]
18. Mahadev Satyanarayanan, James Kistler, Puneet Kumar, Maria Okasaki, Ellen Siegel, and David Steere. "Coda: A Highly Available File System for a Distributed Workstation Environment", IEEE Trans. on Computers, vol. 39, no. 4, (April 1990), pp. 447--459.]]

• Information systems

  • Data management systems

    • Database management system engines

• Software and its engineering

  • Software organization and properties

    • Software system structures