A single protocol that spans three communication primitives

In this post, we present a protocol that implements three communication primitives: Reliable communication, Byzantine consistent broadcast, and Byzantine reliable broadcast. Before presenting the protocol, we first review the specification of these communication primitives.

Reliable communication

Byzantine consistent broadcast

Byzantine reliable broadcast

Every instance of Byzantine reliable broadcast has a designated sender process $s$, who broadcasts a message $m$. This abstraction provides two operations:

• $\mathtt{brbCast}(m)$ - through which $s$ broadcasts $m$.
• $\mathtt{brbDeliver}(m)$ - invoked by a receiver to deliver $m$ sent by $s$.

Any implementation of this abstraction must satisfy the following properties:

• Validity. If the sender is correct and broadcasts a message $m$, then every correct process eventually delivers $m$.
• No duplication. Every correct process delivers at most one message.
• Integrity. If some correct process delivers a message $m$ with sender $s$ and process $s$ is correct, then $m$ was previously broadcast by $s$.
• Consistency. If some correct process delivers a message $m$ and another correct process delivers a message $m’$,then $m = m’$.
• Totality. If some message is delivered by any correct process, every correct process eventually delivers a message.

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// Code for process i

echo = False
vote = False
reliableDeliver = False

upon broadcast(m)
   send <BROADCAST, m>ᵢ to all processes

upon receiving <BROADCAST, m>ⱼ from j 
   if echo == False
      trigger deliver(j, m)
      send <ECHO, <BROADCAST, m>ⱼ>ᵢ to all processes
      echo = True

upon receiving {<ECHO, <BROADCAST, m>ⱼ>ₖ | k ∈ Q} = M from a quorum Q
   if vote == False
      trigger consistentDeliver(j, m)
      send <VOTE, <BROADCAST, m>ⱼ>ᵢ to all processes
      vote = True

upon receiving {<VOTE, <BROADCAST, m>ⱼ>ₖ} from f+1 processes
   if vote == False
      trigger consistentDeliver(j, m)
      send <VOTE, <BROADCAST, m>ⱼ>ᵢ to all processes
      vote = True

upon receiving {<VOTE, <BROADCAST, m>ⱼ>ₖ | k ∈ Q} = M from a quorum Q
   if reliableDeliver == False
      trigger reliableDeliver(j, m)
      reliableDeliver = True