|
 ABSTRACT
An optimistic concurrency control technique is one that allows transactions to execute without synchronization, relying on commit-time validation to ensure serializability. Several new optimistic concurrency control techniques for objects in decentralized distributed systems are described here, their correctness and optimality properties are proved, and the circumstances under which each is likely to be useful are characterized.
Unlike many methods that classify operations only as Reads or Writes, these techniques systematically exploit type-specific properties of objects to validate more interleavings. Necessary and sufficient validation conditions can be derived directly from an object's data type specification. These techniques are also modular: they can be applied selectively on a per-object (or even per-operation) basis in conjunction with standard pessimistic techniques such as two-phase locking, permitting optimistic methods to be introduced exactly where they will be most effective.
These techniques can be used to reduce the algorithmic complexity of achieving high levels of concurrency, since certain scheduling decisions that are NP-complete for pessimistic schedulers can be validated after the fact in time, independent of the level of concurrency. These techniques can also enhance the availability of replicated data, circumventing certain tradeoffs between concurrency and availability imposed by comparable pessimistic techniques.
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
|
|
| |
2
|
AGRAWAL, D., BERNSTEIN, A. J., GUPTA, P., AND SENGUPTA, S. Distributed optimistic concurrency control with reduced rollback. Distributed Syst. 2, 1 (1987).
|
 |
3
|
|
| |
4
|
BADAL, D.Z. Concurrency control overhead or closer look at blocking vs. non-blocking concurrency control mechanisms. In Proceedings of the 5th Berkeley Workshop, 1981, pp. 55-103.
|
| |
5
|
|
| |
6
|
BERNSTEIN, P. A., GOODMAN, N., AND LAI, M. Y. Two-part proof schema for database concurrency control. In Proceedings of the 5th Berkeley Workshop on Distributed Data Management and Computer Networks, 1981.
|
| |
7
|
|
| |
8
|
|
| |
9
|
CERI, S,, AND OWICKI, S. On the use of optimistic methods for concurrency control in distributed databases. In Proceedings of the 6th Berkeley Workshop, of the 1982, pp. 117-130.
|
| |
10
|
Arvola Chan , Stephen Fox , Wen-Te K. Lin , Anil Nori , Daniel R. Ries, The implementation of an integrated concurrency control and recovery scheme, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida
[doi> 10.1145/582353.582386]
|
| |
11
|
DUBOURDIEU, D. J. Implementation of distributed transactions. In Proceedings of the 1982 Berkeley Workshop on Distributed Data Management and Computer Networks, 1982, pp. 81-94.
|
| |
12
|
|
| |
13
|
|
| |
14
|
|
| |
15
|
|
| |
16
|
GAWLICK, D. Processing "not spots" in high performance systems. In Proceedings COMPCON '85, 1985.
|
| |
17
|
|
| |
18
|
|
| |
19
|
|
| |
20
|
|
| |
21
|
|
| |
22
|
|
| |
23
|
HERLIHY, M. P., LYNCH, N. A., MERRITT, M., AND WEIHL, W.E. On the correctness of orphan elimination algorithms. In Proceedings of the 17th Symposium on Fault-Tolerant Computer Systems (FTCS) (July 1987).
|
| |
24
|
|
| |
25
|
JACOBSON, D.M. A protocol for optimistic transactions on abstract data types. Tech. Rep. TR 83-12-04, Department of Computer Science, University of Washington, Seattle, 1984.
|
| |
26
|
|
| |
27
|
|
| |
28
|
|
| |
29
|
|
| |
30
|
LAUSEN, G. Formal aspects of optimistic concurrency control in a multiversion data base system. Inform. Syst. 8, 4 (1983), 291-301.
|
| |
31
|
MENASCE, D. A., AND NAKANISHI, N. Optimistic versus pessimistic concurrency control mechanisms in data base management systems. Inform. Syst. 7, 1 (1982), 13-27.
|
| |
32
|
|
| |
33
|
|
| |
34
|
|
| |
35
|
|
| |
36
|
|
| |
37
|
|
| |
38
|
|
| |
39
|
|
| |
40
|
TAY, Y. C., GOODMAN, N., AND SURf, R. Performance evaluation of locking in databases: A survey. Tech. Rep. TR-17-84, Harvard Aiken Laboratory, Cambridge, Mass., 1984.
|
| |
41
|
|
| |
42
|
|
| |
43
|
|
| |
44
|
|
CITED BY 24
|
|
SangKeun Lee , SoonYoung Jung , Chong-Sun Hwang, A new conflict relation for concurrency control and recovery in object-based databases, Proceedings of the fifth international conference on Information and knowledge management, p.288-295, November 12-16, 1996, Rockville, Maryland, United States
|
|
|
|
|
|
|
|
|
Rajeev Rastogi , Sharad Mehrotra , Yuri Breitbart , Henry F. Korth , Avi Silberschatz, On correctness of non-serializable executions, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.97-108, May 25-28, 1993, Washington, D.C., United States
|
|
|
|
|
|
SangKeun Lee , Chong-Sun Hwang , WonGye Lee, A uniform approach to global concurrency control and recovery in multidatabase environment, Proceedings of the sixth international conference on Information and knowledge management, p.51-58, November 10-14, 1997, Las Vegas, Nevada, United States
|
|
|
Anne-Marie Kermarrec , Antony Rowstron , Marc Shapiro , Peter Druschel, The IceCube approach to the reconciliation of divergent replicas, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.210-218, August 2001, Newport, Rhode Island, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Rajeev Rastogi , Henry F. Korth , Abraham Silberschatz, Strict histories in object-based database systems, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.288-299, May 25-28, 1993, Washington, D.C., United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
H.2