Friday, January 28, 2011

Impossibility Result for Asynchronous Consensus

From Fischer, Lynch, Paterson, "Impossibility of Distributed Consensus with One Faulty Process"

In this paper, we show the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We do not consider Byzantine failures, and we assume that the message system is reliable- it delivers all messages correctly and exactly once. Nevertheless, even with these assumptions, the stopping of a single process at an inopportune time can cause any distributed commit protocol to fail to reach agreement. Thus, this important problem has no robust solution without further assumptions about the computing environment or still greater restrictions on the kind of failures to be tolerated!

No comments:

Post a Comment