A ‘liub(log2(N))-2’ Resilient Decentralized Commit Protocol

Shyan-Ming Yuan*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


In distributed database systems, commit protocols are used to ensure the transaction atomicity. In the presence of failures, nonblocking commit protocols can guarantee the transaction atomicity without blocking the transaction execution. A (resilient) decentralized nonblocking commit protocol (RDCP) is proposed for distributed database systems. This protocol is based on the hypercube network topology and is ‘liub(log2(N))-2’ resilient to node failures (N = number of system-nodes). The number of messages sent among the N nodes is O(N.log22(N)) which is only a factor of log2(N) over the message complexity lower bound O(N·log2(N)) of decentralized commit protocols. Furthermore, RDCP is an optimistic nonblocking protocol. It aborts the transaction only when some nodes want to abort or some nodes fail before they make local decisions.

Original languageEnglish
Pages (from-to)594-599
Number of pages6
JournalIEEE Transactions on Reliability
Issue number4
StatePublished - 1 Jan 1994


  • commit protocol
  • decentralized algorithm
  • Distributed database system
  • hypercube
  • message complexity
  • resilience

Fingerprint Dive into the research topics of 'A ‘liub(log2(N))-2’ Resilient Decentralized Commit Protocol'. Together they form a unique fingerprint.

Cite this