Answers are grounded in this paper and cite their sources.
Asynchronous common subset (ACS) is a powerful paradigm enabling applications such as Byzantine fault-tolerance (BFT) and multi-party computation (MPC). The most efficient ACS framework in the information-theoretic setting is due to Ben-Or, Kelmer, and Rabin (BKR, 1994). The BKR ACS protocol has been both theoretically and practically impactful. However, the BKR protocol has an O(log n) running time (where n is the number of replicas) due to the usage of n parallel asynchronous binary agreement (ABA) instances, impacting both performance and scalability. Indeed, for a network of 16 ~ 64 replicas, the parallel ABA phase occupies about 95% ~ 97% of the total runtime in BKR. A long-standing open problem is whether we can build an ACS framework with O(1) time while not increasing the message or communication complexity of the BKR protocol.
No takes yet. Share an insight, caveat, or question.
Duan et al. (2023) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: