## 5 Algorithm  
In this section, we first provide some definitions to facilitate the description of the basis of the algorithm. Subsequently, we present two lemmas that establish the basis of our proposed algorithm. The first lemma states the required synchronization, and premature feedback safety, for any implementation of a broadcast algorithm that starts in an arbitrary initial system configuration. The second lemma shows that in any broadcast algorithm that starts in an arbitrary system configuration, actions cannot solely depend on local knowledge, knowledge collected from the process executing the action and its neighbors. The second lemma implies that any such algorithm needs to implement a mechanism to gather some non-local knowledge which is often implemented using waves in a distributed computational model. We then introduce the first asynchronous reliable broadcast algorithm.  
Our proposed algorithm constructs a _normal broadcast tree_ and extends the tree to the entire network to implement the broadcast. The normal broadcast tree refers to the broadcast tree rooted at root \(r\) satisfying the following three conditions:  
1. All the processes in the normal broadcast tree have received the broadcast directly or indirectly from root process \(r\);
2. All the neighbors of the processes in the broadcast phase in the tree that have not received a message from the root are in the cleaning phase, have assumed parents in the tree, and are _locked_;
3. Each path in the tree from root \(r\) to a leaf is made up of zero or more processes in broadcast phases followed by zero or more processes in the feedback phases which are followed by _zero_ or more processes in the cleaning phase.  
On the other hand, an _abnormal broadcast tree_ does not satisfy at least one of the above conditions. A process is said to be locked if it cannot change its parent so that the locked process in the normal broadcast tree does not assume a parent not included in the normal broadcast tree and receives a spurious message propagated by an abnormal broadcast tree. All the processes in the broadcast tree remain locked until the completion of the broadcast to avoid the interference of the processes that are not included in the normal broadcast tree.  
In a normal broadcast tree, the processes that have received a message from the root and do not have any children in the broadcast phase are referred to as _level-l processes_. The neighbors of the level-\(l\) processes in the cleaning phase are referred to as _boundary_ or _level \(l+1\)_ processes. Boundary processes are those non-completed processes in the cleaning phase with parents in the broadcast tree that are only allowed to receive the broadcast from a process in the normal broadcast tree. The boundary processes are not affected by the arbitrarily initialized processes due to being locked as locking prevents state changes in boundary processes caused by arbitrarily initialized processes. Therefore, non-completed boundary processes isolate the completed processes in the normal broadcast tree from the state changes caused by arbitrarily initialized processes, which in turn eliminates safety violations during the broadcast. A boundary process remains as a non-completed process in the cleaning phase until it receives a message from the legitimate root directly or indirectly. In addition, the neighbors of the boundary processes that are not included in the tree and not level-\(l\) processes are referred to as _level \(l+2\)_ processes.