In this paper, we first prove that it is impossible to devise an asynchronous reliable broadcast algorithm that can start in an arbitrary initial system configuration where processes execute their actions solely based on local knowledge. We then propose the first asynchronous reliable broadcast algorithm that, starting in any arbitrary initial system configuration, ensures three properties, namely, premature feedback safety, propagation 1-safety, and propagation reliability. Premature feedback refers to the conclusion of a broadcast operation at a process although the process has neighbors that did not receive the most recent broadcast yet. Due to possessing the premature feedback safety property, the proposed algorithm always executes as per its specification without premature feedback and is able to implement propagation reliability with exactly once semantics. In addition, our proposed algorithm works even if the processes that the broadcast did not reach yet are perturbed by transient faults, making it more scalable compared to their counterparts requiring initialization.
Dabees et al. (Thu,) studied this question.