## 7 Proof of Correctness
By Lemma 5, leaf processes cannot join an normal broadcast tree and hence remain in state \(Cc\) until \(j\) enters state \(Cb\). When the bottom-up wave reaches the leaves as the processes enter state \(Bb\), the leaves enter state \(Cb\) instead of \(Bb\). Observe that the \(b\)-phase proceeds from root \(r\) to the leaves in at most \(D-1\) rounds. When process \(i\) enters state \(Cb\), process \(i\) waits until each one of their neighbors not in \(T\) enters state \(Cc\), locks, and points to the designated parent by the root (available in \(CorrInfo_{i}\)). Observe that each one of the neighbors \(j\) of \(i\) not in \(T\) can be in \(Cc\); however, its parent is not the one designated by the root in an abnormal state or in an abnormal tree. If process \(j\) is in an abnormal state or tree, then by Lemma 4, \(j\) enters state \(Cc\) in at most \(n\) rounds. By Proposition 2, process \(j\) will not enter any abnormal tree after entering state \(Cc\) in \(n\) rounds. If \(j\) is in state \(Cc\) and \(j\)'s parent is not the designated one by the root, it is easy to see that in one round guarded command \(i2\) is executed and \(j\) assumes the parent designated by the root. Subsequently, guarded command \(i2\) is enabled to assign a leaf in \(T\) designated by the root (available in \(CorrInfo_{i}\)) as a parent to each neighbor of \(i\) not in \(T\). When all the neighbors of \(i\) not in \(T\) enter \(Cc\) and assume the designated parent by the root and are locked, process \(i\) enters \(Bc\) in an additional round. After all the ancestors of \(i\) enter state \(Bc\) in a top-down manner in a \(Bc\) phase, then process \(i\) enters state \(Bc\) in one round. Therefore, it is easy to see that process \(i\) enters phase \(Bc\) in at most \(2D+1+n\) rounds. Hence, the proof follows. The following corollary, which states that after the completion of the secondary wave, all the neighbors of the leaves which are not in tree \(T\) are included in \(T\) as leaves to obtain normal tree \(T^{\prime}\), immediately follows from Proposition 1 and Lemma 6. Corollary 2: _In a normal system configuration where process \(r\) is enabled and is in state \(Cc\), root \(r\) is included in normal tree \(T\) as a leaf in one round. Let tree \(T\) be a normal tree immediately after the completion of a secondary wave. Immediately after the completion of the next secondary wave, all the neighbors of the leaves which are not in tree \(T\) are included in tree \(T\) as leaves._  
**Lemma 7** (Propagation Reliability): _Starting in any arbitrary system configuration, the broadcast is completed in \(2D^{2}+2(D+1)+n\) rounds, where \(D\) is the diameter of graph \(G\)._  
Starting in an arbitrary system configuration, we know that by Lemma 1, root \(r\) enters normal starting system configuration after \(n\) rounds. It is easy to see by Lemma 6 that the first secondary wave is completed in at most \(2D+1+n\) rounds. After the first secondary wave, at most \(D-1\) secondary waves are required to complete the broadcast. By Lemma 6, we know that after the first secondary wave is completed in \(2D+1+n\) rounds, each one of the subsequent secondary waves is completed in \(2D+1\) rounds. It is easy to see that after the first secondary wave is completed in \(2D+1+n\) rounds after the system starts, since there are \(D-1\) secondary waves remaining, we need \((D-1)(2D+1)\) rounds to complete the remaining in at most \(D-1\) remaining secondary waves. Hence, each process is guaranteed to enter state \(Bc\) in at most \(2D+1+n+(D-1)(2D+1)\) rounds. Observe that subsequently primary \(F\) and \(C\) waves are completed in at most \(D+1\) rounds. Therefore, the broadcast is completed after \(2D^{2}+2(D+1)+n\) rounds. Hence, the proof follows. The following theorem immediately follows from Lemmas 3, 5 and 7. **Theorem 1**: _The proposed algorithm is a 1-safe reliable broadcast algorithm which completes each broadcast in \(2D^{2}+2(D+1)+n\) rounds after starting in an arbitrary initial system configuration._