Consensus with Byzantine Failures and Little System Synchrony

In distributed systems, consensus is the act of having all parts agreeing in choosing one value. E.g., in binary consensus problem, every correct process proposes some value in $\{0,1\}$ and must make an irrevocable decision on a value such that follow these properties:

• (Agreement) No two correct processes decide differently;
• (Validity) If some correct process decides v , then v is proposed by some correct process;
• (Termination) Every correct process eventually decides some value.

The consensus problem is at the core of fault-tolerant distributed systems. Solving consensus is impossible in asynchronous systems subject to process failures. A well-known way to overcome this impossibility is to make partial synchrony assumptions about the system, like relative speeds of processes are bounded, and all links are eventually timely (a message sent at the time $T$ are delayed at most $\Delta$ by the link).

This possibility result holds for a system $S_{crash}$ with crash failures and a system $S_{byz}$ with byzantine failures, with a resiliency of $n>2f+1$ and $n>3f+1$, respectively, where $n$ is the number of processes and $f$ is the maximum that can fail.

To solve consensus, is it really necessary that all links be eventually timely? What if only some links are eventually timely, while other links can be arbitrarily slow; can consensus still be solved? How these possibilities work for crash-failure and byzantine systems?

It has been proved in previous work that consensus is possible in a weaker system where at least one unknown faulty process whose $f$ outgoing direct links are eventually timed. This results only works for systems with crash failures.

In this paper, the authors evaluates these possibilities for byzantine systems by trying to solve consensus in a system with all processes with some eventually timed links. They have defined two systems (i) $S_{byz}$ where all the links are eventually timed and (ii) $S{ʹ}_{byz}$ where only the to and from links of the correct processes are eventually timed.

Their consensus algorithm uses consistent unique broadcast as subroutine, where messages have a tag to ensure that (1) correct processes deliver the same set of messages, and (2) a correct process delivers at most one message with a given tag. Tags are used to ensure that a byzantine process does not broadcast two different messages in the same round. They also use provable reliable send that guarantees that all message m sent by a correct process p will be delivered to q and other process r will get the proof about the delivery.

Subroutines

Consistent unique broadcast

Consistent unique broadcast is guaranteed by the following properties:

• (Validity) If a correct process p broadcasts (X,k,v) then all correct processes eventually cudeliver (X,k,v) from p_ ( (X,k) is the tag, and v is the value) ;
• (Unforgeability) If a correct process p does not broadcasts (X,k,v) then no correct process will ever deliver it.
• (Uniqueness) For each tag (X,k) and q, a correct process delivers at most one message with the tag. In other words, there is no correct process that will deliver the same message more than once.
• (Relay) If a correct process delivers (X,k,v) from p then all correct processes will eventually deliver the message.

Provable reliable send

Provable reliable send guarantees that if p is correct then all correct processes r gets the proof that m is in transit, and if a correct process r gets the proof that m is in transit, and q is correct, then q receives m. In other words, a process r gets the proof that m is in transit if p is a correct process and have sent m, and q is a correct process and have received m. The provable reliable send follows these properties:

• (Integrity) A correct process q receives m from a correct process p at most once, and only if p has previously sent m to q;
• (Validity) If some correct process p sends m to some correct process q then eventually q receives m from p;
• (Proof-Integrity) If some correct process r gets the proof of m from some process p to some correct process q then q receives m from p;
• (Proof-Validity) If some correct process p sends m to some process q then every correct process r gets the proof of m from p to q.
• (Eventual timeliness) If process q is a bisource (a process whose incoming and outgoing links are eventually timely) then there exists $\Delta ʹ$ and $Tʹ$ such that if some correct process r gets the proof of m from some process p to process q at time t then q receives m from p by time $max\{t,Tʹ\}+\Delta ʹ$. In other words, if r have the proof of m being sent at the time t from p, then the message m must be delivered at a time $max\{t,Tʹ\}+\Delta$ .

Consensus

They use the previous subroutines to implement consensus. They have derived their consensus algorithm from Ben-Or's randomized algorithm. Here, each process $p_{i=1...n}$ keeps a current estimate of the decision value, which is initially the value that $p_0$ proposes to consensus. The algorithm proceeds by rounds, where each round has four phases: certification, reporting, proposing, and consulting the coordinator where all process exchange the proposed v until all agree on the same value.

They have concluded with this algorithm that consensus is possible in system $S_{byz}$, in which all non-faulty process whose incoming and outgoing links are all eventually timely. This means that consensus is not possible in a $S{ʹ}_{byz}$ systems (some correct process does not have all links eventually timed). In other words, it is not possible to tolerate byzantine failures if it exists at least one non-faulty process s whose $n-1$ or $f$ outgoing links are eventually timed (in this situation, consensus is only possible in system that tolerates crash faults).