## 5 Algorithm
### Basis of the Algorithm
The above lemma implies that starting in an arbitrary initial system configuration, any asynchronous broadcast algorithm that ensures premature feedback safety needs to implement mechanisms for processes to collect knowledge beyond their neighbors. For example, this mechanism may involve initiating a new fresh wave to check whether or not the processes to be included in the normal broadcast tree prior to extending the broadcast to a new set of processes. We now provide the basis of the 1-safe and reliable broadcast algorithm based on the above lemmas, then give the detailed description of the algorithm followed by its formal specification. The proposed algorithm needs to meet the following challenges. First, between every completed process and a non-completed non-boundary process, at least one boundary process is maintained at all times. Second, as the broadcast proceeds to the boundary processes, the next set of boundary processes needs to be determined, and they need to be made the new boundary processes when the broadcast proceeds in the presence of arbitrary initialization. Third, some process synchronization (premature feedback safety) needs to be implemented so that boundary processes only receive the broadcast from completed processes. The proposed algorithm uses two concurrent waves, namely the _primary wave_ and the _secondary wave_, to implement the asynchronous reliable broadcast. The primary wave constructs and contracts a broadcast tree rooted at process \(r\) using a top-down _broadcast phase_, followed by two consecutive bottom-up phases called _feedback_ and _cleaning_. A process is in a broadcast phase when it is involved in a message broadcast, in a bottom-up feedback phase when it is involved in acknowledging the root about the completion of the broadcast phase, and in a cleaning phase when it is involved in cleaning the trace of the broadcast tree. On the other hand, the secondary wave is used to verify the normality of a broadcast tree before the advancement of the primary wave to a new set of processes while implementing mechanisms to ensure premature feedback safety. A secondary wave in tree \(T\) consists of one bottom-up feedback phase, an \(f\)-phase, starting from the leaves, followed by one top-down phase, a \(b\)-phase, followed by a bottom-up cleaning phase and a \(c\)-phase. The primary wave, initiated by root process \(r\), broadcasts a message received from the application protocol process of \(r\) while simultaneously constructing a broadcast tree rooted at \(r\). In the beginning, root \(r\) constructs a broadcast tree which contains only root \(r\) as a boundary process. Subsequently, the broadcast tree advances to the neighbors of \(r\) by making neighbors of \(r\) boundary processes and \(r\) a completed process. Then, prior to each advancement of the broadcast to boundary processes, a fresh secondary bottom-up wave in the broadcast tree is used to verify the normality of the broadcast tree and inform the root about the normality of the broadcast tree. Notice that a fresh wave is essential for the implementation of the broadcast algorithm with premature feedback safety since local knowledge is insufficient as stated by Lemma 2. Subsequently, the root informs boundaryprocesses of the result of the verification using a top-down wave to advance the broadcast. The advancement takes place as all the non-completed neighbors of boundary processes become new boundary processes and all the boundary processes become completed processes. The verification of the normality of the broadcast tree, the information gathering and dissemination by the secondary wave prior to the advancement of the broadcast, implements the boundary safety and 1-safety of the broadcast and facilitates level-by-level construction of the broadcast tree where, after each secondary wave, the broadcast advances only to all the current boundary processes. The secondary wave implements the required synchronization by ensuring that at all times completed processes and non-completed processes are separated by boundary processes.