2026-10-03T15:04:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24845 2026-02-09T06:41:51Z ddc:004 open_access

Byzantine Consensus in the Random Asynchronous Model Danezis, George Komatovic, Jovan Kokoris-Kogias, Lefteris Sonnino, Alberto Zablotchi, Igor network model asynchronous random scheduler Byzantine consensus 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik George Danezis and Jovan Komatovic and Lefteris Kokoris-Kogias and Alberto Sonnino and Igor Zablotchi 2025 Is Part Of LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2025.28 urn:nbn:de:0030-drops-248457 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.28 eng https://creativecommons.org/licenses/by/4.0/legalcode