Affiliations: Department of Information Management, Chaoyang
University of Technology, 168 Gifeng E. Rd., Wufeng, Taichung County, Taiwan
413, R.O.C. | Department of Computer & Information Science,
National Chiao Tung University 1001, Ta Hsueh Road, Hsinchu, Taiwan 300,
R.O.C.
Abstract: The Byzantine Agreement (BA) problem is a fundamental problem to
consider in designing a fault-tolerance distributed system. Most BA protocols
require all the fault-free processors to reach a common agreement at the same
round, called an Immediate Byzantine Agreement (IBA), whereas another type of
BA protocol allows the fault-free processors to reach a common agreement,
called an Eventual Byzantine Agreement (EBA), at different rounds when they
receive enough information. Up to now, all the existing EBA protocols are
designed to solve the EBA problem based on the single failure type assumption
(dormant fault only or malicious fault only) as to fallible processors over a
reliable fully connected network. However, in practice, most network topologies
would not be fully connected, and the underlying network would not be reliable,
which means both dormant and malicious faults may occur within the same network
simultaneously. In this study, we shall propose a new protocol to solve the EBA
problem with dual failure mode on both processors and communication media (both
dormant and malicious faults can happen simultaneously to either the processors
or the communication media or both) over an unreliable un-fully connected
network. The proposed protocol is the optimal when the above assumptions are
considered.
