Adding Byzantine tolerance to large scale distributed systems is considered non-practical. The time, message and space requirements are very high. Recently, researches have investigated the broadcast problem in the presence of a f_e-local Byzantine adversary. The local adversary cannot control more than f_e neighbors of any given node. This paper proves sufficient conditions as to when the synchronous Byzantine consensus problem can be solved in the presence of a f_e-local adversary. Moreover, we show that for a family of graphs, the Byzantine consensus problem can be solved using a relatively small number of messages, and with time complexity proportional to the diameter of the network. Specifically, for a family of bounded-degree graphs with logarithmic diameter, O(log n) time and O(n log n) messages. Furthermore, our proposed solution requires constant memory space at each node.
展开▼
