Browse Prior Art Database

Original Publication Date: 1983-May-31
Included in the Prior Art Database: 2007-Mar-29

Publishing Venue

Software Patent Institute

Related People

Dwork, Cynthia: AUTHOR [+3]


Cynthia hork Dale Skeen

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 9% of the total text.

Page 1 of 14

Cynthia hork

Dale Skeen

TR 82-538

May 1983

Department of Computer Science Cornell University
Ithaca. New Pork

* This work was supported in part by the NSF Grant MCS81-01220.

[This page contains 1 picture or other non-text object]

Page 2 of 14

[This page contains 1 picture or other non-text object]

Page 3 of 14

The Inherent Cost of Nonblocking Commitment .I

Cynthia Dwork
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.

1. Introduction

  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...