THE INHERENT COST OF NONBLOCKING COMMITMENT
Original Publication Date: 1983-May-31
Included in the Prior Art Database: 2007-Mar-29
Software Patent Institute
Dwork, Cynthia: AUTHOR [+3]
Cynthia hork Dale Skeen
Department of Computer Science Cornell University
Ithaca. New Pork 14853
* This work was supported in part by the NSF Grant MCS81-01220.
The Inherent Cost of Nonblocking Commitment .I
Dale Skeen Compater Science Department
CorneN University Ithaca, New >Yo& 14853
A commitment protocol orchestrates the execution of a distributed transaction, allowing each participant to "vote" on the transaction and then applying a pre- specified rule to decide the outcome (commit or abort). A nonblocking is able to correctly terminate a transaction at all operational participants in the pres- ence of any number of benign processor failures. Herein. we derive strong lower bounds for both non- blocking protocols and their less fault-tolerant block- ing counterparts. Results on message complexity are both surprising and encouraging: the message com- plexities of the two classes of protocols are identical. Results on time complexity were less encouraging: nonblocking protocols are approximately 50% more expensive. However, we show how to overlap non- blocking executions of interfering transactions and thereby reduce their extra cost.
A distributed trnnsaction is an atomic action span- ning multiple processors; either all or none of its effects persist. The transaction notion is fundamental in fault-tolerant systems - useful both in the concep tualization and the realization of such systems. His-
torically transactions have been associated with data- base systems; however, the notion has broad applica- bili ty .
In execution, a distributed transaction (henceforth, a '%ransaction") is decomposed into subtransactions, each of which is executed by a single processor. A commitment protocol orchestrates the execution of the subtransactions among the participating processors, establishing the all or nothing appearance of the tran- saction. A transaction is only as faulttolerant as the commitment protocol coordinating its execution.
An extremely important class of faulttolerant commitment protocols is the nonblocking protocols. A nonblocking protocol can correctly terminate a transac- tion as long as processor failures are not malicious and one of the participating processors remains opera- tional. Hence, such protocols never "block" (suspend execution) because of processor failures, and in this sense, they are maximally tolerant of benign processor failures.
In spite of their increased fault-tolerance, non- blocking protocols are often not used because of their expense: all known nonblocking protocols are approxi- mately 50% more costly than their blocking counter- parts. The same overhead is found whether the cost metric i...