Prioritized-MVBA: A New Approach to Design an Optimal Asynchronous Byzantine Agreement Protocol

作者：Nasit S Sony, Xianzhong Ding · 发表于：International Journal of Information Security · 年份：2026 · DOI：10.1007/s10207-026-01214-4 · 研究领域：Distributed systems and fault tolerance、Ammonia Synthesis and Nitrogen Reduction、Age of Information Optimization

Abstract Multi-valued Byzantine agreement (MVBA) protocols are critical components in designing atomic broadcast and fault-tolerant state machine replication protocols in asynchronous networks. While these protocols have seen significant advancements, challenges remain in optimizing their communication and computation efficiency without sacrificing performance. In this paper, we address the challenge of achieving agreement in MVBA without incurring extra computation and communication rounds. Our approach leverages an analysis of message distribution patterns in asynchronous networks, observing that a subset of $$f+1$$ f + 1 parties, including at least one honest party, can achieve an agreement more efficiently than relying on all n parties, where $$n=3f+1$$ n = 3 f + 1 , f maximum number of faulty parties. We introduce a novel protocol, Prioritized-MVBA (pMVBA), which integrates a committee-based selection process and the asynchronous binary Byzantine agreement (ABBA) protocol. In this design, a randomly selected subset of $$f+1$$ f + 1 parties broadcast their requests, collect verifiable proofs, and utilize these proofs within the ABBA framework to reach an agreement. The proposed pMVBA protocol is resilient to up to $$\lfloor \frac{n}{3} \rfloor $$ ⌊ n 3 ⌋ Byzantine failures and achieves optimal performance, with an expected runtime of O (1), message complexity of $$O(n^2)$$ O ( n 2 ) ...