## 5 Algorithm
### Basis of the Algorithm
Boundary processes mark the leaves of the broadcast tree and identify the processes that need to initiate the secondary wave. Note that since the system starts in an arbitrary initial system configuration, continuous marking of the leaves is crucial. That is, a locked process does not experience a state change due to the states or state changes of any of its neighbors other than its parent. The secondary wave along with a mechanism of locking the boundary processes guarantee that the boundary processes only receive the broadcast from completed processes avoiding the specification violation mentioned in Lemma 1. Maintenance of this separation with boundary processes at all times requires that before the boundary processes receive the broadcast, all the neighbors of the boundary processes not included in the normal broadcast tree and are not boundary processes (level \(l+2\) processes) are designated as the new boundary processes. The secondary wave changes the states of the newly designated boundary processes to indicate that they are non-completed, locks them, and assigns some boundary processes as parents to them. Locking of the level \(l+2\) processes prevents state changes of level \(l+2\) processes due to arbitrary initialized processes. Notice that if a level \(l+2\) process \(i\) is not locked, due to the states of its neighbors not in the tree, process \(i\) may change its state and enter a broadcast phase and/or assume a parent included in an abnormal broadcast tree immediately before the broadcast advances to the parent of a process \(i\) leading to not maintaining boundary processes. That is, when the broadcast phase advances to the parent of process \(i\) (a boundary process), and process \(i\)'s parent encounters process \(i\) that has entered the broadcast phase due to arbitrary initialization, a normal broadcast tree is no longer maintained. Now, observe that if it was not locked, process \(i\)'s parent may prematurely enter the feedback phase without delivering the message to process \(i\) violating propagation reliability. As a result of locking process \(i\), a level \(l+2\) process, once included in the tree, cannot assume a parent other than its designated parent in the broadcast tree or enter broadcast or feedback phases due to the states of its neighbors not included in the normal tree. After locking and parent assignment in the tree for the level \(l+2\) processes, the broadcast tree is extended to the level \(l+2\) processes by making them the new boundary processes and making the neighbors of the level \(l+2\) processes that are neither boundary nor level \(l+2\) processes the new level \(l+2\) processes. Subsequently, the broadcast is extended to the current boundary processes. This concludes the current secondary wave and a new secondary wave can now be started. Prior to assigning parents to and locking of level \(l+2\) processes, no assumptions can be made about their states, particularly boundary processes cannot identify which of their neighbors are in level \(l+2\) based on the states of their neighbors. Therefore, the neighbors of the boundary processes (level \(l+2\) processes) that are not included in the broadcast tree yet need to be identified. For that purpose, the secondary wave collects the ids of all the neighbors of boundary processes, the _ids_ of the boundary processes, and the _id_'s of the leaf processes (level \(l\)) and identifies the level \(l+2\) processes as those that are neighbors of boundary but neither level \(l\) (leaf) nor level \(l+1\) processes. Recall that as proven by Lemma 2, advancement of the broadcast to the boundary processes while maintaining the boundary safety property cannot be implemented locally. Therefore, a mechanism of state collection such as the one implemented here is essential. We now describe the secondary wave in further detail. The secondary wave is initiated by the boundary processes in a normal broadcast tree \(T\) and the wave proceeds towards root process \(r\) in a bottom-up manner.