Agreement problems are a fundamental building block for constructing reliable distributed systems. While robust and efficient protocols exist in the crash-failure setting, protocols resilient against a Byzantine adversary tend to have problems with either efficiency or security. This paper proposes an optimistic approach to the Byzantine agreement problem, combining the efficiency of fully synchronous protocols with the robustness of asynchronous ones. If the system satisfies certain timing assumptions, and all parties are honest (the optimistic case), the protocol reaches optimal performance. Otherwise, if the timing assumptions are violated or parties become corrupted the protocol invokes an asynchronous "fallback'' protocol. Neither liveness nor security are violated in the transition, and the performance overhead is minimal. Furthermore, no expensive cryptographic operations are needed in the optimistic case, unlike in most practical Byzantine agreement protocols.
Thus, the optimistic approach gives a maximum of security while being more efficient than most (less secure) protocols.
By: K. Kursawe
Published in: RZ3202 in 2000
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .