Commit Protocols

The definition from [1]

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 [2]. 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 [2]
  • 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 [2]

  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.