Article

Free access

Edge locks and deadlock avoidance in distributed systems

Author:

Henry F. KorthAuthors Info & Claims

PODC '82: Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing

Pages 173 - 182

https://doi.org/10.1145/800220.806695

Published: 18 August 1982 Publication History

PDF eReader

Abstract

Two locking protocols are defined for distributed database systems. One protocol provides deadlock avoidance without the need to roll back transactions. The other allows a useful weakening of the protocol in which only a limited class of easily handled deadlocks may occur. The protocols are capable of handling replicated as well as partitioned data. Like the centralized protocol on which they are based, the protocol of this paper permits locking at multiple granularities and allows collections of locks to be constructed to correspond to an arbitrary collection of database operations. Special provisions are made in the protocol to allow readers, and in particular, readers that touch data at only one site, to execute with less locking overhead than writers. Following the description of the protocol, comparisons are made between the protocol of this paper and other protocols previously published that offer similar features.

References

[1]

Attar, R., P.A. Bernstein, and N. Goodman (1982), "Site Initialization, Recovery, and Back-Up in a Distributed Database System," Proc. 6 Berkeley Workshop on Distributed Databases and Computer Networks, pp. 185-202.

Google Scholar

[2]

Bernstein, P.A., and N. Goodman (1981), "Concurrency Control in Distributed Database Systems," ACM Computing Surveys, 13:2, pp. 185-221.

Digital Library

Google Scholar

[3]

Eswaran, K.E., J.N. Gray, R.A. Lorie, and I.L. Traiger (1976), "On the Notions of Consistency and Predicate Locks in a Relational Database System," Comm. ACM 14:11, pp. 624-634.

Digital Library

Google Scholar

[4]

Gray, J.N. (1978), "Notes on Database Operating Systems," RJ3120, IBM Research Laboratory, San Jose, CA., also in Operating Systems, An Advanced Course, Lecture Notes in Computer Science 60, Goos and Hartmanis, eds. Springer-Verlag, pp. 393-481.

Digital Library

Google Scholar

[5]

Gray, J.N., R.A. Lorie, G.R. Putzolu, and I.L. Traiger (1975), "Granularity of Locks and Degrees of Consistency in a Shared Data Base," RJ1654, IBM Research Laboratory, San Jose, CA.

Google Scholar

[6]

Korth, H.F. (1981a), "Locking Primitives in a Database System," to appear, J. ACM.

Digital Library

Google Scholar

[7]

Korth, H.F. (1981b), "Deadlock Freedom Using Edge Locks," to appear, ACM Transactions on Database Systems.

Digital Library

Google Scholar

[8]

Lamport, L. (1978), "Time, Clocks and the Ordering of Events in a Distributed System," Comm. ACM, 21:7, pp. 558-565.

Digital Library

Google Scholar

[9]

Lindsay, B.G., P.G. Selinger, C. Galtieri, J.N. Gray, R.A. Lorie, T.G. Price, F. Putzolu, I.L. Traiger, B.W. Wade (1979), "Notes on Distributed Databases," RJ2571, IBM Research Laboratory, San Jose, CA.

Google Scholar

[10]

Menasce, D.A., G.J. Popek, and R.R. Muntz (1980), "A Locking Protocol for Resource Coordination is Distributed Databases," ACM Transactions on Database Systems, 5:2, pp. 103-138.

Digital Library

Google Scholar

[11]

Rosenkrantz, D.J., R.E. Stearns, and P.M. Lewis (1978), "System Level Concurrency Control for Distributed Database Systems," ACM Transactions on Database Systems, 3:2, pp. 178-198.

Digital Library

Google Scholar

[12]

Traiger, I.L., J.N. Gray, C.A. Galtieri, and B.G. Lindsay (1978), "Transactions and Consistency in Distributed Database Systems," RJ2555, IBM Research Laboratory, San Jose, CA.

Google Scholar

[13]

Ullman, J.D. (1980), Principles of Database Systems, Computer Science Press, Potomac, MD.

Digital Library

Google Scholar

Cited By

View all

(1988)BibliographyConcurrency Control in Distributed Database Systems10.1016/B978-0-444-70409-2.50028-9(331-349)Online publication date: 1988
https://doi.org/10.1016/B978-0-444-70409-2.50028-9
Francez NHailpern B(1985)ScriptACM SIGOPS Operating Systems Review10.1145/850770.85077319:2(53-67)Online publication date: 1-Apr-1985
https://dl.acm.org/doi/10.1145/850770.850773
Francez NHailpern BProbert RLynch NSantoro N(1983)ScriptProceedings of the second annual ACM symposium on Principles of distributed computing10.1145/800221.806723(213-227)Online publication date: 17-Aug-1983
https://dl.acm.org/doi/10.1145/800221.806723

Index Terms

Edge locks and deadlock avoidance in distributed systems

Recommendations

Deadlock freedom using edge locks

We define a series of locking protocols for database systems that all have three main features: freedom from deadlock, multiple granularity, and support for general collections of locking primitives. A rooted directed acyclic graph is used to represent ...
Efficient distributed deadlock avoidance with liveness guarantees
EMSOFT '06: Proceedings of the 6th ACM & IEEE International conference on Embedded software

We present a deadlock avoidance algorithm for distributed systems that guarantees liveness. Deadlock avoidance in distributed systems is a hard problem and general solutions are considered impractical due to the high communication overhead. In previous ...
Deadlock-Free channels and locks
ESOP'10: Proceedings of the 19th European conference on Programming Languages and Systems

The combination of message passing and locking to protect shared state is a useful concurrency pattern. However, programs that employ this pattern are susceptible to deadlock. That is, the execution may reach a state where each thread in a set waits for ...

Comments

Information & Contributors

Information

Published In

PODC '82: Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing

August 1982

261 pages

ISBN:0897910818

DOI:10.1145/800220

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 August 1982

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
571
Total Downloads

Downloads (Last 12 months)74
Downloads (Last 6 weeks)7

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

(1988)BibliographyConcurrency Control in Distributed Database Systems10.1016/B978-0-444-70409-2.50028-9(331-349)Online publication date: 1988
https://doi.org/10.1016/B978-0-444-70409-2.50028-9
Francez NHailpern B(1985)ScriptACM SIGOPS Operating Systems Review10.1145/850770.85077319:2(53-67)Online publication date: 1-Apr-1985
https://dl.acm.org/doi/10.1145/850770.850773
Francez NHailpern BProbert RLynch NSantoro N(1983)ScriptProceedings of the second annual ACM symposium on Principles of distributed computing10.1145/800221.806723(213-227)Online publication date: 17-Aug-1983
https://dl.acm.org/doi/10.1145/800221.806723

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Deadlock freedom using edge locks

Efficient distributed deadlock avoidance with liveness guarantees

Deadlock-Free channels and locks