Byzantine Consensus in the Random Asynchronous Model

We propose a novel relaxation of the classic asynchronous network model, called the random asynchronous model, which removes adversarial message scheduling while preserving unbounded message delays and Byzantine faults. Instead of an adversary dictating message order, delivery follows a random schedule. We analyze Byzantine consensus at different resilience thresholds ($n=3f+1$, $n=2f+1$, and $n=f+2$) and show that our relaxation allows consensus with probabilistic guarantees which are impossible in the standard asynchronous model or even the partially synchronous model.

We complement these protocols with corresponding impossibility results, establishing the limits of consensus in the random asynchronous model.