Partial Synchrony for Free? New Upper Bounds for Byzantine Agreement

Overview

• Byzantine agreement allows multiple processes to agree on a common value, even if some processes fail in arbitrary ways
• The Dolev-Reischuk bound states that any deterministic solution to Byzantine agreement must exchange at least Ω(n²) bits, where n is the number of processes
• Optimal solutions with O(n²) bit complexity and optimal fault tolerance have been known for decades, but lack robustness under adverse network conditions
• Recent research has focused on Byzantine agreement in partially synchronous networks, but existing solutions are complex and require O(n³) bits in the worst case

Plain English Explanation

Optimizing Distributed Protocols for Query Rewrites - Technical Report describes a fundamental problem in distributed computing called Byzantine agreement. In this problem, a group of n processes needs to agree on a common value, even if some of the processes are behaving in unexpected or malicious ways (e.g., sending incorrect information).

The researchers explain that an important theoretical result, the Dolev-Reischuk bound, shows that any deterministic solution to Byzantine agreement must exchange at least Ω(n²) bits of information. This means that the amount of data that needs to be communicated grows quadratically with the number of processes.

Over the past few decades, researchers have developed solutions to Byzantine agreement that achieve this optimal O(n²) bit complexity and are also optimally resilient (able to tolerate up to n-1 failures). However, these solutions assume a perfectly synchronous network, where all processes can reliably communicate with each other at the same time. In reality, networks often experience delays and other disruptions, so these solutions may not be robust enough.

Therefore, the researchers have been focusing on Byzantine agreement in partially synchronous networks, where the timing of communications is not as reliable. The Robust Constrained Consensus for Inequality Constrained Distributed Optimization paper and the OLYMPIA: A Simulation Framework for Evaluating Concrete Scalability and Security of Decentralized Systems paper explore this more realistic setting. However, the existing solutions for partially synchronous Byzantine agreement are complex and still require a lot of communication, up to O(n³) bits in the worst case.

Technical Explanation

In this paper, the researchers introduce a new technique called Oper, which is a generic transformation that can convert deterministic Byzantine agreement algorithms designed for synchronous networks into algorithms that work in partially synchronous networks. Oper has several key properties:

1. It does not require any cryptography, making it simpler and more efficient.
2. It is optimally resilient, meaning it can tolerate up to n-1 faulty processes (as long as n ≥ 3t+1, where t is the maximum number of failures).
3. It preserves the worst-case per-process bit complexity of the original synchronous algorithm.

By leveraging Oper, the researchers present the first partially synchronous Byzantine agreement algorithm that:

1. Achieves the optimal O(n²) bit complexity.
2. Requires no cryptography.
3. Is optimally resilient (n ≥ 3t+1).

This shows that the Dolev-Reischuk bound is tight even in partially synchronous networks, meaning that the lower bound on communication complexity cannot be improved.

Furthermore, the researchers adapt Oper to handle long input values and obtain several new partially synchronous algorithms with improved complexity and weaker (or completely absent) cryptographic assumptions.

Critical Analysis

The researchers acknowledge that their Oper transformation and the resulting partially synchronous Byzantine agreement algorithms are not without limitations. For example, they assume a partially synchronous network model, which may not capture all the complexities of real-world distributed systems.

Additionally, the Adversary Augmented Simulation to Evaluate Fairness of Hyperledger Fabric's Ordering Service paper highlights the importance of considering adversarial network conditions when evaluating the performance and robustness of distributed protocols.

The researchers also mention that their solutions may not be as efficient as some existing partially synchronous Byzantine agreement algorithms that rely on cryptography. The trade-off between cryptographic assumptions and communication complexity is an active area of research, and the Round-Optimal Dollar(n)Dollar Block Broadcast Schedules in Logarithmic Time paper explores this topic further.

Despite these potential limitations, the researchers' work represents a significant contribution to the field of Byzantine agreement, as it provides a generic transformation that can bridge the gap between synchronous and partially synchronous solutions, while preserving key properties like optimal resilience and communication complexity.

Conclusion

This paper introduces a novel technique called Oper, which allows deterministic Byzantine agreement algorithms designed for synchronous networks to be adapted for partially synchronous networks. The key benefits of Oper are that it requires no cryptography, is optimally resilient, and preserves the communication complexity of the original synchronous algorithm.

By leveraging Oper, the researchers present the first partially synchronous Byzantine agreement algorithm that achieves optimal O(n²) bit complexity, optimal resilience, and no cryptographic assumptions. This is a significant result, as it shows that the Dolev-Reischuk lower bound on communication complexity is tight even in the more realistic partially synchronous setting.

The researchers' work advances the state of the art in Byzantine agreement and could have important implications for the design of robust and efficient distributed systems that need to reach consensus in the face of potential failures or malicious behavior.