X. Liu and J. Pu (PRC)
consensus, byzantine failure, eventual timeliness, partialsynchrony
This paper considers solving consensus in an n-process distributed system where the processes are pairwise connected by reliable links and up to f < n/3 unknown processes are subject to Byzantine failures. It is well known that if either all the processes or all the links are asynchronous, consensus can’t be solved. A natural way circumventing the impossibility is to enhanced the processor and links with some synchrony. It is a long-standing challenge to study the least synchrony under which consensus can be solved. Under the non-authenticated Byzantine failure model and partially synchronous process model, the best result in the literature is that a ♦n−1-bisource is enough for solving consensus. That is, if the links between a correct process and all the other processes are eventually timely, consensus can be solved. This paper show that a ♦3f -bisource is also enough, so we only require that the links between some correct process and 3f (instead of all) other processes are eventually timely. The significance lies in that the degree of synchrony needed to solve consensus relies on only the resilience (that is, f), independent of the scale n of the system.
Important Links:
Go Back
