the inherent cost of nonblocking commitment
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 commitment protocol is able to correctly terminate a transaction at all operational participants in the presence of any number of benign processor failures. Herein, we derive strong lower bounds for both nonblocking protocols and their less fault-tolerant blocking counterparts. Results on message complexity are both surprising and encouraging: the message complexities 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 nonblocking executions of interfering transactions and thereby reduce their extra cost.
cost commit distributed transaction participant presence processor failure lower bound message complexity class time complexity fault tolerance