Implementing Uniform Reliable Broadcast with Binary Consensus in Systems with Fair-Lossy Links

When implementing multivalued consensus using binary consensus, previous algorithms assume the availability of uniform reliable broadcast, which is not implementable in systems with fair-lossy links. In this paper, we show that with binary consensus we can implement uniform reliable broadcast directly in systems with fair-lossy links, and thus the separate assumption of the availability of uniform reliable broadcast is not necessary. We further prove that any implementation of uniform reliable broadcast in the fair-lossy link model requires the invocation of an infinite number of binary consensus instances even if no process ever broadcasts any messages, and this is true even when multivalued consensus is used. We also prvoide a more efficient algorithm implementing uniform reliable broadcast using multivalued consensus. Finally, we prove that both algorithms also satisfy a strong uniform total order property, and thus they actually implement strong uniform atomic broadcast.