Hybrid Byzantine Agreement

Abstract: Consensus is a central problem of distributed data processing by tolerating errors. Unfortunately, it is not possible to solve such a problem in asynchronous systems that are vulnerable to process failures. In order to decisively circumvent this impossibility (known as FLP impossibility), several protocols have been proposed in addition to asynchronous systems enriched with additional hypotheses. Two approaches have been studied to solve the problem of Byzantine consensus in a deterministic way in systems where maximum t processes can have byzantine behavior. The first is based on the addition of Synchron, called based timekeeper, while the second, called Time-Free, is based on the message exchange model. This paper shows that the two types of hypotheses are not antagonistic and can be combined to resolve an authenticated Byzantine consensus. The combined hypothesis takes into account a correct process pi, called ?-t-1-BW, and an X-game of correct processes (including pi itself), so that for any query released through a correct pj process of X, pj a response of ft ? X among the first responses to that query or the two links that connect pi and pj Timely. Based on this combination, a simple hybrid authenticated Byzantine consensus protocol is proposed, taking advantage of the best of both worlds. Although many hybrid protocols have been designed for the problem of consensus in the crash model, this is, to our knowledge, the first hybrid deterministic solution to the problem of the Byzantine consensus. We are introducing a complete hybrid error model for synchronized distributed systems, which adds communication errors to a traditional hybrid process error model: each process in the system can spread to fls-transmitter-link failures and occur here until flr connection failures per tower without being considered defective; up to a few flsa?fls and flra?flr among which can even cause fake news, instead of just omissions. In an accompanying paper (Schmid et al.

(2009) [14], devoted to a comprehensive set of impossibilities and lower limits, we demonstrated that this model surpasses all existing approaches to modeling connection errors in terms of acceptance coverage in a simple probabilistic environment.