Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

THE INHERENT COST OF NONBLOCKING COMMITMENT

IP.com Disclosure Number: IPCOM000127979D
Original Publication Date: 1982-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 17 page(s) / 45K

Publishing Venue

Software Patent Institute

Related People

Cynthia Dwork: AUTHOR [+4]

Abstract

A commitment protocol orchestrates the execution of a distributed transaction, allowing each participant to 64vote" 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. tThis work was supported in part by the NSF grant ~fcssl-01220.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 17

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

THE INHERENT COST OF NONBLOCKING COMMITMENT

Cynthia Dwork Dale Skeen

TR 82-538 May 1983

Department of Computer Science Cornell University Ithaca. New York

Abstract

A commitment protocol orchestrates the execution of a distributed transaction, allowing each participant to 64vote" 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.

tThis work was supported in part by the NSF grant ~fcssl-01220.

1. Introduction

A distributed transaction 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-bility.

In execution, a distributed transaction (henceforth, a "transaction") is decomposed into 8Ubtr4nsaction8, each of which is executed by a single processor. A cominitment 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 fault- tolerant as the commitment protocol coordinating its execution.

An extremely important class of fault-tolerant commi~men t 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 is message counts or tandem message delays. Message counts are a rough measure of the network bandwidth required to support the protocols; whereas tandem message delays are often a large

Cornell University Page 1 Dec 31, 1982

Page 2 of 17

THE INHERENT COST OF NONBLOCKING COMMITMENT

component in the executio...