Byzantine Generals and Transaction Commit Protocols
Leslie Lamport, Michael J. Fischer · 1982
The transaction commit problem in a distributed database system is an instance of the Weak Byzantine Generals problem. It is shown that even under the assumption that a process can fail only by "crashing"---failing to send any more messages---a solution to this problem that can tolerate k failures must, in the worst case, require at least k + 1 message-passing delays. Under this same assumption, a simple solution that exhibits the optimal worst-case behavior is given. i Contents 1 Introduction 1 2 The WBG Problem 2 3 The Time Complexity of the WBG Problem 3 4 A Byzantine Generals Solution 13 ii 1 Introduction In many database systems, there is a point in the processing of a transaction when an irrevocable decision is made whether to abort or commit it---where committing the transaction involves inserting any changes it made into the database. For a distributed database system, this decision must be announced to all the sites a#ected by the transaction. We will show that designin...