Common use of end if Clause in Contracts

end if. Algorithm 1: Implementing ND-broadcast in BAMPn,t[t < n/3] When a process pi wants to ND-broadcast a message whose content is vi, it broadcasts the message ND INIT(i, vi) (line 1). When a process receives a message ND INIT(j, −) for the first time, it broad- casts a message ND ECHO(j, v) where v is the data content of the ND INIT() message (line 2). If the message ND INIT(j, v) received is not the first message ND INIT(j, −), pj is Byzantine and the message is discarded. Finally, when pi has received the same message ND ECHO(j, v) from (n − t) different processes, it locally ND-delivers MSG(j, v) (lines 3-4). The algorithm considers an instance of ND-broadcast, i.e., a correct process invokes at most once ND-broadcast. Adding a sequence number to each message allows each process to ND-broadcast a sequence of messages. Theorem 1. Algorithm 1 implements ND-broadcast in the system model BAMPn,t[t < n/3]. 1A similar vocabulary will be used for the abstractions MV-broadcast and SMV-broadcast introduced in Section 3. Proof To prove the ND-termination property, let us consider a non-faulty process pi that ND-broadcasts the message MSG(vi). As pi is non-faulty, the message ND INIT(i, vi) is received by all the non-faulty processes, which are at least (n − t), and every non-faulty process broadcasts ND ECHO(i, vi) (line 2). Hence, each non-faulty process receives the message ND ECHO(i, vi). from (n − t) different processes. It follows that every non-faulty process eventually ND-delivers the message MSG(i, vi) (lines 3-4). To prove the ND-no-duplicity property, let us assume by contradiction that two non-faulty processes pi and pj ND-deliver different messages m1 and m2 from some process pk (i.e., m1 = MSG(k, v) and m2 = MSG(k, w), with v /= w). It follows from the predicate of line 3, that pi received ECHO(k, v) from a set of (n − t) distinct processes, and pj received ECHO(k, w) from a set of (n − t) distinct processes. As n > 3t, it follows that the intersection of these two sets contains a non-faulty process. But, as it is non-faulty, this sent the same message ND ECHO() to pi and pj (line 2). Hence, m1 = m2, which contradicts the initial assumption. To prove the ND-validity property, we show that, if Byzantine processes forge and broadcast a message ND ECHO(i, w) such that pi is correct and has never invoked ND broadcast MSG(w), then no correct process can ND-deliver MSG(i, w). Let us observe that at most t processes can broadcast the message ND ECHO(i, w). As t < n − t, it follows that the predicate of line 3 can never be satisfied at a correct process. Hence, if pi is correct, no correct process can ND-deliver from pi a message that was not been ND-broadcast by pi. ✷T heorem 1 It is easy to see that this implementation uses two consecutive communication steps and O(n2) underlying messages (n − 1 in the first communication step, and n(n − 1) in the second one). Moreover, there are two types of protocol messages, and the size of the control information added to a message is log2 n (sender identity).