Byzantine Lattice Agreement in Asynchronous Systems

02/17/2020
by   Xiong Zheng, et al.
0

We study the Byzantine lattice agreement (BLA) problem in asynchronous distributed message passing systems. In the BLA problem, each process proposes a value from a join semi-lattice and needs to output a value also in the lattice such that all output values of correct processes lie on a chain despite the presence of Byzantine processes. We present an algorithm for this problem with round complexity of O(log f) which tolerates f < n/5 Byzantine failures in the asynchronous setting without digital signatures, where n is the number of processes. We also show how this algorithm can be modified to work in the authenticated setting (i.e., with digital signatures) to tolerate f < n/3 Byzantine failures.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset