## 7 Proof of Correctness  
In this section, we first define a few terms used in the proofs, then present the proof outline, followed by the proof for the proposed algorithm. Root \(r\), referred to as the _normal root_, is the only process that receives a message as input to broadcast to the network. Any process without a parent other than \(r\) and is the root of a tree is called an _abnormal root_. **Proposition 1**: _Starting in an arbitrary system configuration, in the execution of the first enabled action of the proposed algorithm, process \(i\) may only receive a spurious message from an illegitimate source, while it is impossible to receive a message from a legitimate source._  
**Definition 1**: _A normal starting configuration with respect to root \(r\) refers to a system configuration in which \(input()\wedge S_{r}=C\wedge S^{{}^{\prime}}_{r}=c\wedge\forall_{j\in N_{r}}(P_ {j}=r\wedge S_{j}=C\wedge L_{j}=1\wedge S^{{}^{\prime}}_{j}=c\wedge lock_{j})\) holds._  
**Definition 2** (normal broadcast tree): _A tree \(T\) is a normal broadcast tree if it satisfies the following three conditions:_  
1. _[label=()]_
2. _Tree_ \(T\) _is rooted at process_ \(r\)_._
3. _Each internal process_ \(i\) _in the normal tree satisfies_ \(L_{i}=L_{P_{i}}+1\wedge Lock_{i}\wedge S_{i}=B\) _and each leaf process_ \(i\) _satisfies_ \(S_{i}=C\wedge lock_{i}\wedge L_{i}=L_{P_{i}}+1\)_._
4. _For root_ \(r\) _of tree_ \(T\)_,_ \(P_{r}=\bot\) _holds and for any internal or leaf process_ \(i\) _in_ \(T\)_, if_ \(j\) _is the parent for process_ \(i\)_, then_ \(P_{i}=j\)_._  
**Lemma 3** (1-safety): _In any arbitrary system configuration, let \(i\) be a process included in an normal broadcast tree after the system starts. No process joins the abnormal tree by assuming process \(i\) as its parent and entering state \(Bc\)._  
Notice that immediately after the system starts, only if process \(i\) is a leaf (boundary process) in an abnormal tree, in state \(Cb\), locked, and all \(i\)'s children are in \(Cc\) and locked, then process \(i\) enters state \(Bc\) (Guard \(ib7\)). Then, \(i\)'s children enter state \(Cf\) (Guard \(if3\)) and start the secondary wave and wait until entering \(Bc\). However, in an abnormal tree,  
Figure 6: Illustrative example for normal system configuration (rounds 16–20). when the secondary wave initiated by \(i\)'s children reaches the root of the abnormal tree, the abnormal root cannot start the top-down \(b\)-phase which facilitates that \(i\)'s children enter \(Bc\). Therefore, no child of \(i\) can enter state \(Bc\). Hence, the proof follows. **Lemma 4** (Abnormal State Delay). : _Starting in an arbitrary system configuration where \(i\) is in an abnormal tree, process \(i\) enters state \(Cc\) in at most \(n\) rounds._  
Proof. : Let process \(i\) be a process in an abnormal tree. We are to show that process \(i\) enters \(Cc\). Observe that by Lemma 3, the height of the abnormal tree cannot increase by more than one. By the definition of abnormal tree, the root of the abnormal tree containing process \(i\) is in an abnormal state and is enabled to execute guarded command \(rCa\) or \(iCa\). Then by the weak fairness assumption, the root of the abnormal tree enters \(Cc\) in one round, which reduces the height of the abnormal tree containing process \(i\) by one. Observe that the new root of the abnormal tree containing process \(i\) is now enabled to execute guarded command \(iCa\). Inductively, it can be shown that the abnormal tree(s) containing \(i\) vanishes in at most \(n\) rounds. Hence the proof follows. The following corollaries immediately follow from Lemma 4. **Corollary 1** (Delay). : _After starting in an arbitrary system configuration, the system enters a normal starting configuration in O(\(n\)) rounds._  
Proof. : Upon system start, by Lemma 4 root \(r\) enters state \(Cc\) in \(n\) rounds and the system enters the normal starting configuration \(n+1\) rounds. The following proposition immediately follows from Lemmas 3 and 4. **Proposition 2**.