Commit Protocols

The definition from Distributed algorithms. Nancy A. Lynch. 1997

Let $\{0,1\}$ be the input domain, where $1$ represents \emph{commit}, and $0$ represents \emph{abort}.
\begin{enumerate}
  \item \textbf{Agreement} No two processes decide on two different values.
  \item \textbf{Validity}
        \begin{enumerate}
          \item If any process starts with $0$, then $0$ is the only possible decision value.
          \item If all processes start with $1$, and there are no failures, then $1$ is the only possible decision value.
        \end{enumerate}
  \item \textbf{Termination}
        \begin{enumerate}
          \item \textbf{Weak Termination (Blocking Termination)} If there are no failures then all processes eventually decide.
          \item \textbf{Strong Termination (Non-blocking termination)} All non-faulty processes eventually decide.
        \end{enumerate}
\end{enumerate}

This is similar but not identical to Byzantine Agreement/Binary consensus but with a modified validity.

• 1 phase commit / 1PC, 2PC, 3PC are specific protocols with 1,2, and 3 rounds respectively.

• See related A comparison of the Byzantine Agreement problem and the Transaction Commit Problem. Jim Gray. 1990. According to this, the commit problem and Byzantine generals are identical in the fault-free case.

  Fault Tolerance/Degree of Agreement	Some Agree	All Agree
  Limited Time	Byzantine	Ideal
  Unlimited Time	Inferior	Commit

• From A comparison of the Byzantine Agreement problem and the Transaction Commit Problem. Jim Gray. 1990
  • Generally, the fault model is crash/omission (Processes may lose state and be reset to a null state)
  • The network model is partially synchronous: (Messages may be delayed, corrupted, or lost)

• From A comparison of the Byzantine Agreement problem and the Transaction Commit Problem. Jim Gray. 1990

  Fundamental differences between the problems and their solutions emerge when there are faults. The basic differences are:

  • Commit protocols tolerate finitely many faults. Byzantine protocols tolerate at most N/3 faults.
  • ALL processors agree in the commit case. SOME processors agree in the Byzantine case.
  • Commit algorithms are fail-fast. They give either a common answer or no answer. Byzantine algorithms give random answers without warning if the fault threshold is exceeded.
  • Commit agreement may require unbounded time. Byzantine agreement terminates in bounded time.
  • Commit algorithms require no extra processors and few extra messages. Byzantine algorithms require many messages and processors.