## 5 Algorithm
### Basis of the Algorithm  
In this section, we introduce the basis of the proposed algorithm and provide essential definition. _Premature feedback safety_ is a process synchronization such that a broadcast algorithm is said to satisfy premature feedback safety iff a _completed non-broadcasted_ process cannot become completed broadcasted or _non-completed_ prior to all its neighbors receiving the most recently broadcasted message. A completed process refers to a process that has received the most recent message broadcasted by a source process, or a _non-completed process_ otherwise. A process is referred to as a broadcasted process iff all its neighbors have received the most recently broadcasted message and non-broadcasted otherwise. The following lemma shows the role of maintaining premature feedback safety in implementing propagation reliability for broadcast algorithms. In particular, it shows that if premature feedback safety is not implemented by a broadcast algorithm, propagation reliability cannot be guaranteed after starting in an arbitrary initial system configuration. In other words, premature feedback safety is implemented if, for any completed non-broadcasted process \(i\in V\) and in any system configuration, process \(i\) never becomes broadcasted or non-completed without broadcasting its message to all its neighbors. **Lemma 1** (Premature Feedback Safety Requirement). : _Starting in an arbitrary system configuration, if a broadcast algorithm does not implement premature feedback safety, propagation reliability cannot be implemented using only local knowledge under the locally shared memory modules model._  
Proof. : Let process \(i\) and \(j\) be two neighboring processes where process \(i\) received message \(M\) from the legitimate source and process \(j\) received message \(M^{\prime}\) from an illegitimate source, where \(M\
eq M^{\prime}\). Notice that process \(j\) can be in a state which indicates that \(j\) is a completed process due to arbitrary initialization though has received broadcast from an illegitimate source. Observe that since it cannot be decided as to which message (\(M\) or \(M^{\prime}\)) is sent by root process \(r\) based on process \(i\)'s and process \(j\)'s states using local knowledge, i.e., it cannot be decided as to which message shall propagate to the other process. Now, process \(j\) is not guaranteed to receive the legitimate broadcast from the legitimate root. Thus, the propagation reliability is violated. Hence, the proof follows. The above lemma merely states that any implementation of a reliable broadcast algorithm under the locally shared memory modules model that starts in an arbitrary system configuration needs to implement premature feedback safety. The following lemma states that starting in an arbitrary initial system configuration, an asynchronous reliable broadcast cannot be implemented with only local knowledge. **Lemma 2** (Non-Local Knowledge Requirement). : _There does not exist an asynchronous reliable broadcast algorithm that implements premature feedback safety and can solely rely on local knowledge._  
**Proof. ** Assume that process \(i\) is a boundary process. Before advancing the broadcast to process \(i\), each non-completed neighbor \(j\) of \(i\) needs to become a boundary process. This is because if a non-completed neighbor \(j\) of \(i\) is not made a boundary process, \(j\) can receive a message from a non-completed process violating the boundary reliability requirement by Lemma 1. This requires the identification of whether or not each process \(j\) is a non-completed non-boundary process since only the non-completed non-boundary processes are to be made boundary processes prior to advancement of the broadcast to process \(i\). Due to arbitrary initialization, process \(j\)'s state and the state of process \(j\)'s neighbors may indicate that it is a completed process. Then clearly, in the absence of synchronization, process \(i\)'s local knowledge cannot distinguish whether process \(j\) is completed or not. Hence, the proof follows.