Consistent broadcast

Consistent broadcast has two operations associated with it: and which we want to implement by means of the communication primitives send and receive. Recall that the underlying communication mechanism provides point-to-point connections which are secure and authenticated. That is, each process can send a message directly to any other process and the receiver can be sure of the identity of the sender and that the content of the message has not been altered. Messages sent with the consistent broadcast facility consist of three parts: m=(c,p,r), where c is the message contents, p the sending process, and r the round in which the message is sent. Consistent broadcast has the following three properties:

correctness

If m=(c,p,r) is by $p \in L$ at round r then all $q \in L$ m at round r+2. Here, L, as before, denotes the set of correct processes.

unforgeability

If m=(c,p,r) is not by $p \in L$, then no $q \in L$ ever accepts it.

relay

If $q \in L$ accepts m at round r, then every $p \in L$ accepts it no later than round r+1.

The protocol that is used to achieve the above is described next. As before, there are at most f<n/3 faulty processes (implying that there are at least 2f+1 correct, or loyal). A sent message is received by the receiver in the next round, and messages are authenticated, i.e., they cannot be forged by traitors. Sending a message to ``all'' includes sending it to oneself. The following describes the implementation of and in terms of the primitive send and receive operations. Here a process p wants to at round r.

round r

The process p sends $[\mathrm{INIT}, (c,p,r)]$ to all processes.

round r+1

If q receives $[\mathrm{INIT}, (c,p,r)]$ from process p,
it sends $[\mathrm{ECHO}, (c,p,r)]$ to all processes.

round $t\geq r+2$

If process q receives $[\mathrm{ECHO}, (c,p,r)]$ from at least f+1 distinct processes, and it has not yet sent an echo, then it sends $[\mathrm{ECHO}, (c,p,r)]$.

round $t\geq r+2$

If process q receives $[\mathrm{ECHO}, (c,p,r)]$ from at least 2f+1 processes it performs .

The protocol has the correctness property since when $p \in L$ sends a message at round r, it is echoed by 2f+1 different $q \in L$ at round r+1, and thus accepted by every $q \in L$ at round r+2.

The unforgeability property follows because to accept a message at least 2f+1 echoes are required. An $[\mathrm{ECHO}, (c,p,r)]$ is triggered by two events only. The first way to trigger an echo is for a process to receive the message $[\mathrm{INIT}, (c,p,r)]$.Since the underlying mechanism is point-to-point, secure and authenticated, if an INIT message is not sent it cannot be forged. The second possibility is for a process to receive f+1 echoes. But this cannot happen either because there are at most f traitors.

The relay property follows since if $p \in L$ accepts at round r, it has received 2f+1 echoes, of which at least f+1 must be from correct processes. Thus, all correct processes receive f+1 echoes at round r and will therefore echo themselves, causing every $q \in L$ to accept at round r+1.