Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: A Note on the Transaction Backout Problem
Authors: Krentel, Mark W.
Keywords: computer science
technical report
Issue Date: Feb-1986
Publisher: Cornell University
Abstract: The transaction backout problem arises in the area of distributed databases. Suppose failures partition a data-redundant distributed database, and each partition continues to function as if it were the entire database. When the database is reconnected, the transactions executed by different partitions may not be serializable, and hence it may be necessary to back out some of the transactions. The transaction backout problem is to remove the smallest set of transactions that will leave the remaining ones serializable. The general problem is NP-complete, and in this paper we show that the special case of a fixed-size database can be solved in polynomial time by dynamic programming.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
86-737.pdf482.44 kBAdobe PDFView/Open
86-737.ps388.91 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us