OPTIMAL TIME BYZANTINE AGREEMENT FOR T-LESS-THAN-N 8 WITH LINEAR-MESSAGES/

This paper presents a Byzantine Agreement protocol with n = 8t + 1, op timal number of rounds (namely min {f + 2, t + 1} where f is number of actual faults), and messages of linear size (namely m less than or eq ual to n + O (log n), where m stands for message size). All previous p rotocols that stop in optimal time and tolerate t = O (n) faults requi re mess ages of size at least O (n(2)). The new protocol uses a novel technique called Reconstructed Traversal which is based on the Reconst ruction Principle and on the Coordinated Traversal protocol.