In this follow up post to our basic Lock-Commit post, we show a multi-shot synchronous protocol for uniform consensus that can tolerate $f$ omission failures, given 2f < n. We then extend it to one that tolerates both $f$ omission failures and $k$ crash failures given k+2f < n.

Multi-shot Lock-Commit for omission failures

Unlike the single-shot protocol, this protocol never terminates, it just appends commands to an ever-growing log of committed commands called commitLog. The log is extended by appending commands to it. As in the previous post, we do not discuss executing the commands as well as how clients can learn about consensus (will be covered in later posts). Another change is that each time the commitLog is sent from a sender to a recipient, the recipient checks if its commitLog is behind (missing commands) and then updates its log (learns about committed commands it missed).

Once the primary commits a command, we use the boolean readyToPropose to indicate that the primary can send a new proposal to append to the log.

We will also use a deterministic mapping from view to primary. Let $primary(v)$ be the id of the primary for view $v$.

// pseudocode for Replica j

state = init // the state of the state machine
commitLog = []     // a log of committed commands
view = 1     // view number that indicates the current Primary
lock-value = null
lock-view = 0     // the highest view a propose was heard
mycmd = null
start timer(1) // start timer for first view
readyToPropose = true // primary can send another propose

while true:

   // as a primary (you are replica j)
   if primary(view) == j:
   on receiving cmd from client and readyToPropose == true:
         readyToPropose = false
         send ("propose", commitLog, cmd, view) to all replicas
         
   // as a replica in the same view -> lock
   on receiving ("propose", CL, cmd, v) and v == view:
         // learn if needed
         if CL > commitLog then commitLog = CV
         if CL == commitLog:                
            lock-view = v
            lock-value = cmd
            send ("lock", commitLog, lock-value, lock-view) to the primary j

   // as a primary getting n-f locks -> commit
   if primary(view) == j:
   on receiving ("lock", CL, cmd, view) from n-f distinct replicas:
         // append to log
         if CL == commitLog then
            commitLog.append(cmd)
            send ("commit", commitLog, view) to all replicas
            readyToPropose = true
         
   // as a replica in dame view -> append and start next timer
   on receiving ("commit", CL, v) and v == view:
         // learn if needed
         if CL > commitLog then
            commitLog = CV
            restart timer(v)

Note that as an optimization, we could have piggybacked the “commit” message with the next “propose” message.

The view change trigger protocol is similar to the single-shot one, except that timer(i) is restarted each time a replica appends to commitLog (see “restart timer” above). This implements a stable leader variant where a primary can commit many entries and is replaced only when there are $f+1$ “blame” messages. An alternative variant that replaces the primary every round will be explored in later posts.

  on timer(v) expiring and view == v; or
  on receiving ("blame", v) from f+1 distinct replicas
        send ("blame", v) to all replicas
  on receiving ("blame", v) from n-f distinct replicas and view <= v:
        // this will trigger view change to view v+1
        send ("view change", v+1) to all replicas 

The view change protocol is modified so the new primary learns about committed commands it has missed (this is different from Raft where the new primary must be the most up-to-date replica). The new primary must choose the lock-value of the highest lock-view for the proposals that are about the longest commitLog entry it has seen. If the longest commitLog entry is committed and the new primary sees no append proposals then the new primary is free to choose from the client commands. Here is the view change for replica $j$:

   // send commit log and highest lock
   on receiving ("view change", v) and view < v:
        view = v
        start timer(view)
        send ("highest lock", commitLog, lock-value, lock-view, view) to replica v
        
   // as the primary (you are replica j)
   if primary(view) == j:       
   on receiving messages M={("highest lock", CL, l-value, l-view, j)} from n-f distinct replicas:
        Let CL be the longest commit log in M.CL
        // learn if needed
        If CL > commitLog then commitLog = CV
        Let H be the set of messages in M where M.CL == commitLog
        if H is empty or all H.l-view == 0:
             mycmd = any value heard from the clients
        otherwise:
             // use the lock-value of the message in H with highest lock-view
             let m in H be a message with maximum H.l-view 
             mycmd = m.l-value
        readyToPropose = false
        send ("propose", commitLog, mycmd, view) to all replicas

Observe that when a primary proposes a message, as well as when replicas send their highest lock to the next primary, the entire commit log is sent in the message. This ensures that, at any time, whenever a replica is locked on value, all the previous log positions are committed. While sending the entire log each time brings conceptual simplicity, it is expensive to send the entire log. In practice, one can use message digests and chained digests to quickly identify any missing committed commands. In a future post, we will discuss how this can be optimized.

Multi-shot Lock-Commit tolerating both omission and crash failures

With both $f$ omission failures and $k$ crash failures the primary needs to guarantee that all non-crashed replicas receive a “propose” message and lock. Just waiting for $n-(k+f)$ “lock” messages may not be safe because it may be that the primary is omission faulty and these $n-(k+f)=f+1 \leq c$ parties all crash. The primary does not know if it is omission faulty!

Instead, the primary asks the replicas to “help” spread the “propose” message. Each helper sends the “propose” to everyone and then sends a “help done”. This way, the primary can wait for $n-(k+f)$ parties to acknowledge “help done” and know that at least one of the helpers was non-omission faulty. Since it received a “help done”, then this non-omission faulty did not crash before sending the message to everyone! Here is the pseudocode for Replica $j$:

state = init // the state of the state machine
commitLog = []     // a log of committed commands
view = 1     // view number that indicates the current Primary
lock-value = null
lock-view = 0     // the highest view a propose was heard
start timer(1) // start timer for first view
readyToPropose = true // primary can send another propose


while true:

   // as a primary (you are replica j)
   on receiving cmd from client, view == j, readyToPropose == true:
         send ("help", commitLog, cmd, view) to all replicas
         readyToPropose = false
   on receiving ("help", CL, cmd, v) and v==view:
         // learn if needed
         if CL > commitLog then commitLog = CV
         send ("propose", commitLog, cmd, v) to all replicas
         send ("help done", commitLog, cmd, v) to the primary j
   on receiving ("help done", CL, cmd, view) from f+1 distinct replicas and view == j:
         // append to log
         commitLog.append(cmd)
         send ("commit", commitLog, cmd, view) to all replicas
         readyToPropose = true
   // as a replica: execute and restart timer
   on receiving ("commit", CL, cmd, v):
         // learn if needed
         if CL > commitLog then commitLog = CV
         restart timer(v)
   // as a backup replica in the same view
   on receiving ("propose", CL, cmd, v) and v==view:
         // learn if needed
         if CL > commitLog then commitLog = CV
         //lock
         lock-view = v
         lock-value = cmd

Note that as an optimization, we could have piggybacked the “commit” message with the next “propose” message.

Remarks

Just like the previous post, we did not fully specify how the clients send commands to the replicas and we do not talk about executing the commands. We here on the consensus protocol and defer execution and clients to later posts.

Argument for Safety

Claim: Fix any log position $j$, let $v$ be the first view where a party commits to value $cmd$. Then, no primary will propose $cmd’ \neq cmd$ at any view $v’\geq v$ for the log position $j$.

Proof:

By induction on $v’ \geq v$. For $v’=v$, this follows since the primary sends just one “propose” value per view on a given log position. Assume the hypothesis holds for all view $\leq v’$ and consider the view change of primary $v’+1$.

Let $W$ be the parties that set $lock-view = v$ in view $v$ for log position $j$. Since primary $v$ had at least $f+1$ helpers that did not crash, then at least one of them must have sent the proposal to all non-faulty parties.

Let $R$ be the set of at least $n-(f+k)$ parties that party $v’+1$ received their $(“highest lock”, lock-value, lock-view, v’+1)$ for view $v’+1$ on log position $j$.

Since $\vert N \setminus W\vert \leq f$ and $\vert R\vert \geq f+1$ it must be that $W \cap R \neq \emptyset$. So the primary of $v’+1$ must hear from a member of $R$ and, from the induction hypothesis, we know that this member’s lock-view is at least $v$ and its lock-value must be $cmd$. In addition, from the induction hypothesis, we know that no other member of $W$ can have a lock-value for a value that has a lock-view of at least $v$ with a value $cmd’ \neq cmd$.

Hence, during the view change of view $v’+1$, the value with the maximum view in $W$ must be $cmd$ with a view $\geq v$.

Argument for Liveness

For liveness, we need to modify the blame threshold to $f+1$ and the view change threshold to $n-(f+k) \geq f+1$.

Claim: Fix some log position $j$. Let $v$ be the first view with a non-faulty primary. Then, all non-faulty parties will commit to the log position $j$ by the end of view $v$.

Proof:

Observe that in any view $<v$, either some non-faulty replica commits and hence all non-faulty replicas commit one round later; or otherwise, all non-faulty do not commit, and hence will send a “blame” and hence all non-faulty will send a “view change”.

If some non-faulty parties have not committed to log position $j$ before entering view $v$, then all non-faulty will enter view $v$ within one message delay. In view $v$, the non-faulty primary will gather $n-(f+k)$ distinct “help done” messages and will send a commit message that will arrive to all the non-faulty parties before their $timer(v)$ expires (assuming the timer is larger than 6 message delays). Hence, even if all omission faulty send a “blame” message, there will not be a “view change” message.

Hence the non-faulty primary of view $v$ will continue to append messages to the log and will eventually reach position $j$.

Please answer/discuss/comment/ask on Twitter.