TY - GEN

T1 - Synchronous byzantine agreement with nearly a cubic number of communication bits

AU - Kowalski, Dariusz R.

AU - Mostéfaoui, Achour

PY - 2013

Y1 - 2013

N2 - This paper studies the problem of Byzantine consensus in a synchronous message-passing system of n processes. The first deterministic algorithm, and also the simplest in its principles, was the Exponential Information Gathering protocol (EIG) proposed by Pease, Shostak and Lamport in [19]. The algorithm requires processes to send exponentially long messages. Many follow-up works reduced the cost of the algorithm. However, they had to either lower the maximum number of faulty processes t from the optimal range t < n/3 to some smaller range of t [4, 11, 18], or increase the maximum worst-case number of rounds needed for termination (the lower bound being t + 1) [3, 9, 20]. Garay and Moses were the first and only who solved the problem by using a polynomial number of communication bits, for the whole optimal range t < n/3 of the number of Byzantine processes and within the optimal number (t+1) of communication rounds. Their solution, though very complex and sophisticated, requires processes to send O(n9) bits in total. In this work, we present much simpler solution that also holds for the whole optimal range t < n/3 and the optimal number t + 1 of communication rounds, and at the same time lowers the number of exchanged communication bits to O(n3 log n). For achieving such an improvement, processes no more exchange relayed proposed values, but information on suspicions "who suspects who", the size of which is quadratic in n in the worst case.

AB - This paper studies the problem of Byzantine consensus in a synchronous message-passing system of n processes. The first deterministic algorithm, and also the simplest in its principles, was the Exponential Information Gathering protocol (EIG) proposed by Pease, Shostak and Lamport in [19]. The algorithm requires processes to send exponentially long messages. Many follow-up works reduced the cost of the algorithm. However, they had to either lower the maximum number of faulty processes t from the optimal range t < n/3 to some smaller range of t [4, 11, 18], or increase the maximum worst-case number of rounds needed for termination (the lower bound being t + 1) [3, 9, 20]. Garay and Moses were the first and only who solved the problem by using a polynomial number of communication bits, for the whole optimal range t < n/3 of the number of Byzantine processes and within the optimal number (t+1) of communication rounds. Their solution, though very complex and sophisticated, requires processes to send O(n9) bits in total. In this work, we present much simpler solution that also holds for the whole optimal range t < n/3 and the optimal number t + 1 of communication rounds, and at the same time lowers the number of exchanged communication bits to O(n3 log n). For achieving such an improvement, processes no more exchange relayed proposed values, but information on suspicions "who suspects who", the size of which is quadratic in n in the worst case.

KW - Agreement problem

KW - Byzantine process

KW - Consensus

KW - EIG

KW - Message-passing model

KW - Round-based protocol

KW - Synchronous distributed system

UR - http://www.scopus.com/inward/record.url?scp=84883539543&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84883539543&partnerID=8YFLogxK

U2 - 10.1145/2484239.2484271

DO - 10.1145/2484239.2484271

M3 - Conference contribution

AN - SCOPUS:84883539543

SN - 9781450320658

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 84

EP - 91

BT - PODC 2013 - Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing

T2 - 2013 ACM Symposium on Principles of Distributed Computing, PODC 2013

Y2 - 22 July 2013 through 24 July 2013

ER -