DARE to Agree: Byzantine Agreement With Optimal Resilience and Adaptive Communication
Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Lewis Gilbert, Rachid Guerraoui, Jovan Komatovic, Manuel Vidigueira · 2024
Byzantine Agreement (BA) enables n processes to reach consensus on a common valid Lo-bit value, even in the presence of up to t n/3. Different instantiations of ada-Dare achieve near-optimal adaptive bit complexity of O(nLo + n(f + 1)κ) for both strong multi-valued validated BA (SMVBA) and interactive consistency (IC). By definition, for IC, Lo = nLin where Lin is the size of an input value. These results achieve optimal O(n(Lo + f)) word complexity and significantly improve the previous best results by up to a linear factor, depending on Lo and f.