ESSEN - An Efficient Single Round Signature Protected Message Exchange Agreement Protocol for Wireless Distributed Networks

Abstract:
Byzantine agreement is a well-studied problem with many solutions for distributed computing systems. However, solving the Byzantine agreement problem in an efficient way in terms of communication complexity is still a challenging task. For example, in synchronous distributed systems with stringent time requirements not only the fault tolerance capability, but also the communication complexity is crucial for the practical usability. By this work an agreement protocol with minimal communica-tion complexity and maximal fault tolerance is aimed at. The protocol suits to synchronous wired as well as wireless dis-tributed systems, where the focus is put on the latter. A novel synchronous single-round-based agreement protocol for wireless networks – called ESSEN – is presented, which copes with f arbitrary faults (including malicious cooperative Byzantine faults) using at least ?? > ?? + ??² + ??/??+(?? – ??)/?? nodes. Moreover, this is the first approach which solves the Byzantine agreement problem in a single broadcast round independent of the number of tolerated faults.